91無向樹及生成樹ppt課件

1、第第9章章 樹樹 n9.1 無向樹及生成樹無向樹及生成樹n9.2 根樹及其運(yùn)用根樹及其運(yùn)用 9.1 無向樹及生成樹無向樹及生成樹 無向樹、森林無向樹、森林樹枝、弦、余樹樹枝、弦、余樹生成樹生成樹根本回路與根本回路系統(tǒng)根本回路與根本回路系統(tǒng)根本割集與根本割集系統(tǒng)根本割集與根本割集系統(tǒng)最小生成樹最小生成樹 無向樹無向樹無向樹無向樹(樹樹): 連通而無回路的無向圖，用連通而無回路的無向圖，用T表示表示.平凡樹平凡樹: 平凡圖平凡圖森林森林: 每個(gè)連通分支都是樹的非連通的無向圖每個(gè)連通分支都是樹的非連通的無向圖樹葉樹葉: 樹中度數(shù)為樹中度數(shù)為1的頂點(diǎn)的頂點(diǎn)分支點(diǎn)分支點(diǎn): 樹中度數(shù)樹中度數(shù)2的頂點(diǎn)的頂點(diǎn)

2、右圖為一棵右圖為一棵12階樹階樹.聲明聲明:本章中所討論的回路均本章中所討論的回路均 指簡單回路或初級回路指簡單回路或初級回路 無向樹的性質(zhì)無向樹的性質(zhì)定理定理9.1 設(shè)設(shè)G=是是n階階m條邊的無向圖，那么下條邊的無向圖，那么下面各命題是等價(jià)的：面各命題是等價(jià)的：1G是樹是樹(連通無回路連通無回路);2G中恣意兩個(gè)頂點(diǎn)之間存在獨(dú)一的途徑中恣意兩個(gè)頂點(diǎn)之間存在獨(dú)一的途徑;3G中無回路且中無回路且m=n1;4G是連通的且是連通的且m=n1;5G是連通的且是連通的且G中任何邊均為橋中任何邊均為橋;6G中沒有回路中沒有回路, 但在任何兩個(gè)不同的頂點(diǎn)之間但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有獨(dú)

