《離散數(shù)學 課件 考研 大學課程 數(shù)學一 第九章 樹》由會員分享，可在線閱讀，更多相關《離散數(shù)學 課件 考研 大學課程 數(shù)學一 第九章 樹（45頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、【8枚枚硬硬幣幣問問題題】若若有有8枚枚硬硬幣幣a，b，c，d，e，f，g，h，其其中中7枚枚重重量量相相等等，只只有有1枚枚稍稍輕輕?，F(xiàn)現(xiàn)要要求求以以天天平平為為工工具具，最最少少的的比較幾次可以挑出輕幣來？比較幾次可以挑出輕幣來？4/15/20241第九章 樹J定義9.1 連通而不含回路的無向圖稱為無向樹,簡稱樹,常用T表示樹.J連通分支數(shù)大于等于2,且每個連通分支均是樹的非連通無向圖稱為森林.J平凡圖稱為平凡樹.J設T為一棵無向樹,vV,若d(v)1,則稱v為T的樹葉.若d(v)2,則稱v為T的分支點.9.1無向樹及生成樹無向樹及生成樹4/15/20243圖中（a），（b）為樹，而（c）

2、不是樹，但（c）為森林。（a）（b）（c）?例4/15/20244判斷下列哪些圖是樹？v1v2v3v4v5v1v2v3v4v5v1v2v4v3v5(a)(b)(c)解:圖(a)是樹,因為它連通又不包含回路。圖(b),(c)不是樹,因為圖(b)雖連通但有回路,圖(c)雖無回路但不連通。在圖(a)中,v1、v4、v5為均為葉，v2、v3均為分支節(jié)點。?例題4/15/20245連通圖、樹和森林之間的相互轉(zhuǎn)換。?例4/15/20246定理9.1 設G,則下面各命題是等價的:(1)G連通而不含回路;(2)G的每對頂點之間具有唯一的一條路徑;(3)G是連通的且nm+1;(4)G中無回路且nm+1;(5)G

3、中無回路,但在G中任兩個不相鄰的頂點之間 增加一條邊,就形成唯一的一條初級回路;(6)G是連通的且G中每條邊都是橋;(7)G是連通的,但刪除任何一條邊后,就不連通了.其中n為G中頂點數(shù),m為邊數(shù).4/15/20247定理9.2 設T是n階非平凡的樹,則T中至少有2片樹葉.證明：設樹T有x片樹葉，樹T中所有結(jié)點的度數(shù)之和 等于邊數(shù)的2倍。在樹T中邊數(shù)等于結(jié)點數(shù)減1，即n1。所以2(n1)=。另一方面，樹中的分支點為n-x個，每個分支點的度數(shù)大于等于2，所有分支點度數(shù)之和大于等于2(nx)，從而下式成立：2(n-1)=x+2(n-x)解之，得 x2。4/15/20248畫出5階所有非同構(gòu)的無向樹。

4、解：設Ti為5階無向樹,則Ti的邊數(shù)為4，Ti的度序列之和為8，(Ti)4,(Ti)1,可能的度序列為：(1)1,1,1,1,4 (2)1,1,1,2,3 (3)1,1,2,2,2稱只有一個分支點且其度數(shù)為稱只有一個分支點且其度數(shù)為n-1的的n階無向樹為階無向樹為星形圖星形圖，稱，稱唯一的分支點為唯一的分支點為星心星心。?例題4/15/20249定義9.2 設G是無向連通圖,T是G的生成子圖,并且T是樹,則稱T是G的生成樹.G在T中的邊稱為T的樹枝,G不在T中的邊稱為T的弦.T的所有弦的集合的導出子圖稱為T的余樹.圖(b)，(c)為圖(a)的兩棵生成樹。?例（a）（b）（c）4/15/2024

5、10(2)為(1)的一棵生成樹T,(3)為T的余樹.?例（1）（2）（3）余樹可能不連通，也可能含回路。4/15/202411定理9.3 任何連通圖G至少存在一棵生成樹.推論1 設n階無向連通圖G有m條邊,則 mn-1.推論2 設n階無向連通圖G有m條邊,T是G的生成樹,T是T的余樹,則T中有m-n+1條邊.（1）（2）（3）m=8,n=54/15/202412圖中,初級回路aed，bdf，cef.這3個回路中每一個回路都只含一條弦,其余的邊都是樹枝,這樣的回路稱為基本回路基本回路.abcdef4/15/202413定義9.3 設T是n階連通圖G=的一棵生成樹,G有n條邊.設e1,e2,em-

