《離散數(shù)學》ppt課件

1、離散數(shù)學離散數(shù)學Discrete Discrete Mathematics Mathematics 16.1 無向樹及其性質無向樹及其性質16.2 生成樹生成樹16.3 根樹及其運用根樹及其運用定義定義16.1無向樹無向樹: 連通無回路的無向圖連通無回路的無向圖平凡樹平凡樹: 平凡圖平凡圖森林森林: 每個連通分支都是樹的非連通的無向圖每個連通分支都是樹的非連通的無向圖樹葉樹葉: 樹中度數(shù)為樹中度數(shù)為1的頂點的頂點分支點分支點: 樹中度數(shù)樹中度數(shù)2的頂點的頂點右圖為一棵右圖為一棵12階樹階樹.聲明聲明:本章中所討論的回路均本章中所討論的回路均 指簡單回路或初級回路指簡單回路或初級回路定理定理16

2、.1 設設G=是是n階階m條邊的無向圖，那么以下等價的：條邊的無向圖，那么以下等價的：1G是樹是樹;2G中恣意兩個頂點之間存在獨一的途徑中恣意兩個頂點之間存在獨一的途徑;3G中無回路且中無回路且m=n1;4G是連通的且是連通的且m=n1;5G是連通的且是連通的且G中任何邊均為橋中任何邊均為橋;6G中沒有回路中沒有回路, 但在任何兩個不同的頂點之間加一條新邊后但在任何兩個不同的頂點之間加一條新邊后所得圖中有獨一的一個含新邊的圈所得圖中有獨一的一個含新邊的圈. 證明：證明： 由于由于G是樹，所以是樹，所以G是連通的，是連通的，u, vV，u和和v之間存在一條路。之間存在一條路。假設路不獨一，設假設

3、路不獨一，設L1和和L2都是都是u和和v之間的路，之間的路，那么由那么由L1和和L2上的邊組成了上的邊組成了G中的一個回路，矛盾。中的一個回路，矛盾。 先證先證G中無回路。假設中無回路。假設G中存在某個結點中存在某個結點v上的環(huán)，上的環(huán)， uV，由條件知，由條件知u到到v存在一條路存在一條路L1：uv， 那么那么u到到v有另一條路有另一條路L2：uvv，矛盾。，矛盾。 假設假設G中存在長度大于等于中存在長度大于等于2的一條回路，那么回路上兩個結點之的一條回路，那么回路上兩個結點之間存在不同的路間存在不同的路, 矛盾。所以矛盾。所以G中無回路。中無回路。 以下用歸納法證明以下用歸納法證明m=n1

4、。 當當n=1時，時，G為平凡圖，為平凡圖，m=0=11=n1。結論成立。結論成立。 設設nk時，結論成立。下證時，結論成立。下證n=k+1時，結論也成立。時，結論也成立。 設設e=(u,v)是是G中的一條邊，由于中的一條邊，由于G中無回路，所以中無回路，所以G-e有兩個有兩個連通分支連通分支G1和和G2，設它們的結點數(shù)和邊數(shù)分別為：，設它們的結點數(shù)和邊數(shù)分別為：n1，m1和和n2，m2。 于是有于是有n1k和和n2k，由歸納假設知：，由歸納假設知：m1=n11和和m2=n2-1， m=m1m21=n1-1n2-11=n-1。只須證明只須證明G是連通的。假設不然是連通的。假設不然,設設G有有s

5、(s2)個連通分支個連通分支G1,G2,Gs, Gi中均無回路，都是樹。由中均無回路，都是樹。由可知，可知，mi=ni1，i=1,s。于是于是m=m1m2ms=n1-1n2-1ns-1=n1n2ns-s=ns，由于由于s2，這與，這與m=n1矛盾。所以矛盾。所以G是連通圖。是連通圖。 只須證明只須證明G的每一條邊均為橋。的每一條邊均為橋。設設e是是G的恣意邊，刪除的恣意邊，刪除e得子圖得子圖G1，它的邊數(shù)，它的邊數(shù)m1=m-1，結點數(shù)，結點數(shù)n1=n， m1=m1=n-1-1=n-2=n1-2n1-1，由習題，由習題14的第的第49題知題知G1不是連通圖，不是連通圖，所以所以e是橋。是橋。 由