3、一的一個(gè)含新邊的圈加一條新邊后所得圖中有獨(dú)一的一個(gè)含新邊的圈. 無向樹的性質(zhì)無向樹的性質(zhì)( (續(xù)續(xù)) ) )(2)()1(2xnxvdni 定理定理9.2 設(shè)設(shè)T 是是 n 階非平凡的無向樹，那么階非平凡的無向樹，那么T中至中至少少有兩片樹葉有兩片樹葉. 證證 設(shè)設(shè)T有有x片樹葉，由握手定理及定理片樹葉，由握手定理及定理9.1可知，可知， 由上式解出由上式解出x2.例題例題例例1 知無向樹知無向樹T中中, 有有1個(gè)個(gè)3度頂點(diǎn)度頂點(diǎn), 2個(gè)個(gè)2度頂點(diǎn)度頂點(diǎn), 其他頂點(diǎn)全是其他頂點(diǎn)全是樹葉樹葉. 試求樹葉數(shù)試求樹葉數(shù), 并畫出滿足要求的非同構(gòu)的無向樹并畫出滿足要求的非同構(gòu)的無向樹. 解解 用樹的性

4、質(zhì)用樹的性質(zhì)m=n1和握手定理和握手定理. 設(shè)有設(shè)有x片樹葉，于是片樹葉，于是 n=1+2+x=3+x, 2m=2(n1)=2(2+x)=13+22+x解出解出x=3，故，故T有有3片樹葉片樹葉. T的度數(shù)列為的度數(shù)列為1, 1, 1, 2, 2, 3 有有2棵非同構(gòu)的無向樹棵非同構(gòu)的無向樹, 如下圖如下圖例題例題例例2 知無向樹知無向樹T有有5片樹葉片樹葉, 2度與度與3度頂點(diǎn)各度頂點(diǎn)各1個(gè)個(gè), 其他頂點(diǎn)的其他頂點(diǎn)的度數(shù)均為度數(shù)均為4. 求求T的階數(shù)的階數(shù)n, 并畫出滿足要求的一切非同構(gòu)的并畫出滿足要求的一切非同構(gòu)的無向樹無向樹. 解解 設(shè)設(shè)T的階數(shù)為的階數(shù)為n, 那么邊數(shù)為那么邊數(shù)為n1,

5、 4度頂點(diǎn)的個(gè)數(shù)為度頂點(diǎn)的個(gè)數(shù)為n7. 由握手定理得由握手定理得 2m=2(n1)=51+21+31+4(n7)解出解出n=8, 4度頂點(diǎn)為度頂點(diǎn)為1個(gè)個(gè). T的度數(shù)列為的度數(shù)列為1,1,1,1,1,2,3,4 有有3棵非同構(gòu)的無向樹棵非同構(gòu)的無向樹 生成樹生成樹 TT設(shè)設(shè)G為無向連通圖為無向連通圖G的生成樹的生成樹: G的生成子圖并且是樹的生成子圖并且是樹生成樹生成樹T的樹枝的樹枝: G在在T中的邊中的邊生成樹生成樹T的弦的弦: G不在不在T中的邊中的邊生成樹生成樹T的余樹的余樹 : 一切弦的集合的導(dǎo)出子圖一切弦的集合的導(dǎo)出子圖留意：留意： 不一定連通不一定連通, 也不一定不含回路也不一定不

6、含回路. 右圖黑邊構(gòu)成生成樹右圖黑邊構(gòu)成生成樹紅邊構(gòu)成余樹紅邊構(gòu)成余樹生成樹的存在性生成樹的存在性 定理定理 任何無向連通圖都有生成樹任何無向連通圖都有生成樹.證證 用破圈法用破圈法. 假設(shè)圖中無圈假設(shè)圖中無圈, 那么圖本身就是本人的生成樹那么圖本身就是本人的生成樹. 否那么刪去圈上的任一條邊否那么刪去圈上的任一條邊, 這不破壞連通性這不破壞連通性, 反復(fù)進(jìn)展反復(fù)進(jìn)展 直到無圈為止直到無圈為止,剩下的圖是一棵生成樹剩下的圖是一棵生成樹.推論推論1 設(shè)設(shè)n階無向連通圖有階無向連通圖有m條邊條邊, 那么那么mn1. 推論推論2 設(shè)設(shè)n階無向連通圖有階無向連通圖有m條邊條邊, 那么它的生成樹的余樹那

7、么它的生成樹的余樹 有有mn+1條邊條邊. 推論推論3 設(shè)設(shè) 為為G的生成樹的生成樹 T 的余樹，的余樹，C 為為G 中恣意一中恣意一個(gè)圈，那么個(gè)圈，那么C與與 一定有公共邊一定有公共邊. TT根本回路與根本回路系統(tǒng)根本回路與根本回路系統(tǒng) 定義定義 設(shè)設(shè)T是是n階階m條邊的無向連通圖條邊的無向連通圖G的一棵生成的一棵生成樹，設(shè)樹，設(shè)e1, e2, , emn+1為為T的弦的弦. 設(shè)設(shè)Cr為為T添加弦添加弦er產(chǎn)生的產(chǎn)生的G中獨(dú)一的圈中獨(dú)一的圈(由由er和樹枝組成和樹枝組成), 稱稱Cr為對為對應(yīng)應(yīng)弦弦er的根本回路或根本圈的根本回路或根本圈, r=1, 2, , mn+1. 稱稱C1, C2,

8、 , Cmn+1為對應(yīng)為對應(yīng)T的根本回路系統(tǒng)的根本回路系統(tǒng). 求根本回路的算法求根本回路的算法: 設(shè)弦設(shè)弦e=(u,v), 先求先求T中中u到到v的途的途徑徑 uv, 再并上弦再并上弦e, 即得對應(yīng)即得對應(yīng)e的根本回路的根本回路. 根本割集與根本割集系統(tǒng)根本割集與根本割集系統(tǒng) 定義定義 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵生成樹的一棵生成樹, e1, e2, , en1為為T的樹枝，的樹枝，Si是是G的只含樹枝的只含樹枝ei, 其他邊其他邊都是弦都是弦的割集的割集, 稱稱Si為對應(yīng)生成樹為對應(yīng)生成樹T由樹枝由樹枝ei生成的根本生成的根本割割集集, i=1, 2, , n1. 稱稱S1, S2,

9、 , Sn1為對應(yīng)為對應(yīng)T的的根本根本割集系統(tǒng)割集系統(tǒng).求根本割集的算法求根本割集的算法: 設(shè)設(shè)e為生成樹為生成樹T的樹枝的樹枝, Te由兩由兩棵子樹棵子樹T1與與T2組成組成, 令令 Se=e | eE(G)且且e的兩個(gè)端點(diǎn)分別屬于的兩個(gè)端點(diǎn)分別屬于T1與與T2 那么那么Se為為e對應(yīng)的根本割集對應(yīng)的根本割集. 實(shí)例實(shí)例例例 圖中紅邊為一棵生成樹圖中紅邊為一棵生成樹, , 求對應(yīng)它的根本回路系統(tǒng)求對應(yīng)它的根本回路系統(tǒng) 與根本割集系統(tǒng)與根本割集系統(tǒng)解解 弦弦e,f,ge,f,g對應(yīng)的根本回路分別為對應(yīng)的根本回路分別為 Ce=e b c, Cf=f a b c, Cg=g a b c d,Ce=

10、e b c, Cf=f a b c, Cg=g a b c d, C C基基=Ce, Cf, Cg. =Ce, Cf, Cg. 樹枝樹枝a,b,c,da,b,c,d對應(yīng)的根本割集分別為對應(yīng)的根本割集分別為 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g,f g, Sd=d, g, S S基基=Sa, Sb, Sc, Sd.=Sa, Sb, Sc, Sd.無向圖與最小生成樹無向圖與最小生成樹 對無向圖或有向圖的每一條邊對無向圖或有向圖的每一條邊e附加一個(gè)實(shí)數(shù)附加一個(gè)實(shí)數(shù)w(e

11、), 稱作邊稱作邊e的權(quán)的權(quán). 圖連同附加在邊上的權(quán)稱作帶權(quán)圖圖連同附加在邊上的權(quán)稱作帶權(quán)圖, 記作記作G=. 設(shè)設(shè)G是是G的子圖的子圖, G一切邊的權(quán)的和稱作一切邊的權(quán)的和稱作G的權(quán)的權(quán), 記作記作W(G). 最小生成樹最小生成樹: 帶權(quán)圖權(quán)最小的生成樹帶權(quán)圖權(quán)最小的生成樹求最小生成樹的算法求最小生成樹的算法避圈法避圈法 (Kruskal)設(shè)設(shè)G=, 將非環(huán)邊按權(quán)從小到大排序：將非環(huán)邊按權(quán)從小到大排序：e1, e2, , em.(1) 取取e1在在T中中(2) 檢查檢查e2, 假設(shè)假設(shè)e2與與e1不構(gòu)成回路不構(gòu)成回路, 那么將那么將e2參與參與T中中, 否那否那么棄去么棄去e2.(3) 檢查

12、檢查e3, 反復(fù)進(jìn)展直至得到生成樹為止反復(fù)進(jìn)展直至得到生成樹為止. 實(shí)例實(shí)例例例 求圖的一棵最小生成樹求圖的一棵最小生成樹 W(T)=389.2 根樹及其運(yùn)用根樹及其運(yùn)用有向樹有向樹根樹、樹根、樹葉、內(nèi)點(diǎn)、分支點(diǎn)根樹、樹根、樹葉、內(nèi)點(diǎn)、分支點(diǎn)家族樹、根子樹、有序樹家族樹、根子樹、有序樹r元樹元樹r元有序樹元有序樹r元正那么樹元正那么樹r元有序正那么樹元有序正那么樹r元完全正那么樹元完全正那么樹r元有序完全正那么樹元有序完全正那么樹最優(yōu)最優(yōu)2元樹與元樹與Huffman算法算法前綴嗎與最正確前綴嗎前綴嗎與最正確前綴嗎中序行遍法、前序行遍法、后續(xù)行遍法中序行遍法、前序行遍法、后續(xù)行遍法波蘭符號法與逆

13、波蘭符號法波蘭符號法與逆波蘭符號法 有向樹與根樹的定義有向樹與根樹的定義 有向樹有向樹: 基圖為無向樹的有向圖基圖為無向樹的有向圖根樹根樹: 有一個(gè)頂點(diǎn)入度為有一個(gè)頂點(diǎn)入度為0, 其他的入度均為其他的入度均為1的的 非平凡的有向樹非平凡的有向樹樹根樹根: 有向樹中入度為有向樹中入度為0的頂點(diǎn)的頂點(diǎn)樹葉樹葉: 有向樹中入度為有向樹中入度為1, 出度為出度為0的頂點(diǎn)的頂點(diǎn)內(nèi)點(diǎn)內(nèi)點(diǎn): 有向樹中入度為有向樹中入度為1, 出度大于出度大于0的頂點(diǎn)的頂點(diǎn)分支點(diǎn)分支點(diǎn): 樹根與內(nèi)點(diǎn)的總稱樹根與內(nèi)點(diǎn)的總稱頂點(diǎn)頂點(diǎn)v的層數(shù)的層數(shù): 從樹根到從樹根到v的通路長度的通路長度樹高樹高: 有向樹中頂點(diǎn)的最大層數(shù)有向樹中

14、頂點(diǎn)的最大層數(shù)根樹根樹(續(xù)續(xù))根樹的畫法根樹的畫法: :樹根放上方樹根放上方, ,省去一切有向邊上的箭頭省去一切有向邊上的箭頭如右圖所示如右圖所示 a a是樹根是樹根 b,e,f,h,ib,e,f,h,i是樹葉是樹葉 c,d,gc,d,g是內(nèi)點(diǎn)是內(nèi)點(diǎn) a,c,d,ga,c,d,g是分支點(diǎn)是分支點(diǎn) a a為為0 0層層;1;1層有層有b,c; 2b,c; 2層有層有d,e,f;d,e,f; 3 3層有層有g(shù),h; 4g,h; 4層有層有i.i. 樹高為樹高為4 4家族樹家族樹定義定義 把根樹看作一棵家族樹把根樹看作一棵家族樹:(1) 假設(shè)頂點(diǎn)假設(shè)頂點(diǎn) a 鄰接到頂點(diǎn)鄰接到頂點(diǎn) b, 那么稱那么稱

15、 b 是是 a 的兒子的兒子, a 是是 b 的父親的父親;(2) 假設(shè)假設(shè)b和和c為同一個(gè)頂點(diǎn)的兒子為同一個(gè)頂點(diǎn)的兒子, 那么稱那么稱b和和c是兄是兄弟弟;(3) 假設(shè)假設(shè)ab且且a可達(dá)可達(dá)b, 那么稱那么稱a是是b的祖先的祖先, b是是a的的后代后代.設(shè)設(shè)v為根樹的一個(gè)頂點(diǎn)且不是樹根為根樹的一個(gè)頂點(diǎn)且不是樹根, 稱稱v及其一切后及其一切后代的導(dǎo)出子圖為以代的導(dǎo)出子圖為以v為根的根子樹為根的根子樹. 根樹的分類根樹的分類有序樹有序樹: 將根樹同層上的頂點(diǎn)規(guī)定次序?qū)⒏鶚渫瑢由系捻旤c(diǎn)規(guī)定次序r元樹元樹:根樹的每個(gè)分支點(diǎn)至多有根樹的每個(gè)分支點(diǎn)至多有r個(gè)兒子個(gè)兒子r元正那么樹元正那么樹: 根樹的每個(gè)