6、n+1為T的弦,設Cr是T加弦er產(chǎn)生的G的回路,r=1,2,m-n+1.稱Cr為對應于弦er的基本回路,稱C1,C2,Cm-n+1為對應生成樹T的基本回路系統(tǒng).在右圖中,Ca=aed,Cb=dbf,Cc=cef,為對應生成樹T的基本回路，Ca,Cb,Cc為T的基本回路系統(tǒng)。一個連通圖G對應不同的生成樹的基本回路及基本回路系統(tǒng)可能不同，但基本回路的個數(shù)等于m-n+1.abcdef4/15/202414J定義9.4 設T是n階連通圖G=的一棵生成樹,稱T的n-1個樹枝對應的G的n-1個割集(每個割集只含一個樹枝,其余的邊都是弦)S1,S2,Sn-1為對應生成樹T的G的基本割集,稱S1,S2,Sn

7、-1為對應生成樹T的基本割集系統(tǒng).對一個n階連通圖G來說,基本割集的個數(shù)必為n-1個,這是G的固有特性.4/15/202415在右下圖所示的圖G中,實邊所構(gòu)成的子圖是G的一棵生成樹T，求T對應的基本回路和基本回路系統(tǒng)，基本割集和基本割集系統(tǒng)。解:G中頂點數(shù)n=6,邊數(shù)m=9，基本回路個數(shù)為m-n+1=4,即T有4條弦，f,g,h,i。對應每條弦有一個基本回路：Cf=face;Cr=gba;Ch=hdcb;Ci=ied;基本回路系統(tǒng)為 Cf,Cr,Ch,Ci.abcdefghiT有5個樹枝a,b,c,d,e,因而有5個基本割集:Sa=a,g,f ;Sb=b,g,h ;Sc=c,f,h ;Sd=d

8、,i,h ;Se=e,f,i.基本割集系統(tǒng)為Sa,Sb,Sc,Sd,Se.?例題例題4/15/202416定義9.5 設無向連通帶權圖G=,T是G的一棵生成樹.T各邊帶權之和稱為T的權,記作W(T).G的所有生成樹中帶權最小的生成樹稱為最小生成樹.問題的提出：問題的提出：要在要在 n 個城市間建立通信聯(lián)絡個城市間建立通信聯(lián)絡網(wǎng)。網(wǎng)。頂點頂點：表示城市，表示城市，權：權：城市間通信線路的城市間通信線路的花費代價。希望此通信網(wǎng)花費代價最小?；ㄙM代價。希望此通信網(wǎng)花費代價最小。4/15/202417問題分析：答案只能從生成樹中找，因為要做到任何兩個城市之間有線路可達，通信網(wǎng)必須是連通的；但對長度最小

9、的要求可以知道網(wǎng)中顯然不能有圈，如果有圈，去掉一條邊后，并不破壞連通性，但總代價顯然減少了，這與總代價最小的假設是矛盾的。結(jié)論：希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網(wǎng)所需花費的總代價）最小 最小代價生成樹。4/15/202418Kruskal算法(避圈法)設n階無向連通帶權圖G=中有m條邊e1,e2,em,它們帶的權分別為a1,a2,am,不妨設a1a2am.(1)取e1在T中(e1非環(huán),若e1為環(huán),則棄e1)；(2)若e2不與e1構(gòu)成回路,取e2在T中,否則棄e2,再查e3,繼續(xù)這一過程,直到形成生成樹T為止.用以上算法生成的T是最小生成樹.4/15/202419用避圈法

10、求下圖所示的最小生成樹.abcdef5555136642解:?例題例題W(T)=1+2+3+4+5=154/15/202420febacd546036388404820452815383062251210hg鋪設一個連接各個城市的光纖通信網(wǎng)絡。（單位：萬元）?例題例題4/15/202421V1V6V5V4V3V26513566425算法思想：算法思想：設設 N=(V,E)是連通網(wǎng)，是連通網(wǎng)，TE 是是 N 上最小生成樹中上最小生成樹中邊的集合邊的集合。初始令初始令 U=u0,(u0 V),TE=。在所有在所有 u U,v V-U 的邊的邊(u,v)E 中，中，找一條代價最小的邊找一條代價最小的