6、于由于G中每一條邊均為橋，因此中每一條邊均為橋，因此G中無回路。又由于中無回路。又由于G連通，所以連通，所以G是樹。由是樹。由知，知，u, vV，uv，u與與v之間存在一條獨一的路。之間存在一條獨一的路。在在u與與v之間添加一條新邊之間添加一條新邊, 得到得到G的一條回路的一條回路, 顯然這條回路是獨一的。顯然這條回路是獨一的。 只須證明只須證明G是連通的，是連通的，u, vV，uv，在，在u與與v之間添加一條新邊之間添加一條新邊(u,v)就產(chǎn)生就產(chǎn)生G的一個獨一的回路，故結點的一個獨一的回路，故結點u和結點和結點v連通。由于連通。由于u與與v是恣意是恣意的，所以的，所以G是連通圖。是連通圖。

7、 )(2)()1(2xnxvdni 定理定理16.2 設設T 是是 n 階非平凡的無向樹，那么階非平凡的無向樹，那么T中至少有兩片中至少有兩片樹葉樹葉. 由上式解出由上式解出x2.證證 設設T有有x片樹葉，由握手定理及定理片樹葉，由握手定理及定理9.1可知，可知，例例1 知無向樹知無向樹T中中, 有有1個個3度頂點度頂點, 2個個2度頂點度頂點, 其他頂點全是其他頂點全是樹葉樹葉. 試求樹葉數(shù)試求樹葉數(shù), 并畫出滿足要求的非同構的無向樹并畫出滿足要求的非同構的無向樹. 解解 用樹的性質用樹的性質m=n1和握手定理和握手定理. 設有設有x片樹葉，于是片樹葉，于是 n=1+2+x=3+x, 2m=

8、2(n1)=2(2+x)=13+22+x解出解出x=3，故，故T有有3片樹葉片樹葉. T的度數(shù)列為的度數(shù)列為1, 1, 1, 2, 2, 3 有有2棵非同構的無向樹棵非同構的無向樹, 如下圖如下圖例例2 知無向樹知無向樹T有有5片樹葉片樹葉, 2度與度與3度頂點各度頂點各1個個, 其他頂點的度數(shù)其他頂點的度數(shù)均為均為4. 求求T的階數(shù)的階數(shù)n, 并畫出滿足要求的一切非同構的無向樹并畫出滿足要求的一切非同構的無向樹. 解解 設設T的階數(shù)為的階數(shù)為n, 那么邊數(shù)為那么邊數(shù)為n1, 4度頂點的個數(shù)為度頂點的個數(shù)為n7. 由由握手定理得握手定理得 2m=2(n1)=51+21+31+4(n7)解出解出

9、n=8, 4度頂點為度頂點為1個個. T的度數(shù)列為的度數(shù)列為1,1,1,1,1,2,3,4 有有3棵非同構的無向樹棵非同構的無向樹 定義定義16.2 設設G為無向連通圖為無向連通圖G的生成樹的生成樹: G的生成子圖并且是樹的生成子圖并且是樹生成樹生成樹T的樹枝的樹枝: G在在T中的邊中的邊生成樹生成樹T的弦的弦: G不在不在T中的邊中的邊T留意：留意： 不一定連通不一定連通, 也不一定不含回路也不一定不含回路.T生成樹生成樹T的余樹的余樹 : 一切弦的集合的導出子圖一切弦的集合的導出子圖例例e1e2e7e8e9e11e10e3e5e4e6(1)(2)生成樹生成樹T的弦的弦: e6, e7, e

10、8, e10 , e11定理定理16.3無向圖無向圖G具有生成樹當且僅當具有生成樹當且僅當G為連通圖。為連通圖。證明：必要行顯然。證明：必要行顯然。以下證明假設無向圖以下證明假設無向圖G為連通圖，那么為連通圖，那么G具有生成樹。具有生成樹。假設連通圖假設連通圖G無回路，那么無回路，那么G本身就是一棵生成樹；本身就是一棵生成樹；假設假設G至少有一個回路，刪除此回路的一邊，得到子圖至少有一個回路，刪除此回路的一邊，得到子圖G1，它依然，它依然連通，并與連通，并與G有一樣結點集。有一樣結點集。假設假設G1無回路，那么無回路，那么G1就是一棵生成樹；就是一棵生成樹；假設假設G1仍有一個回路，再刪除仍有

11、一個回路，再刪除G1回路上的一邊。回路上的一邊。反復上述過程反復上述過程,直至得到一個無回路的連通圖直至得到一個無回路的連通圖, 該圖就是一棵生成樹該圖就是一棵生成樹.推論推論3 設設 為為G的生成樹的生成樹 T 的余樹，的余樹，C 為為G 中恣意一個圈，那么中恣意一個圈，那么C與與 一定有公共邊一定有公共邊. TT推論推論1 設設n階無向連通圖有階無向連通圖有m條邊條邊, 那么那么mn1. 推論推論2 設設n階無向連通圖有階無向連通圖有m條邊條邊, 那么它的生成樹的余樹有那么它的生成樹的余樹有mn+1條邊條邊.定義定義16.3 設設T是是n階階m條邊的無向連通圖條邊的無向連通圖G的一棵生成樹

12、的一棵生成樹,設設e1, e2, , emn+1為為T的弦的弦. 設設Cr為為T添加弦添加弦er產(chǎn)生的產(chǎn)生的G中獨一的中獨一的圈圈, 稱稱Cr為對應弦為對應弦er的根本回路或根本圈的根本回路或根本圈, r=1, 2, mn+1. 稱稱C1, C2, , Cmn+1為對應為對應T的根本回路系統(tǒng)的根本回路系統(tǒng). mn1稱為稱為G的圈的圈秩秩.無向連通圖的秩，與生成樹的選擇無關。無向連通圖的秩，與生成樹的選擇無關。求根本回路的算法求根本回路的算法: 設弦設弦e=(u,v), 先求先求T中中u到到v的途徑的途徑 uv, 再并上弦再并上弦e, 即得對應即得對應e的根本回路的根本回路. 例例e1e2e7e

13、8e9e11e10e3e5e4e6生成樹生成樹T的弦的弦: e6, e7, e8, e10 , e11它們對應的根本回路分別為它們對應的根本回路分別為: C1=e6e4e5 C2=e7e2e1C3=e8e9e2e1 C4=e10e3e5e2C4=e11e3e5e2e9上圖的圈秩為上圖的圈秩為5,根本回路系統(tǒng)為根本回路系統(tǒng)為C1,C2, C3,C4,C5.定義定義16.5 設設T是是n階連通圖階連通圖G的一棵生成樹的一棵生成樹, e1, e2, , en1為為T的樹枝，的樹枝，Si是是G的只含樹枝的只含樹枝ei, 其他邊都是弦的割集其他邊都是弦的割集, 稱稱Si為對應生為對應生成樹成樹T由樹枝由

14、樹枝ei生成的根本割集生成的根本割集, i=1, 2, , n1. 稱稱S1, S2, , Sn1為對應為對應T的根本割集系統(tǒng)的根本割集系統(tǒng).稱稱n1為為G的割集秩的割集秩. 求根本割集的算法求根本割集的算法: 設設e為生成樹為生成樹T的樹枝的樹枝, Te由兩棵子樹由兩棵子樹T1與與T2組成組成, 令令 Se=e | eE(G)且且e的兩個端點分別屬于的兩個端點分別屬于T1與與T2 那么那么Se為為e對應的根本割集對應的根本割集. 例例e1e2e7e8e9e11e10e3e5e4e6T的樹枝的樹枝: e1, e2, e3, e4, e5, e9它們的根本割集分別為它們的根本割集分別為:S1 =

15、e1, e7, e8, S2 =e2, e7, e8 , e10, e11, S3 =e3, e10, e11, S4 =e4, e6, S5 =e5, e6, e10, e11, S9 =e9, e8 , e11 .G的割集秩為的割集秩為6.例例 圖中紅邊為一棵生成樹圖中紅邊為一棵生成樹, , 求對應它的根本回路系統(tǒng)求對應它的根本回路系統(tǒng) 與根本割集系統(tǒng)與根本割集系統(tǒng)解解 弦弦e,f,ge,f,g對應的根本回路分別為對應的根本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d, Ce=e b c, Cf=f a b c, Cg=g a b c d, C C基基=

16、Ce, Cf, Cg. =Ce, Cf, Cg. 樹枝樹枝a,b,c,da,b,c,d對應的根本割集分別為對應的根本割集分別為 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S S基基=Sa, Sb, Sc, Sd.=Sa, Sb, Sc, Sd.定義定義16.4 對無向圖或有向圖的每一條邊對無向圖或有向圖的每一條邊e附加一個實數(shù)附加一個實數(shù)w(e), 稱作邊稱作邊e的權的權. 圖連同附加在邊上的權稱作帶權圖圖連同附加在邊上的權稱作帶權圖,

17、記作記作G=. 設設G是是G的子圖的子圖, G一切邊的權的和稱作一切邊的權的和稱作G的權的權, 記作記作W(G). 最小生成樹最小生成樹: 帶權圖權最小的生成樹帶權圖權最小的生成樹求最小生成樹的算法求最小生成樹的算法避圈法避圈法 (Kruskal)設設G=, 將非環(huán)邊按權從小到大排序：將非環(huán)邊按權從小到大排序：e1, e2, , em.(1) 取取e1在在T中中(2) 檢查檢查e2, 假設假設e2與與e1不構成回路不構成回路, 那么將那么將e2參與參與T中中, 否那否那么棄去么棄去e2.(3) 檢查檢查e3, 反復進展直至得到生成樹為止反復進展直至得到生成樹為止. 例例 求圖的一棵最小生成樹求

18、圖的一棵最小生成樹 W(T)=38有向樹有向樹根樹、樹根、樹葉、內點、分支點根樹、樹根、樹葉、內點、分支點家族樹、根子樹、有序樹家族樹、根子樹、有序樹r叉樹叉樹r叉有序樹叉有序樹r叉正那么樹叉正那么樹r叉有序正那么樹叉有序正那么樹r叉完全正那么樹叉完全正那么樹r叉有序完全正那么樹叉有序完全正那么樹最優(yōu)最優(yōu)2叉樹與叉樹與Huffman算法算法前綴嗎與最正確前綴嗎前綴嗎與最正確前綴嗎中序行遍法、前序行遍法、后續(xù)行遍法中序行遍法、前序行遍法、后續(xù)行遍法波蘭符號法與逆波蘭符號法波蘭符號法與逆波蘭符號法 有向樹有向樹: 基圖為無向樹的有向圖基圖為無向樹的有向圖定義定義16.6 根樹根樹: 有一個頂點入度

19、為有一個頂點入度為0, 其他的入度均為其他的入度均為1的非平凡的有向樹的非平凡的有向樹樹根樹根: 有向樹中入度為有向樹中入度為0的頂點的頂點樹葉樹葉: 有向樹中入度為有向樹中入度為1, 出度為出度為0的頂點的頂點內點內點: 有向樹中入度為有向樹中入度為1, 出度大于出度大于0的頂點的頂點分支點分支點: 樹根與內點的總稱樹根與內點的總稱頂點頂點v的層數(shù)的層數(shù): 從樹根到從樹根到v的通路長度的通路長度樹高樹高: 有向樹中頂點的最大層數(shù)有向樹中頂點的最大層數(shù)根樹的畫法根樹的畫法: :樹根放上方樹根放上方, ,省去一切有向邊上的箭頭省去一切有向邊上的箭頭如右圖所示如右圖所示 a a是樹根是樹根 b,e

20、,f,h,i b,e,f,h,i是樹葉是樹葉 c,d,g c,d,g是內點是內點 a,c,d,g a,c,d,g是分支點是分支點 a a為為0 0層層;1;1層有層有b,c; 2b,c; 2層有層有d,e,f;d,e,f; 3 3層有層有g,h; 4g,h; 4層有層有i.i. 樹高為樹高為4 4定義定義16.7 根樹看作一棵家族樹根樹看作一棵家族樹:(1) 假設頂點假設頂點 a 鄰接到頂點鄰接到頂點 b, 那么稱那么稱 b 是是 a 的兒子的兒子, a 是是 b 的父親的父親;(2) 假設假設b和和c為同一個頂點的兒子為同一個頂點的兒子, 那么稱那么稱b和和c是兄弟是兄弟;(3) 假設假設a

21、b且且a可達可達b, 那么稱那么稱a是是b的祖先的祖先, b是是a的后代的后代.有序樹有序樹: 將根樹同層上的頂點規(guī)定次序將根樹同層上的頂點規(guī)定次序r叉樹叉樹:根樹的每個分支點至多有根樹的每個分支點至多有r個兒子個兒子r叉正那么樹叉正那么樹: 根樹的每個分支點恰有根樹的每個分支點恰有r個兒子個兒子r叉完全正那么樹叉完全正那么樹: 樹葉層數(shù)一樣的樹葉層數(shù)一樣的r元正那么樹元正那么樹r叉有序樹叉有序樹: 有序的有序的r元樹元樹r叉正那么有序樹叉正那么有序樹: 有序的有序的r元正那么樹元正那么樹r叉完全正那么有序樹叉完全正那么有序樹: 有序的有序的r元完全正那么樹元完全正那么樹)()(1itiivl

22、wtW 定義定義16.9 設設2叉樹叉樹T有有t片樹葉片樹葉v1, v2, , vt, 樹葉的權分別樹葉的權分別 為為w1, w2, , wt, 稱稱 為為T的權的權, 記作記作 W(T), 其中其中l(wèi)(vi)是是vi的層數(shù)的層數(shù). 在一切有在一切有t片樹葉片樹葉, 帶權帶權 w1, w2, , wt 的的 2元元樹中樹中, 權最小的權最小的2叉樹稱為最優(yōu)叉樹稱為最優(yōu) 2叉樹叉樹.定義定義16.8 設設v為根樹的一個頂點且不是樹根為根樹的一個頂點且不是樹根, 稱稱v及其一切后代及其一切后代的導出子圖為以的導出子圖為以v為根的根子樹為根的根子樹. 2叉正那么有序樹的每個分支點的兩個兒子導出的根子

23、樹分叉正那么有序樹的每個分支點的兩個兒子導出的根子樹分別稱為左子樹和右子樹別稱為左子樹和右子樹.例子例子:P313 圖圖16.7以下圖中的三棵樹以下圖中的三棵樹T1，T2和和T3都是帶權都是帶權2，2，3，3，5的二叉樹的二叉樹.以上三棵樹不是最優(yōu)樹。以上三棵樹不是最優(yōu)樹。W(T1)=2222335332=38W(T2)=3454332221=47W(T3)=3333522222=36它們的權分別是：它們的權分別是： Huffman算法算法:給定給定t片樹葉的權為片樹葉的權為W1,W2,Wt且且W1W2Wt。 銜接權為銜接權為W1，W2的兩片樹葉，得一分枝點，其權為的兩片樹葉，得一分枝點，其權

24、為W1W2在在W1W2，W3，Wt中選出兩個最小的權，銜接它們對中選出兩個最小的權，銜接它們對應的結點應的結點(不一定是樹葉不一定是樹葉)，得新分枝點及所帶的權，得新分枝點及所帶的權反復，直到構成反復，直到構成t1個分枝點，個分枝點，t片樹葉為止片樹葉為止例例16.4 求帶權求帶權2，2，3，3，5的最優(yōu)二叉樹的最優(yōu)二叉樹T。 解：生成最優(yōu)二叉樹的過程解：生成最優(yōu)二叉樹的過程最優(yōu)樹的權為：最優(yōu)樹的權為：W(T)=2323523232=34例例 求帶權為求帶權為1, 1, 2, 3, 4, 5的最優(yōu)樹的最優(yōu)樹. 解題過程由以下圖給出解題過程由以下圖給出W(T)=38定義定義16.10 設設 =1

25、2n-1n是長度為是長度為n的符號串的符號串的前綴的前綴: 12k , k=1,2,n-1 前綴碼前綴碼: 1, 2, , m, 其中其中1, 2, , m為非空字為非空字符串符串, 且任何兩個互不為前綴且任何兩個互不為前綴2元前綴碼元前綴碼: 只出現(xiàn)兩個符號只出現(xiàn)兩個符號(如如0與與1)的前綴碼的前綴碼(2) 0,10,110, 1111, 10,01,001,110是前綴碼是前綴碼 0,10,010, 1010 不是前綴碼不是前綴碼例如例如(1) 1,00,011,0101,01001,01000是前綴碼。而是前綴碼。而 1,00,0101,0100,01001,01000不是前綴碼不是前

26、綴碼一棵一棵2元樹產(chǎn)生一個二元前綴碼元樹產(chǎn)生一個二元前綴碼:對每個分支點對每個分支點, 假設關聯(lián)假設關聯(lián)2條邊條邊, 那么給左邊標那么給左邊標0, 右邊標右邊標1; 假設只關聯(lián)假設只關聯(lián)1條邊條邊, 那么可以給它標那么可以給它標0(左左), 也可以標也可以標1(右右). 將從樹根到每一片樹葉的通路上標的數(shù)字組成的字符串記在將從樹根到每一片樹葉的通路上標的數(shù)字組成的字符串記在樹葉處樹葉處, 所得的字符串構成一個前綴碼所得的字符串構成一個前綴碼.如右圖所示如右圖所示定理定理16.6 由一棵給定的二叉正那么樹，可以產(chǎn)生獨一的二元前綴由一棵給定的二叉正那么樹，可以產(chǎn)生獨一的二元前綴碼碼.例例16.5求

27、以下圖所示的二叉樹產(chǎn)生的前綴碼。求以下圖所示的二叉樹產(chǎn)生的前綴碼。產(chǎn)生的前綴碼為：產(chǎn)生的前綴碼為：01,11,000,0010,0011 例例 在通訊中，設八進制數(shù)字出現(xiàn)的頻率如下：在通訊中，設八進制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%采用采用2元前綴碼元前綴碼, 求傳輸數(shù)字最少的求傳輸數(shù)字最少的2元前綴碼元前綴碼 (稱作最正確稱作最正確前前綴碼綴碼), 并求傳輸并求傳輸10n(n2)個按上述比例出現(xiàn)的八進制數(shù)字個按上述比例出現(xiàn)的八進制數(shù)字需需要多少個二進制數(shù)字？假設用等長的要多少個二進制數(shù)字？假設用等長的 (長為長為

28、3) 的碼字傳輸需的碼字傳輸需求求多少個二進制數(shù)字多少個二進制數(shù)字?解解 用用Huffman算法求以頻率算法求以頻率(乘以乘以100)為權的最優(yōu)為權的最優(yōu)2元樹元樹. 這這里里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最優(yōu)最優(yōu)2元樹如下圖元樹如下圖. 編碼編碼: 0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001傳傳100個按比例出現(xiàn)的八進制數(shù)字所需二進制數(shù)字的個數(shù)為個按比例出現(xiàn)的八進制數(shù)字所需二進制數(shù)字的個數(shù)為 W(T)=285.傳傳10n(n2)個所用二進制數(shù)字的個數(shù)為個所用二進制數(shù)字的個數(shù)為2.8510n, 而用等長碼而用等長碼(長為長為3)需求用需求用 310n