離散數(shù)學(xué) 課件 考研 大學(xué)課程 數(shù)學(xué)一 第九章 樹

《離散數(shù)學(xué) 課件 考研 大學(xué)課程 數(shù)學(xué)一 第九章 樹》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué) 課件 考研 大學(xué)課程 數(shù)學(xué)一 第九章 樹（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設(shè)T為一棵無向樹,vV,若d(v)1,則稱v為T的樹葉.若d(v)2,則稱v為T的分支點(diǎn).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é)點(diǎn)。?例題4/15/20245連通圖、樹和森林之間的相互轉(zhuǎn)換。?例4/15/20246定理9.1 設(shè)G,則下面各命題是等價的:(1)G連通而不含回路;(2)G的每對頂點(diǎn)之間具有唯一的一條路徑;(3)G是連通的且nm+1;(4)G中無回路且nm+1;(5)G

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

4、解：設(shè)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稱只有一個分支點(diǎn)且其度數(shù)為稱只有一個分支點(diǎn)且其度數(shù)為n-1的的n階無向樹為階無向樹為星形圖星形圖，稱，稱唯一的分支點(diǎn)為唯一的分支點(diǎn)為星心星心。?例題4/15/20249定義9.2 設(shè)G是無向連通圖,T是G的生成子圖,并且T是樹,則稱T是G的生成樹.G在T中的邊稱為T的樹枝,G不在T中的邊稱為T的弦.T的所有弦的集合的導(dǎo)出子圖稱為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 設(shè)n階無向連通圖G有m條邊,則 mn-1.推論2 設(shè)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 設(shè)T是n階連通圖G=的一棵生成樹,G有n條邊.設(shè)e1,e2,em-

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

7、-1為對應(yīng)生成樹T的基本割集系統(tǒng).對一個n階連通圖G來說,基本割集的個數(shù)必為n-1個,這是G的固有特性.4/15/202415在右下圖所示的圖G中,實邊所構(gòu)成的子圖是G的一棵生成樹T，求T對應(yīng)的基本回路和基本回路系統(tǒng)，基本割集和基本割集系統(tǒng)。解:G中頂點(diǎn)數(shù)n=6,邊數(shù)m=9，基本回路個數(shù)為m-n+1=4,即T有4條弦，f,g,h,i。對應(yīng)每條弦有一個基本回路：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 設(shè)無向連通帶權(quán)圖G=,T是G的一棵生成樹.T各邊帶權(quán)之和稱為T的權(quán),記作W(T).G的所有生成樹中帶權(quán)最小的生成樹稱為最小生成樹.問題的提出：問題的提出：要在要在 n 個城市間建立通信聯(lián)絡(luò)個城市間建立通信聯(lián)絡(luò)網(wǎng)。網(wǎng)。頂點(diǎn)頂點(diǎn)：表示城市，表示城市，權(quán)：權(quán)：城市間通信線路的城市間通信線路的花費(fèi)代價。希望此通信網(wǎng)花費(fèi)代價最小?；ㄙM(fèi)代價。希望此通信網(wǎng)花費(fèi)代價最小。4/15/202417問題分析：答案只能從生成樹中找，因為要做到任何兩個城市之間有線路可達(dá)，通信網(wǎng)必須是連通的；但對長度最小

9、的要求可以知道網(wǎng)中顯然不能有圈，如果有圈，去掉一條邊后，并不破壞連通性，但總代價顯然減少了，這與總代價最小的假設(shè)是矛盾的。結(jié)論：希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價）最小 最小代價生成樹。4/15/202418Kruskal算法(避圈法)設(shè)n階無向連通帶權(quán)圖G=中有m條邊e1,e2,em,它們帶的權(quán)分別為a1,a2,am,不妨設(shè)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鋪設(shè)一個連接各個城市的光纖通信網(wǎng)絡(luò)。（單位：萬元）?例題例題4/15/202421V1V6V5V4V3V26513566425算法思想：算法思想：設(shè)設(shè) 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。重復(fù)上述操作直至重復(fù)上述操作直至 U=V 為止，則為止，則 T=(V,TE)為為 N 的最小生成樹。的最小生成樹。V1V3V6V4V2V5構(gòu)造最小生成樹的另一方法：普里姆(Prim)算法 4/15/202422 設(shè)D是有向圖,如果略去有向邊的方向所得無向圖為一棵無向樹,則稱D為有向樹。定義 9.6 設(shè)T是n(n 2)階有向樹，若T中有一個頂點(diǎn)的入度為0，其余的頂點(diǎn)的入度均為1，則稱T為根樹。v入度為0的頂點(diǎn)稱為樹根，v入度為1出度為0的頂點(diǎn)稱為樹葉，v入度為1出度不為0的頂點(diǎn)稱為內(nèi)點(diǎn)，內(nèi)點(diǎn)和樹根統(tǒng)稱為分支

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