11、邊(u0,v0)。將將(u0,v0)并入集合并入集合 TE，同時同時 v0 并入并入 U。重復上述操作直至重復上述操作直至 U=V 為止，則為止，則 T=(V,TE)為為 N 的最小生成樹。的最小生成樹。V1V3V6V4V2V5構(gòu)造最小生成樹的另一方法：普里姆(Prim)算法 4/15/202422 設D是有向圖,如果略去有向邊的方向所得無向圖為一棵無向樹,則稱D為有向樹。定義 9.6 設T是n(n 2)階有向樹，若T中有一個頂點的入度為0，其余的頂點的入度均為1，則稱T為根樹。v入度為0的頂點稱為樹根，v入度為1出度為0的頂點稱為樹葉，v入度為1出度不為0的頂點稱為內(nèi)點，內(nèi)點和樹根統(tǒng)稱為分支

12、點。9.2根樹及其應用根樹及其應用4/15/202423(1)(2)v0v1v2v3v4v5v6v7下圖(1)為一棵根樹。v0為樹根,v1,v4,v3,v6,v7為樹葉,v2,v5為內(nèi)點,v0,v2,v5為均為分支點,由于在根樹中有向邊的方向均一致,故可省掉其方向,如圖(2)v0v1v2v3v4v5v6v74/15/202424v從樹根到T的任意頂點v的通路（路徑）長度稱為v的層數(shù)層數(shù)，記為l(v).層數(shù)最大頂點的層數(shù)稱為樹高樹高，記為h(T)。v0v1v2v3v4v5v6v7左圖中,v1,v2,v3,在第一層上，v4,v5在第二層上，v6,v7在第三層上。樹高為3。4/15/202425家族

13、樹一棵根樹可以看成一棵家族樹：(1)若頂點a鄰接到頂點b，則稱b為a的兒子，a為b的父親；(2)若b，c同為a的兒子，則稱b，c為兄弟；(3)若ad，而a可達d，則稱a為d的祖先，d為a的后代。v0v1v2v3v4v5v6v74/15/202426定義9.7 設T為一棵根樹，a為T中的一個頂點，且a不是樹根，稱a及其后代導出的子圖T為T的以a為根的子樹，簡稱根子樹。定義9.8 設T為根樹，若將T中層數(shù)相同的 頂點都標定次序，則稱T為有序樹。4/15/202427定義9.9 設T為一棵根樹：（1）若T的每個分支點至多有r個兒子，則稱T為r元樹（r叉樹）；（2）若T的每個分支點都恰好有r個兒子，則

14、稱T為r元正則樹；（3）若r元樹T是有序的，則稱T是r元有序樹；根樹分成下列各類根樹分成下列各類4/15/202428（4）若r元正則樹T是有序的，則稱T是r元有序正則樹；（5)若T是r元正則樹，且所有樹葉的層數(shù)相同，都等于樹高，則稱T為r元完全正則樹；（6）若r元完全正則樹T是有序樹，則稱T是r元有序完全正則樹。4/15/202429圖（1）為2元有序樹，圖（2）為2元有序正則樹，圖（3）為2元有序完全正則樹。112121 21212121212（1）（2）（3）4/15/202430定義9.10 設2元樹T有t片樹葉,分別帶權為w1,w2,wi,wt(wi為實數(shù),i1,2,t,)稱為T的權

15、,其中L(wi)為帶權wi的樹葉vi的層數(shù).在所有的帶權w1,w2,wt的2元樹中,帶權最小的2元樹稱為最優(yōu)2元樹.4/15/202431在下圖所示的三棵樹中,都是帶權1,3,4,5,6的二元樹,W(T1)=47，W(T2)=54，W(T3)=42。T234561 115463T154631T34/15/202432n給定實數(shù)w1,w2,wt,且w1w2wt.n (1)連接w1,w2為權的兩片樹葉,得一分支點,其權為w1w2;n (2)在w1w2,w3,wt中選出兩個最小的權,連接它們對應的頂點(不一定都是樹葉),得分支點及所帶的權;n (3)重復(2),直到形成t1個分支點,t片樹葉為止.H

