《無向樹及生成樹》PPT課件.ppt

1 第9章樹 9 1無向樹及生成樹9 2根樹及其應(yīng)用 2 9 1無向樹及生成樹 無向樹 森林樹枝 弦 余樹生成樹基本回路與基本回路系統(tǒng)基本割集與基本割集系統(tǒng)最小生成樹 3 無向樹 無向樹 樹 連通而無回路的無向圖 用T表示 平凡樹 平凡圖森林 每個(gè)連通分支都是樹的非連通的無向圖樹葉 樹中度數(shù)為1的頂點(diǎn)分支點(diǎn) 樹中度數(shù) 2的頂點(diǎn)右圖為一棵12階樹 聲明 本章中所討論的回路均指簡(jiǎn)單回路或初級(jí)回路 4 無向樹的性質(zhì) 定理9 1設(shè)G 是n階m條邊的無向圖 則下面各命題是等價(jià)的 1 G是樹 連通無回路 2 G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑 3 G中無回路且m n 1 4 G是連通的且m n 1 5 G是連通的且G中任何邊均為橋 6 G中沒有回路 但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈 5 無向樹的性質(zhì) 續(xù) 定理9 2設(shè)T是n階非平凡的無向樹 則T中至少有兩片樹葉 證設(shè)T有x片樹葉 由握手定理及定理9 1可知 由上式解出x 2 6 例題 例1已知無向樹T中 有1個(gè)3度頂點(diǎn) 2個(gè)2度頂點(diǎn) 其余頂點(diǎn)全是樹葉 試求樹葉數(shù) 并畫出滿足要求的非同構(gòu)的無向樹 解用樹的性質(zhì)m n 1和握手定理 設(shè)有x片樹葉 于是n 1 2 x 3 x 2m 2 n 1 2 2 x 1 3 2 2 x解出x 3 故T有3片樹葉 T的度數(shù)列為1 1 1 2 2 3有2棵非同構(gòu)的無向樹 如圖所示 7 例題 例2已知無向樹T有5片樹葉 2度與3度頂點(diǎn)各1個(gè) 其余頂點(diǎn)的度數(shù)均為4 求T的階數(shù)n 并畫出滿足要求的所有非同構(gòu)的無向樹 解設(shè)T的階數(shù)為n 則邊數(shù)為n 1 4度頂點(diǎn)的個(gè)數(shù)為n 7 由握手定理得2m 2 n 1 5 1 2 1 3 1 4 n 7 解出n 8 4度頂點(diǎn)為1個(gè) T的度數(shù)列為1 1 1 1 1 2 3 4有3棵非同構(gòu)的無向樹 8 生成樹 設(shè)G為無向連通圖G的生成樹 G的生成子圖并且是樹生成樹T的樹枝 G在T中的邊生成樹T的弦 G不在T中的邊生成樹T的余樹 所有弦的集合的導(dǎo)出子圖注意 不一定連通 也不一定不含回路 右圖黑邊構(gòu)成生成樹紅邊構(gòu)成余樹 9 生成樹的存在性 定理任何無向連通圖都有生成樹 證用破圈法 若圖中無圈 則圖本身就是自己的生成樹 否則刪去圈上的任一條邊 這不破壞連通性 重復(fù)進(jìn)行直到無圈為止 剩下的圖是一棵生成樹 推論1設(shè)n階無向連通圖有m條邊 則m n 1 推論2設(shè)n階無向連通圖有m條邊 則它的生成樹的余樹有m n 1條邊 推論3設(shè)為G的生成樹T的余樹 C為G中任意一個(gè)圈 則C與一定有公共邊 10 基本回路與基本回路系統(tǒng) 定義設(shè)T是n階m條邊的無向連通圖G的一棵生成樹 設(shè)e1 e2 e m n 1為T的弦 設(shè)Cr為T添加弦er 產(chǎn)生的G中惟一的圈 由er 和樹枝組成 稱Cr為對(duì)應(yīng)弦er 的基本回路或基本圈 r 1 2 m n 1 稱 C1 C2 Cm n 1 為對(duì)應(yīng)T的基本回路系統(tǒng) 求基本回路的算法 設(shè)弦e u v 先求T中u到v的路徑 uv 再并上弦e 即得對(duì)應(yīng)e的基本回路 11 基本割集與基本割集系統(tǒng) 定義設(shè)T是n階連通圖G的一棵生成樹 e1 e2 e n 1為T的樹枝 Si是G的只含樹枝ei 其他邊都是弦的割集 稱Si為對(duì)應(yīng)生成樹T由樹枝ei 生成的基本割集 i 1 2 n 1 稱 S1 S2 Sn 1 為對(duì)應(yīng)T的基本割集系統(tǒng) 求基本割集的算法 設(shè)e 為生成樹T的樹枝 T e 由兩棵子樹T1與T2組成 令Se e e E G 且e的兩個(gè)端點(diǎn)分別屬于T1與T2 則Se 為e 對(duì)應(yīng)的基本割集 12 實(shí)例 例圖中紅邊為一棵生成樹 求對(duì)應(yīng)它的基本回路系統(tǒng)與基本割集系統(tǒng)解弦e f g對(duì)應(yīng)的基本回路分別為Ce ebc Cf fabc Cg gabcd C基 Ce Cf Cg 樹枝a b c d對(duì)應(yīng)的基本割集分別為Sa a f g Sb b e f g Sc c e fg Sd d g S基 Sa Sb Sc Sd 13 無向圖與最小生成樹 對(duì)無向圖或有向圖的每一條邊e附加一個(gè)實(shí)數(shù)w e 稱作邊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)行直至得到生成樹為止 14 實(shí)例 例求圖的一棵最小生成樹 W T 38 15 9 2根樹及其應(yīng)用 有向樹根樹 樹根 樹葉 內(nèi)點(diǎn) 分支點(diǎn)家族樹 根子樹 有序樹r元樹 r元有序樹 r元正則樹 r元有序正則樹 r元完全正則樹 r元有序完全正則樹 最優(yōu)2元樹與Huffman算法前綴嗎與最佳前綴嗎中序行遍法 前序行遍法 后續(xù)行遍法波蘭符號(hào)法與逆波蘭符號(hào)法 16 有向樹與根樹的定義 有向樹 基圖為無向樹的有向圖根樹 有一個(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ù) 17 根樹 續(xù) 根樹的畫法 樹根放上方 省去所有有向邊上的箭頭如右圖所示a是樹根b e f h i是樹葉c d g是內(nèi)點(diǎn)a c d g是分支點(diǎn)a為0層 1層有b c 2層有d e f 3層有g(shù) h 4層有i 樹高為4 18 家族樹 定義把根樹看作一棵家族樹 1 若頂點(diǎn)a鄰接到頂點(diǎn)b 則稱b是a的兒子 a是b的父親 2 若b和c為同一個(gè)頂點(diǎn)的兒子 則稱b和c是兄弟 3 若a b且a可達(dá)b 則稱a是b的祖先 b是a的后代 設(shè)v為根樹的一個(gè)頂點(diǎn)且不是樹根 稱v及其所有后代的導(dǎo)出子圖為以v為根的根子樹 19 根樹的分類 有序樹 將根樹同層上的頂點(diǎn)規(guī)定次序r元樹 根樹的每個(gè)分支點(diǎn)至多有r個(gè)兒子r元正則樹 根樹的每個(gè)分支點(diǎn)恰有r個(gè)兒子r元完全正則樹 樹葉層數(shù)相同的r元正則樹r元有序樹 有序的r元樹r元正則有序樹 有序的r元正則樹r元完全正則有序樹 有序的r元完全正則樹 20 最優(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元樹 21 求最優(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)等于這2個(gè)兒子的權(quán)之和 重復(fù) 直到只有1個(gè)入度為0的頂點(diǎn)為止 W T 等于所有分支點(diǎn)的權(quán)之和 22 實(shí)例 例求帶權(quán)為1 1 2 3 4 5的最優(yōu)樹解題過程由下圖給出 W T 38 23 前綴碼 設(shè) 1 2 n 1 n是長(zhǎng)度為n的符號(hào)串 的前綴 1 2 k 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 不是前綴碼 24 前綴碼 續(xù) 一棵2元樹產(chǎn)生一個(gè)二元前綴碼 對(duì)每個(gè)分支點(diǎn) 若關(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è)前綴碼 如右圖所示 25 最佳前綴碼 例在通信中 設(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 n 2 個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字 若用等長(zhǎng)的 長(zhǎng)為3 的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字 解用Huffman算法求以頻率 乘以100 為權(quán)的最優(yōu)2元樹 這里w1 5 w2 5 w3 10 w4 10 w5 10 w6 15 w7 20 w8 25 最優(yōu)2元樹如圖所示 26 編碼 0 011 112 0013 1004 1015 00016 000007 00001傳100個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)數(shù)為W T 285 傳10n n 2 個(gè)所用二進(jìn)制數(shù)字的個(gè)數(shù)為2 85 10n 而用等長(zhǎng)碼 長(zhǎng)為3 需要用3 10n個(gè)數(shù)字 27 波蘭符號(hào)法與逆波蘭符號(hào)法 行遍 周游 根樹T 對(duì)T的每個(gè)頂點(diǎn)訪問且僅訪問一次 行遍2元有序正則樹的方式 中序行遍法 左子樹 根 右子樹 前序行遍法 根 左子樹 右子樹 后序行遍法 左子樹 右子樹 根例如 對(duì)圖所示根樹按中序 前序 后序行遍法訪問結(jié)果分別為 ba fdg ceab c dfg e b fgd ec a帶下劃線的是 子 樹根 一對(duì)括號(hào)內(nèi)是一棵子樹 28 波蘭符號(hào)法與逆波蘭符號(hào)法 續(xù) 用2元有序正則樹表示算式 最高層次運(yùn)算放在樹根上 然后依次將運(yùn)算符放在根子樹的根上 數(shù)放在樹葉上 規(guī)定被除數(shù) 被減數(shù)放在左子樹樹葉上 例如 右圖表