9.1無(wú)向樹及生成樹

1、第9章 樹 9.1 無(wú)向樹及生成樹9.2 根樹及其應(yīng)用 19.1 無(wú)向樹及生成樹 無(wú)向樹、森林樹枝、弦、余樹生成樹基本回路與基本回路系統(tǒng)基本割集與基本割集系統(tǒng)最小生成樹 2無(wú)向樹無(wú)向樹(樹): 連通而無(wú)回路的無(wú)向圖，用T表示.平凡樹: 平凡圖森林: 每個(gè)連通分支都是樹的非連通的無(wú)向圖樹葉: 樹中度數(shù)為1的頂點(diǎn)分支點(diǎn): 樹中度數(shù)2的頂點(diǎn)右圖為一棵12階樹.聲明:本章中所討論的回路均 指簡(jiǎn)單回路或初級(jí)回路 3無(wú)向樹的性質(zhì)定理9.1 設(shè)G=是n階m條邊的無(wú)向圖，則下面各命題是等價(jià)的：（1）G是樹(連通無(wú)回路);（2）G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑;（3）G中無(wú)回路且m=n1;（4）G是連通的且m

2、=n1;（5）G是連通的且G中任何邊均為橋;（6）G中沒(méi)有回路, 但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈. 4無(wú)向樹的性質(zhì)(續(xù))定理9.2 設(shè)T 是 n 階非平凡的無(wú)向樹，則T中至少有兩片樹葉. 證 設(shè)T有x片樹葉，由握手定理及定理9.1可知， 由上式解出x2.5例題例1 已知無(wú)向樹T中, 有1個(gè)3度頂點(diǎn), 2個(gè)2度頂點(diǎn), 其余頂點(diǎn)全是樹葉. 試求樹葉數(shù), 并畫出滿足要求的非同構(gòu)的無(wú)向樹. 解 用樹的性質(zhì)m=n1和握手定理. 設(shè)有x片樹葉，于是 n=1+2+x=3+x, 2m=2(n1)=2(2+x)=13+22+x解出x=3，故T有3片樹葉. T的度數(shù)列為1,

3、1, 1, 2, 2, 3 有2棵非同構(gòu)的無(wú)向樹, 如圖所示6例題例2 已知無(wú)向樹T有5片樹葉, 2度與3度頂點(diǎn)各1個(gè), 其余頂點(diǎn)的度數(shù)均為4. 求T的階數(shù)n, 并畫出滿足要求的所有非同構(gòu)的無(wú)向樹. 解 設(shè)T的階數(shù)為n, 則邊數(shù)為n1, 4度頂點(diǎn)的個(gè)數(shù)為n7. 由握手定理得 2m=2(n1)=51+21+31+4(n7)解出n=8, 4度頂點(diǎn)為1個(gè). T的度數(shù)列為1,1,1,1,1,2,3,4 有3棵非同構(gòu)的無(wú)向樹 7生成樹 設(shè)G為無(wú)向連通圖G的生成樹: G的生成子圖并且是樹生成樹T的樹枝: G在T中的邊生成樹T的弦: G不在T中的邊生成樹T的余樹 : 所有弦的集合的導(dǎo)出子圖注意： 不一定連通

4、, 也不一定不含回路. 右圖黑邊構(gòu)成生成樹紅邊構(gòu)成余樹8生成樹的存在性 定理 任何無(wú)向連通圖都有生成樹.證 用破圈法. 若圖中無(wú)圈, 則圖本身就是自己的生成樹. 否則刪去圈上的任一條邊, 這不破壞連通性, 重復(fù)進(jìn)行 直到無(wú)圈為止,剩下的圖是一棵生成樹.推論1 設(shè)n階無(wú)向連通圖有m條邊, 則mn1. 推論2 設(shè)n階無(wú)向連通圖有m條邊, 則它的生成樹的余樹 有mn+1條邊. 推論3 設(shè) 為G的生成樹 T 的余樹，C 為G 中任意一個(gè)圈，則C與 一定有公共邊. 9基本回路與基本回路系統(tǒng) 定義 設(shè)T是n階m條邊的無(wú)向連通圖G的一棵生成樹，設(shè)e1, e2, , emn+1為T的弦. 設(shè)Cr為T添加弦er