16、uffmanHuffman算法算法 一種求最優(yōu)二叉樹的算法一種求最優(yōu)二叉樹的算法4/15/202433【例】求帶權2，2，3，3，5的最優(yōu)二叉樹T。最優(yōu)樹的權為：W(T)=2323523232=344/15/202434最優(yōu)二叉樹在通信編碼中的應用定義9.11 設=12 n-1n為長為n的符號串,稱其子串 1,12,12 n-1 分別為該符號串的長度為1,2,n-1的前綴前綴.設B=1,2,m 為一個符號串集合,若對于任意的i,j B,i j,i,j 互不為前綴,則稱B為前綴碼前綴碼.若符號串中i(i=1,2,m)只出現(xiàn)0,1兩個符號,則稱B為二元前綴碼二元前綴碼。4/15/202435如何產(chǎn)

17、生如何產(chǎn)生二元前綴二元前綴碼呢？碼呢？如：0,10,110,1111 1,01,001,0001 等是(二元)前綴碼而 1,11,101,001,0011 不是(二元)前綴碼4/15/202436由二元樹產(chǎn)生二元前綴碼由二元樹產(chǎn)生二元前綴碼010110101000100010101111【例】右圖所示的二元樹產(chǎn)生的前綴嗎為11,00,011,0100,01014/15/202437 由一棵給定的2元正則樹，可以產(chǎn)生唯一的一個二元前綴碼?！纠坑覉D所示的是一棵2元正則樹,它產(chǎn)生唯一的一個二元前綴碼是000,001,01,10,11。010110014/15/202438提示把各字符看作為樹葉,各

18、字符出現(xiàn)的頻率(或n倍的頻率)作為其相應的權,利用Huffman算法求出最優(yōu)2元樹,由此產(chǎn)生的前綴碼即為最佳前綴碼。利用Huffman算法求出的最優(yōu)2元樹產(chǎn)生的前綴碼稱為最佳前綴碼。4/15/202439【解】將各字符出現(xiàn)的頻率作為其相應的權1=5,2=5,3=5,4=10,5=10,6=15,7=20,8=30為8個權,利用Huffman算法求出的最優(yōu)2叉樹如圖所示(碼長取3,如101傳5)【例題】在通信中,0,1,2,3,4,5,6,7出現(xiàn)的頻率如下 0：30,1：20,2：15 3：10,4：10,5：5 6：5,7：5 求傳輸它們的最佳前綴碼.130305105501100402001

19、0101011000000000010001001100101116020151501001014/15/202440由于0,1,2,3,4,5,6,7出現(xiàn)的頻率為：0:30,1:20,2:15,3:10,4:10,5:5,6:5,7:5圖中方框中的8個碼子是最佳前綴碼。樹T是帶權1,2,8的最優(yōu)二元樹。帶權為i的樹葉vi對應的碼子傳輸出現(xiàn)頻率為i,的數(shù)字，即11傳1,101傳401傳0,0001傳5 001傳2,00001傳6 100傳3,00000傳71303051055011004020010101011000000000010001001100101116020151501001014

20、/15/202441 對于一棵根樹的每個頂點都訪問一次且僅一次稱為行遍或周游一棵樹。對于2叉有序正則樹主要有以下三種周游方式：v 中序行遍法 訪問的次序為：左子樹，樹根，右子樹。v 前序行遍法 訪問的次序為：樹根，左子樹，右子樹。v 后序行遍法 訪問的次序為：左子樹，右子樹，樹根。二元樹的周游及應用4/15/202442【例例】試用三種周游方式行遍下圖試用三種周游方式行遍下圖。中序行遍中序行遍:(a+(bc)d+e)(fg)+a ab bc cg gd df fe e4/15/202443【例例】試用三種周游方式行遍下圖試用三種周游方式行遍下圖。+a ab bc cg gd df fe e前序行遍前序行遍:(+(+a(bc)d)e)(fg)波蘭符號法波蘭符號法:+abcdefg4/15/202444【例例】試用三種周游方式行遍下圖試用三種周游方式行遍下圖。后序行遍后序行遍:(a(bc)+)d)e+)(fg)+a ab bc cg gd df fe e逆波蘭符號法逆波蘭符號法:abc+de+fg4/15/202445