16、分支點(diǎn)恰有根樹的每個(gè)分支點(diǎn)恰有r個(gè)兒子個(gè)兒子r元完全正那么樹元完全正那么樹: 樹葉層數(shù)一樣的樹葉層數(shù)一樣的r元正那么樹元正那么樹r元有序樹元有序樹: 有序的有序的r元樹元樹r元正那么有序樹元正那么有序樹: 有序的有序的r元正那么樹元正那么樹r元完全正那么有序樹元完全正那么有序樹: 有序的有序的r元完全正那么樹元完全正那么樹最優(yōu)最優(yōu)2 2元樹元樹 )()(1itiivlwtW 定義定義 設(shè)設(shè)2元樹元樹T有有t片樹葉片樹葉v1, v2, , vt, 樹葉的權(quán)分樹葉的權(quán)分別別 為為w1, w2, , wt, 稱稱 為為T的權(quán)的權(quán), 記作記作 W(T), 其中其中l(wèi)(vi)是是vi的層數(shù)的層數(shù). 在一

17、切有在一切有t片樹葉片樹葉, 帶權(quán)帶權(quán) w1, w2, , wt 的的 2元樹中元樹中, 權(quán)最小的權(quán)最小的2元樹稱為最元樹稱為最優(yōu)優(yōu) 2元樹元樹.求最優(yōu)樹求最優(yōu)樹 Huffman算法算法:給定實(shí)數(shù)給定實(shí)數(shù)w1, w2, , wt, 作作t片樹葉片樹葉, 分別以分別以w1, w2, , wt為權(quán)為權(quán). 在一切入度為在一切入度為0的頂點(diǎn)的頂點(diǎn)(不一定是樹葉不一定是樹葉)中選出兩個(gè)中選出兩個(gè)權(quán)最小的頂點(diǎn)權(quán)最小的頂點(diǎn), 添加一個(gè)新分支點(diǎn)添加一個(gè)新分支點(diǎn), 以這以這2個(gè)頂點(diǎn)為個(gè)頂點(diǎn)為兒子兒子, 其權(quán)等于這其權(quán)等于這2個(gè)兒子的權(quán)之和個(gè)兒子的權(quán)之和. 反復(fù)反復(fù), 直到只需直到只需1個(gè)入度為個(gè)入度為0 的頂點(diǎn)

18、為止的頂點(diǎn)為止. W(T)等于一切分支點(diǎn)的權(quán)之和等于一切分支點(diǎn)的權(quán)之和實(shí)例實(shí)例例例 求帶權(quán)為求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹的最優(yōu)樹解題過程由以下圖給出，解題過程由以下圖給出，W(T)=38 前綴碼前綴碼 設(shè)設(shè) =12n-1n是長度為是長度為n的符號串的符號串的前綴的前綴: 12k , k=1,2,n-1 前綴碼前綴碼: 1, 2, , m, 其中其中1, 2, , m為為非空字符非空字符串串, 且任何兩個(gè)互不為前綴且任何兩個(gè)互不為前綴2元前綴碼元前綴碼: 只出現(xiàn)兩個(gè)符號只出現(xiàn)兩個(gè)符號(如如0與與1)的前綴碼的前綴碼如如 0,10,110, 1111, 10,01,001,11

19、0是是2元前綴碼元前綴碼 0,10,010, 1010 不是前綴碼不是前綴碼前綴碼前綴碼( (續(xù)續(xù)) )一棵一棵2元樹產(chǎn)生一個(gè)二元前綴碼元樹產(chǎn)生一個(gè)二元前綴碼:對每個(gè)分支點(diǎn)對每個(gè)分支點(diǎn), 假設(shè)關(guān)聯(lián)假設(shè)關(guān)聯(lián)2條邊條邊, 那么給左邊標(biāo)那么給左邊標(biāo)0, 右邊右邊標(biāo)標(biāo)1; 假設(shè)只關(guān)聯(lián)假設(shè)只關(guān)聯(lián)1條邊條邊, 那么可以給它標(biāo)那么可以給它標(biāo)0(看作左邊看作左邊), 也也可以可以標(biāo)標(biāo)1(看作右邊看作右邊). 將從樹根到每一片樹葉的通路上標(biāo)將從樹根到每一片樹葉的通路上標(biāo)的數(shù)字組成的字符串的數(shù)字組成的字符串記在樹葉處記在樹葉處, 所得的字符所得的字符串構(gòu)成一個(gè)前綴碼串構(gòu)成一個(gè)前綴碼.如右圖所示如右圖所示最正確前綴

20、碼最正確前綴碼例例 在通訊中，設(shè)八進(jìn)制數(shù)字出現(xiàn)的頻率如下：在通訊中，設(shè)八進(jì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)個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？假設(shè)用等長的要多少個(gè)二進(jìn)制數(shù)字？假設(shè)用等長的 (長為長為3) 的碼字傳輸需的碼字傳輸需求求多少個(gè)二進(jìn)制數(shù)字多少個(gè)二進(jìn)制數(shù)字?解解 用用Huffman算法求以頻率算法求以頻率(乘以乘

21、以100)為權(quán)的最優(yōu)為權(quán)的最優(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個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)數(shù)個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)數(shù)為為 W(T)=285.傳傳10n(n2)個(gè)所用二進(jìn)制數(shù)字的個(gè)數(shù)為個(gè)所用二進(jìn)制數(shù)字的個(gè)數(shù)為2.8510n, 而用等而用等長長碼碼(長為長為3)需求用需求用 310n個(gè)數(shù)字個(gè)數(shù)字. 波蘭符號法與逆波蘭符號法波蘭符號法與逆波蘭符號法 行遍行遍(周游周游)根樹根樹T : 對對T 的每個(gè)頂點(diǎn)訪問且僅訪問一次的每個(gè)頂點(diǎn)訪問且僅訪問一次. 行遍行遍2元有序正那么樹的方式：元有序正那么樹的方式： 中序行遍法中序行遍法: 左子樹、根、右子樹左子樹、根、右子樹 前序行遍法前序行遍法: 根、左子樹、右子樹根、左子樹、右子樹 后序行遍法后序行遍法: 左子樹、