5、產(chǎn)生的G中惟一的圈(由er和樹枝組成), 稱Cr為對(duì)應(yīng)弦er的基本回路或基本圈, r=1, 2, , mn+1. 稱C1, C2, , Cmn+1為對(duì)應(yīng)T的基本回路系統(tǒng). 求基本回路的算法: 設(shè)弦e=(u,v), 先求T中u到v的路徑uv, 再并上弦e, 即得對(duì)應(yīng)e的基本回路. 10基本割集與基本割集系統(tǒng) 定義 設(shè)T是n階連通圖G的一棵生成樹, e1, e2, , en1為T的樹枝，Si是G的只含樹枝ei, 其他邊都是弦的割集, 稱Si為對(duì)應(yīng)生成樹T由樹枝ei生成的基本割集, i=1, 2, , n1. 稱S1, S2, , Sn1為對(duì)應(yīng)T的基本割集系統(tǒng).求基本割集的算法: 設(shè)e為生成樹T的樹

6、枝, Te由兩棵子樹T1與T2組成, 令 Se=e | eE(G)且e的兩個(gè)端點(diǎn)分別屬于T1與T2 則Se為e對(duì)應(yīng)的基本割集. 11實(shí)例例 圖中紅邊為一棵生成樹, 求對(duì)應(yīng)它的基本回路系統(tǒng) 與基本割集系統(tǒng)解 弦e,f,g對(duì)應(yīng)的基本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基=Ce, Cf, Cg. 樹枝a,b,c,d對(duì)應(yīng)的基本割集分別為 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S基=Sa, Sb, Sc, Sd.12無(wú)向圖與最小生成樹 對(duì)無(wú)向圖或有向圖的每一條邊e附加一個(gè)實(shí)數(shù)w(e), 稱作邊

7、e的權(quán). 圖連同附加在邊上的權(quán)稱作帶權(quán)圖, 記作G=. 設(shè)G是G的子圖, G所有邊的權(quán)的和稱作G的權(quán), 記作W(G). 最小生成樹: 帶權(quán)圖權(quán)最小的生成樹求最小生成樹的算法避圈法 (Kruskal)設(shè)G=, 將非環(huán)邊按權(quán)從小到大排序：e1, e2, , em.(1) 取e1在T中(2) 檢查e2, 若e2與e1不構(gòu)成回路, 則將e2加入T中, 否則棄去e2.(3) 檢查e3, 重復(fù)進(jìn)行直至得到生成樹為止. 13實(shí)例例 求圖的一棵最小生成樹 W(T)=38149.2 根樹及其應(yīng)用有向樹根樹、樹根、樹葉、內(nèi)點(diǎn)、分支點(diǎn)家族樹、根子樹、有序樹r元樹（r元有序樹）r元正則樹（r元有序正則樹）r元完全正則

8、樹（r元有序完全正則樹）最優(yōu)2元樹與Huffman算法前綴嗎與最佳前綴嗎中序行遍法、前序行遍法、后續(xù)行遍法波蘭符號(hào)法與逆波蘭符號(hào)法 15有向樹與根樹的定義 有向樹: 基圖為無(wú)向樹的有向圖根樹: 有一個(gè)頂點(diǎn)入度為0, 其余的入度均為1的 非平凡的有向樹樹根: 有向樹中入度為0的頂點(diǎn)樹葉: 有向樹中入度為1, 出度為0的頂點(diǎn)內(nèi)點(diǎn): 有向樹中入度為1, 出度大于0的頂點(diǎn)分支點(diǎn): 樹根與內(nèi)點(diǎn)的總稱頂點(diǎn)v的層數(shù): 從樹根到v的通路長(zhǎng)度樹高: 有向樹中頂點(diǎn)的最大層數(shù)16根樹(續(xù))根樹的畫法:樹根放上方,省去所有有向邊上的箭頭如右圖所示 a是樹根 b,e,f,h,i是樹葉 c,d,g是內(nèi)點(diǎn) a,c,d,g是

9、分支點(diǎn) a為0層;1層有b,c; 2層有d,e,f; 3層有g(shù),h; 4層有i. 樹高為417家族樹定義 把根樹看作一棵家族樹:(1) 若頂點(diǎn) a 鄰接到頂點(diǎn) b, 則稱 b 是 a 的兒子, a 是 b 的父親;(2) 若b和c為同一個(gè)頂點(diǎn)的兒子, 則稱b和c是兄弟;(3) 若ab且a可達(dá)b, 則稱a是b的祖先, b是a的后代.設(shè)v為根樹的一個(gè)頂點(diǎn)且不是樹根, 稱v及其所有后代的導(dǎo)出子圖為以v為根的根子樹. 18根樹的分類有序樹: 將根樹同層上的頂點(diǎn)規(guī)定次序r元樹:根樹的每個(gè)分支點(diǎn)至多有r個(gè)兒子r元正則樹: 根樹的每個(gè)分支點(diǎn)恰有r個(gè)兒子r元完全正則樹: 樹葉層數(shù)相同的r元正則樹r元有序樹:

