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

【8枚枚硬硬幣幣問(wèn)問(wèn)題題】若若有有8枚枚硬硬幣幣a，b，c，d，e，f，g，h，其其中中7枚枚重重量量相相等等，只只有有1枚枚稍稍輕輕?，F(xiàn)現(xiàn)要要求求以以天天平平為為工工具具，最最少少的的比較幾次可以挑出輕幣來(lái)？比較幾次可以挑出輕幣來(lái)？4/15/20241第九章 樹(shù)J定義9.1 連通而不含回路的無(wú)向圖稱(chēng)為無(wú)向樹(shù),簡(jiǎn)稱(chēng)樹(shù),常用T表示樹(shù).J連通分支數(shù)大于等于2,且每個(gè)連通分支均是樹(shù)的非連通無(wú)向圖稱(chēng)為森林.J平凡圖稱(chēng)為平凡樹(shù).J設(shè)T為一棵無(wú)向樹(shù),vV,若d(v)1,則稱(chēng)v為T(mén)的樹(shù)葉.若d(v)2,則稱(chēng)v為T(mén)的分支點(diǎn).9.1無(wú)向樹(shù)及生成樹(shù)無(wú)向樹(shù)及生成樹(shù)4/15/20243圖中（a），（b）為樹(shù)，而（c）不是樹(shù)，但（c）為森林。（a）（b）（c）?例4/15/20244判斷下列哪些圖是樹(shù)？v1v2v3v4v5v1v2v3v4v5v1v2v4v3v5(a)(b)(c)解:圖(a)是樹(shù),因?yàn)樗B通又不包含回路。圖(b),(c)不是樹(shù),因?yàn)閳D(b)雖連通但有回路,圖(c)雖無(wú)回路但不連通。在圖(a)中,v1、v4、v5為均為葉，v2、v3均為分支節(jié)點(diǎn)。?例題4/15/20245連通圖、樹(shù)和森林之間的相互轉(zhuǎn)換。?例4/15/20246定理9.1 設(shè)G,則下面各命題是等價(jià)的:(1)G連通而不含回路;(2)G的每對(duì)頂點(diǎn)之間具有唯一的一條路徑;(3)G是連通的且nm+1;(4)G中無(wú)回路且nm+1;(5)G中無(wú)回路,但在G中任兩個(gè)不相鄰的頂點(diǎn)之間 增加一條邊,就形成唯一的一條初級(jí)回路;(6)G是連通的且G中每條邊都是橋;(7)G是連通的,但刪除任何一條邊后,就不連通了.其中n為G中頂點(diǎn)數(shù),m為邊數(shù).4/15/20247定理9.2 設(shè)T是n階非平凡的樹(shù),則T中至少有2片樹(shù)葉.證明：設(shè)樹(shù)T有x片樹(shù)葉，樹(shù)T中所有結(jié)點(diǎn)的度數(shù)之和 等于邊數(shù)的2倍。在樹(shù)T中邊數(shù)等于結(jié)點(diǎn)數(shù)減1，即n1。所以2(n1)=。另一方面，樹(shù)中的分支點(diǎn)為n-x個(gè)，每個(gè)分支點(diǎn)的度數(shù)大于等于2，所有分支點(diǎn)度數(shù)之和大于等于2(nx)，從而下式成立：2(n-1)=x+2(n-x)解之，得 x2。4/15/20248畫(huà)出5階所有非同構(gòu)的無(wú)向樹(shù)。解：設(shè)Ti為5階無(wú)向樹(shù),則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稱(chēng)只有一個(gè)分支點(diǎn)且其度數(shù)為稱(chēng)只有一個(gè)分支點(diǎn)且其度數(shù)為n-1的的n階無(wú)向樹(shù)為階無(wú)向樹(shù)為星形圖星形圖，稱(chēng)，稱(chēng)唯一的分支點(diǎn)為唯一的分支點(diǎn)為星心星心。?例題4/15/20249定義9.2 設(shè)G是無(wú)向連通圖,T是G的生成子圖,并且T是樹(shù),則稱(chēng)T是G的生成樹(shù).G在T中的邊稱(chēng)為T(mén)的樹(shù)枝,G不在T中的邊稱(chēng)為T(mén)的弦.T的所有弦的集合的導(dǎo)出子圖稱(chēng)為T(mén)的余樹(shù).圖(b)，(c)為圖(a)的兩棵生成樹(shù)。?例（a）（b）（c）4/15/202410(2)為(1)的一棵生成樹(shù)T,(3)為T(mén)的余樹(shù).?例（1）（2）（3）余樹(shù)可能不連通，也可能含回路。4/15/202411定理9.3 任何連通圖G至少存在一棵生成樹(shù).推論1 設(shè)n階無(wú)向連通圖G有m條邊,則 mn-1.推論2 設(shè)n階無(wú)向連通圖G有m條邊,T是G的生成樹(shù),T是T的余樹(shù),則T中有m-n+1條邊.（1）（2）（3）m=8,n=54/15/202412圖中,初級(jí)回路aed，bdf，cef.這3個(gè)回路中每一個(gè)回路都只含一條弦,其余的邊都是樹(shù)枝,這樣的回路稱(chēng)為基本回路基本回路.abcdef4/15/202413定義9.3 設(shè)T是n階連通圖G=的一棵生成樹(shù),G有n條邊.設(shè)e1,e2,em-n+1為T(mén)的弦,設(shè)Cr是T加弦er產(chǎn)生的G的回路,r=1,2,m-n+1.稱(chēng)Cr為對(duì)應(yīng)于弦er的基本回路,稱(chēng)C1,C2,Cm-n+1為對(duì)應(yīng)生成樹(shù)T的基本回路系統(tǒng).在右圖中,Ca=aed,Cb=dbf,Cc=cef,為對(duì)應(yīng)生成樹(shù)T的基本回路，Ca,Cb,Cc為T(mén)的基本回路系統(tǒng)。一個(gè)連通圖G對(duì)應(yīng)不同的生成樹(shù)的基本回路及基本回路系統(tǒng)可能不同，但基本回路的個(gè)數(shù)等于m-n+1.abcdef4/15/202414J定義9.4 設(shè)T是n階連通圖G=的一棵生成樹(shù),稱(chēng)T的n-1個(gè)樹(shù)枝對(duì)應(yīng)的G的n-1個(gè)割集(每個(gè)割集只含一個(gè)樹(shù)枝,其余的邊都是弦)S1,S2,Sn-1為對(duì)應(yīng)生成樹(shù)T的G的基本割集,稱(chēng)S1,S2,Sn-1為對(duì)應(yīng)生成樹(shù)T的基本割集系統(tǒng).對(duì)一個(gè)n階連通圖G來(lái)說(shuō),基本割集的個(gè)數(shù)必為n-1個(gè),這是G的固有特性.4/15/202415在右下圖所示的圖G中,實(shí)邊所構(gòu)成的子圖是G的一棵生成樹(shù)T，求T對(duì)應(yīng)的基本回路和基本回路系統(tǒng)，基本割集和基本割集系統(tǒng)。解:G中頂點(diǎn)數(shù)n=6,邊數(shù)m=9，基本回路個(gè)數(shù)為m-n+1=4,即T有4條弦，f,g,h,i。對(duì)應(yīng)每條弦有一個(gè)基本回路：Cf=face;Cr=gba;Ch=hdcb;Ci=ied;基本回路系統(tǒng)為 Cf,Cr,Ch,Ci.abcdefghiT有5個(gè)樹(shù)枝a,b,c,d,e,因而有5個(gè)基本割集:Sa=a,g,f ;Sb=b,g,h ;Sc=c,f,h ;Sd=d,i,h ;Se=e,f,i.基本割集系統(tǒng)為Sa,Sb,Sc,Sd,Se.?例題例題4/15/202416定義9.5 設(shè)無(wú)向連通帶權(quán)圖G=,T是G的一棵生成樹(shù).T各邊帶權(quán)之和稱(chēng)為T(mén)的權(quán),記作W(T).G的所有生成樹(shù)中帶權(quán)最小的生成樹(shù)稱(chēng)為最小生成樹(shù).問(wèn)題的提出：?jiǎn)栴}的提出：要在要在 n 個(gè)城市間建立通信聯(lián)絡(luò)個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)。網(wǎng)。頂點(diǎn)頂點(diǎn)：表示城市，表示城市，權(quán)：權(quán)：城市間通信線(xiàn)路的城市間通信線(xiàn)路的花費(fèi)代價(jià)。希望此通信網(wǎng)花費(fèi)代價(jià)最小。花費(fèi)代價(jià)。希望此通信網(wǎng)花費(fèi)代價(jià)最小。4/15/202417問(wèn)題分析：答案只能從生成樹(shù)中找，因?yàn)橐龅饺魏蝺蓚€(gè)城市之間有線(xiàn)路可達(dá)，通信網(wǎng)必須是連通的；但對(duì)長(zhǎng)度最小的要求可以知道網(wǎng)中顯然不能有圈，如果有圈，去掉一條邊后，并不破壞連通性，但總代價(jià)顯然減少了，這與總代價(jià)最小的假設(shè)是矛盾的。結(jié)論：希望找到一棵生成樹(shù)，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小 最小代價(jià)生成樹(shù)。4/15/202418Kruskal算法(避圈法)設(shè)n階無(wú)向連通帶權(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ù)這一過(guò)程,直到形成生成樹(shù)T為止.用以上算法生成的T是最小生成樹(shù).4/15/202419用避圈法求下圖所示的最小生成樹(shù).abcdef5555136642解:?例題例題W(T)=1+2+3+4+5=154/15/202420febacd546036388404820452815383062251210hg鋪設(shè)一個(gè)連接各個(gè)城市的光纖通信網(wǎng)絡(luò)。（單位：萬(wàn)元）?例題例題4/15/202421V1V6V5V4V3V26513566425算法思想：算法思想：設(shè)設(shè) N=(V,E)是連通網(wǎng)，是連通網(wǎng)，TE 是是 N 上最小生成樹(shù)中上最小生成樹(shù)中邊的集合邊的集合。初始令初始令 U=u0,(u0 V),TE=。在所有在所有 u U,v V-U 的邊的邊(u,v)E 中，中，找一條代價(jià)最小的邊找一條代價(jià)最小的邊(u0,v0)。將將(u0,v0)并入集合并入集合 TE，同時(shí)同時(shí) v0 并入并入 U。重復(fù)上述操作直至重復(fù)上述操作直至 U=V 為止，則為止，則 T=(V,TE)為為 N 的最小生成樹(shù)。的最小生成樹(shù)。V1V3V6V4V2V5構(gòu)造最小生成樹(shù)的另一方法：普里姆(Prim)算法 4/15/202422 設(shè)D是有向圖,如果略去有向邊的方向所得無(wú)向圖為一棵無(wú)向樹(shù),則稱(chēng)D為有向樹(shù)。定義 9.6 設(shè)T是n(n 2)階有向樹(shù)，若T中有一個(gè)頂點(diǎn)的入度為0，其余的頂點(diǎn)的入度均為1，則稱(chēng)T為根樹(shù)。v入度為0的頂點(diǎn)稱(chēng)為樹(shù)根，v入度為1出度為0的頂點(diǎn)稱(chēng)為樹(shù)葉，v入度為1出度不為0的頂點(diǎn)稱(chēng)為內(nèi)點(diǎn)，內(nèi)點(diǎn)和樹(shù)根統(tǒng)稱(chēng)為分支點(diǎn)。9.2根樹(shù)及其應(yīng)用根樹(shù)及其應(yīng)用4/15/202423(1)(2)v0v1v2v3v4v5v6v7下圖(1)為一棵根樹(shù)。v0為樹(shù)根,v1,v4,v3,v6,v7為樹(shù)葉,v2,v5為內(nèi)點(diǎn),v0,v2,v5為均為分支點(diǎn),由于在根樹(shù)中有向邊的方向均一致,故可省掉其方向,如圖(2)v0v1v2v3v4v5v6v74/15/202424v從樹(shù)根到T的任意頂點(diǎn)v的通路（路徑）長(zhǎng)度稱(chēng)為v的層數(shù)層數(shù)，記為l(v).層數(shù)最大頂點(diǎn)的層數(shù)稱(chēng)為樹(shù)高樹(shù)高，記為h(T)。v0v1v2v3v4v5v6v7左圖中,v1,v2,v3,在第一層上，v4,v5在第二層上，v6,v7在第三層上。樹(shù)高為3。4/15/202425家族樹(shù)一棵根樹(shù)可以看成一棵家族樹(shù)：(1)若頂點(diǎn)a鄰接到頂點(diǎn)b，則稱(chēng)b為a的兒子，a為b的父親；(2)若b，c同為a的兒子，則稱(chēng)b，c為兄弟；(3)若ad，而a可達(dá)d，則稱(chēng)a為d的祖先，d為a的后代。v0v1v2v3v4v5v6v74/15/202426定義9.7 設(shè)T為一棵根樹(shù)，a為T(mén)中的一個(gè)頂點(diǎn)，且a不是樹(shù)根，稱(chēng)a及其后代導(dǎo)出的子圖T為T(mén)的以a為根的子樹(shù)，簡(jiǎn)稱(chēng)根子樹(shù)。定義9.8 設(shè)T為根樹(shù)，若將T中層數(shù)相同的 頂點(diǎn)都標(biāo)定次序，則稱(chēng)T為有序樹(shù)。4/15/202427定義9.9 設(shè)T為一棵根樹(shù)：（1）若T的每個(gè)分支點(diǎn)至多有r個(gè)兒子，則稱(chēng)T為r元樹(shù)（r叉樹(shù)）；（2）若T的每個(gè)分支點(diǎn)都恰好有r個(gè)兒子，則稱(chēng)T為r元正則樹(shù)；（3）若r元樹(shù)T是有序的，則稱(chēng)T是r元有序樹(shù)；根樹(shù)分成下列各類(lèi)根樹(shù)分成下列各類(lèi)4/15/202428（4）若r元正則樹(shù)T是有序的，則稱(chēng)T是r元有序正則樹(shù)；（5)若T是r元正則樹(shù)，且所有樹(shù)葉的層數(shù)相同，都等于樹(shù)高，則稱(chēng)T為r元完全正則樹(shù)；（6）若r元完全正則樹(shù)T是有序樹(shù)，則稱(chēng)T是r元有序完全正則樹(shù)。4/15/202429圖（1）為2元有序樹(shù)，圖（2）為2元有序正則樹(shù)，圖（3）為2元有序完全正則樹(shù)。112121 21212121212（1）（2）（3）4/15/202430定義9.10 設(shè)2元樹(shù)T有t片樹(shù)葉,分別帶權(quán)為w1,w2,wi,wt(wi為實(shí)數(shù),i1,2,t,)稱(chēng)為T(mén)的權(quán),其中L(wi)為帶權(quán)wi的樹(shù)葉vi的層數(shù).在所有的帶權(quán)w1,w2,wt的2元樹(shù)中,帶權(quán)最小的2元樹(shù)稱(chēng)為最優(yōu)2元樹(shù).4/15/202431在下圖所示的三棵樹(shù)中,都是帶權(quán)1,3,4,5,6的二元樹(shù),W(T1)=47，W(T2)=54，W(T3)=42。T234561 115463T154631T34/15/202432n給定實(shí)數(shù)w1,w2,wt,且w1w2wt.n (1)連接w1,w2為權(quán)的兩片樹(shù)葉,得一分支點(diǎn),其權(quán)為w1w2;n (2)在w1w2,w3,wt中選出兩個(gè)最小的權(quán),連接它們對(duì)應(yīng)的頂點(diǎn)(不一定都是樹(shù)葉),得分支點(diǎn)及所帶的權(quán);n (3)重復(fù)(2),直到形成t1個(gè)分支點(diǎn),t片樹(shù)葉為止.HuffmanHuffman算法算法 一種求最優(yōu)二叉樹(shù)的算法一種求最優(yōu)二叉樹(shù)的算法4/15/202433【例】求帶權(quán)2，2，3，3，5的最優(yōu)二叉樹(shù)T。最優(yōu)樹(shù)的權(quán)為：W(T)=2323523232=344/15/202434最優(yōu)二叉樹(shù)在通信編碼中的應(yīng)用定義9.11 設(shè)=12 n-1n為長(zhǎng)為n的符號(hào)串,稱(chēng)其子串 1,12,12 n-1 分別為該符號(hào)串的長(zhǎng)度為1,2,n-1的前綴前綴.設(shè)B=1,2,m 為一個(gè)符號(hào)串集合,若對(duì)于任意的i,j B,i j,i,j 互不為前綴,則稱(chēng)B為前綴碼前綴碼.若符號(hào)串中i(i=1,2,m)只出現(xiàn)0,1兩個(gè)符號(hào),則稱(chēng)B為二元前綴碼二元前綴碼。4/15/202435如何產(chǎn)生如何產(chǎn)生二元前綴二元前綴碼呢？碼呢？如：0,10,110,1111 1,01,001,0001 等是(二元)前綴碼而 1,11,101,001,0011 不是(二元)前綴碼4/15/202436由二元樹(shù)產(chǎn)生二元前綴碼由二元樹(shù)產(chǎn)生二元前綴碼010110101000100010101111【例】右圖所示的二元樹(shù)產(chǎn)生的前綴嗎為11,00,011,0100,01014/15/202437 由一棵給定的2元正則樹(shù)，可以產(chǎn)生唯一的一個(gè)二元前綴碼?！纠坑覉D所示的是一棵2元正則樹(shù),它產(chǎn)生唯一的一個(gè)二元前綴碼是000,001,01,10,11。010110014/15/202438提示把各字符看作為樹(shù)葉,各字符出現(xiàn)的頻率(或n倍的頻率)作為其相應(yīng)的權(quán),利用Huffman算法求出最優(yōu)2元樹(shù),由此產(chǎn)生的前綴碼即為最佳前綴碼。利用Huffman算法求出的最優(yōu)2元樹(shù)產(chǎn)生的前綴碼稱(chēng)為最佳前綴碼。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個(gè)權(quán),利用Huffman算法求出的最優(yōu)2叉樹(shù)如圖所示(碼長(zhǎng)取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 求傳輸它們的最佳前綴碼.1303051055011004020010101011000000000010001001100101116020151501001014/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個(gè)碼子是最佳前綴碼。樹(shù)T是帶權(quán)1,2,8的最優(yōu)二元樹(shù)。帶權(quán)為i的樹(shù)葉vi對(duì)應(yīng)的碼子傳輸出現(xiàn)頻率為i,的數(shù)字，即11傳1,101傳401傳0,0001傳5 001傳2,00001傳6 100傳3,00000傳71303051055011004020010101011000000000010001001100101116020151501001014/15/202441 對(duì)于一棵根樹(shù)的每個(gè)頂點(diǎn)都訪問(wèn)一次且僅一次稱(chēng)為行遍或周游一棵樹(shù)。對(duì)于2叉有序正則樹(shù)主要有以下三種周游方式：v 中序行遍法 訪問(wèn)的次序?yàn)椋鹤笞訕?shù)，樹(shù)根，右子樹(shù)。v 前序行遍法 訪問(wèn)的次序?yàn)椋簶?shù)根，左子樹(shù)，右子樹(shù)。v 后序行遍法 訪問(wèn)的次序?yàn)椋鹤笞訕?shù)，右子樹(shù)，樹(shù)根。二元樹(shù)的周游及應(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)波蘭符號(hào)法波蘭符號(hào)法:+abcdefg4/15/202444【例例】試用三種周游方式行遍下圖試用三種周游方式行遍下圖。后序行遍后序行遍:(a(bc)+)d)e+)(fg)+a ab bc cg gd df fe e逆波蘭符號(hào)法逆波蘭符號(hào)法:abc+de+fg4/15/202445