13、樹一棵根樹可以看成一棵家族樹：(1)若頂點(diǎn)a鄰接到頂點(diǎn)b，則稱b為a的兒子，a為b的父親；(2)若b，c同為a的兒子，則稱b，c為兄弟；(3)若ad，而a可達(dá)d，則稱a為d的祖先，d為a的后代。v0v1v2v3v4v5v6v74/15/202426定義9.7 設(shè)T為一棵根樹，a為T中的一個頂點(diǎn)，且a不是樹根，稱a及其后代導(dǎo)出的子圖T為T的以a為根的子樹，簡稱根子樹。定義9.8 設(shè)T為根樹，若將T中層數(shù)相同的 頂點(diǎn)都標(biāo)定次序，則稱T為有序樹。4/15/202427定義9.9 設(shè)T為一棵根樹：（1）若T的每個分支點(diǎn)至多有r個兒子，則稱T為r元樹（r叉樹）；（2）若T的每個分支點(diǎn)都恰好有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 設(shè)2元樹T有t片樹葉,分別帶權(quán)為w1,w2,wi,wt(wi為實數(shù),i1,2,t,)稱為T的權(quán)

15、,其中L(wi)為帶權(quán)wi的樹葉vi的層數(shù).在所有的帶權(quán)w1,w2,wt的2元樹中,帶權(quán)最小的2元樹稱為最優(yōu)2元樹.4/15/202431在下圖所示的三棵樹中,都是帶權(quán)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為權(quán)的兩片樹葉,得一分支點(diǎn),其權(quán)為w1w2;n (2)在w1w2,w3,wt中選出兩個最小的權(quán),連接它們對應(yīng)的頂點(diǎn)(不一定都是樹葉),得分支點(diǎn)及所帶的權(quán);n (3)重復(fù)(2),直到形成t1個分支點(diǎn),t片樹葉為止.H

16、uffmanHuffman算法算法 一種求最優(yōu)二叉樹的算法一種求最優(yōu)二叉樹的算法4/15/202433【例】求帶權(quán)2，2，3，3，5的最優(yōu)二叉樹T。最優(yōu)樹的權(quán)為：W(T)=2323523232=344/15/202434最優(yōu)二叉樹在通信編碼中的應(yīng)用定義9.11 設(shè)=12 n-1n為長為n的符號串,稱其子串 1,12,12 n-1 分別為該符號串的長度為1,2,n-1的前綴前綴.設(shè)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倍的頻率)作為其相應(yīng)的權(quán),利用Huffman算法求出最優(yōu)2元樹,由此產(chǎn)生的前綴碼即為最佳前綴碼。利用Huffman算法求出的最優(yōu)2元樹產(chǎn)生的前綴碼稱為最佳前綴碼。4/15/202439【解】將各字符出現(xiàn)的頻率作為其相應(yīng)的權(quán)1=5,2=5,3=5,4=10,5=10,6=15,7=20,8=30為8個權(quán),利用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是帶權(quán)1,2,8的最優(yōu)二元樹。帶權(quán)為i的樹葉vi對應(yīng)的碼子傳輸出現(xiàn)頻率為i,的數(shù)字，即11傳1,101傳401傳0,0001傳5 001傳2,00001傳6 100傳3,00000傳71303051055011004020010101011000000000010001001100101116020151501001014

20、/15/202441 對于一棵根樹的每個頂點(diǎn)都訪問一次且僅一次稱為行遍或周游一棵樹。對于2叉有序正則樹主要有以下三種周游方式：v 中序行遍法 訪問的次序為：左子樹，樹根，右子樹。v 前序行遍法 訪問的次序為：樹根，左子樹，右子樹。v 后序行遍法 訪問的次序為：左子樹，右子樹，樹根。二元樹的周游及應(yīng)用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