10、有序的r元樹r元正則有序樹: 有序的r元正則樹r元完全正則有序樹: 有序的r元完全正則樹19最優(yōu)2元樹 定義 設(shè)2元樹T有t片樹葉v1, v2, , vt, 樹葉的權(quán)分別 為w1, w2, , wt, 稱 為T的權(quán), 記作 W(T), 其中l(wèi)(vi)是vi的層數(shù). 在所有有t片樹葉, 帶權(quán) w1, w2, , wt 的 2元樹中, 權(quán)最小的2元樹稱為最優(yōu) 2元樹.20求最優(yōu)樹 Huffman算法:給定實(shí)數(shù)w1, w2, , wt, 作t片樹葉, 分別以w1, w2, , wt為權(quán). 在所有入度為0的頂點(diǎn)(不一定是樹葉)中選出兩個(gè)權(quán)最小的頂點(diǎn), 添加一個(gè)新分支點(diǎn), 以這2個(gè)頂點(diǎn)為兒子, 其權(quán)等于

11、這2個(gè)兒子的權(quán)之和. 重復(fù), 直到只有1個(gè)入度為0 的頂點(diǎn)為止. W(T)等于所有分支點(diǎn)的權(quán)之和21實(shí)例例 求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹解題過(guò)程由下圖給出，W(T)=38 22前綴碼 設(shè) =12n-1n是長(zhǎng)度為n的符號(hào)串的前綴: 12k , k=1,2,n-1 前綴碼: 1, 2, , m, 其中1, 2, , m為非空字符串, 且任何兩個(gè)互不為前綴2元前綴碼: 只出現(xiàn)兩個(gè)符號(hào)(如0與1)的前綴碼如 0,10,110, 1111, 10,01,001,110是2元前綴碼 0,10,010, 1010 不是前綴碼23前綴碼(續(xù))一棵2元樹產(chǎn)生一個(gè)二元前綴碼:對(duì)每個(gè)分支點(diǎn), 若

12、關(guān)聯(lián)2條邊, 則給左邊標(biāo)0, 右邊標(biāo)1; 若只關(guān)聯(lián)1條邊, 則可以給它標(biāo)0(看作左邊), 也可以標(biāo)1(看作右邊). 將從樹根到每一片樹葉的通路上標(biāo)的數(shù)字組成的字符串記在樹葉處, 所得的字符串構(gòu)成一個(gè)前綴碼.如右圖所示24最佳前綴碼例 在通信中，設(shè)八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%采用2元前綴碼, 求傳輸數(shù)字最少的2元前綴碼 (稱作最佳前綴碼), 并求傳輸10n(n2)個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？若用等長(zhǎng)的 (長(zhǎng)為3) 的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字?解 用Huffman算法求以頻率(乘以1

13、00)為權(quán)的最優(yōu)2元樹. 這里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最優(yōu)2元樹如圖所示. 25 編碼: 0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001傳100個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)數(shù)為 W(T)=285.傳10n(n2)個(gè)所用二進(jìn)制數(shù)字的個(gè)數(shù)為2.8510n, 而用等長(zhǎng)碼(長(zhǎng)為3)需要用 310n個(gè)數(shù)字. 26波蘭符號(hào)法與逆波蘭符號(hào)法 行遍(周游)根樹T : 對(duì)T 的每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次. 行遍2元有序正則樹的方式： 中序行遍法: 左子樹、根、右子樹 前序行遍法: 根、左子樹、右子樹 后序行遍法: 左子樹、右子樹、根 例如, 對(duì)圖所示根樹按中序、前序、 后序行遍法訪問(wèn)結(jié)果分別為： b a (f d g) c e a b (c (d f g) e) b (f g d) e c) a帶下劃線的是(子)樹根, 一對(duì)括號(hào)內(nèi)是一棵子樹 27波蘭符號(hào)法與逆波蘭符號(hào)法(續(xù))用2元有序正則樹表示算式: 最高層次運(yùn)算放在樹根上, 然后依次將運(yùn)算符放在根子樹的根上, 數(shù)放在樹葉上, 規(guī)定被除數(shù)、被減數(shù)放在左子樹樹葉上.例如, 右圖表示算式(b+(c+d)a)(ef)(g+