《無(wú)向樹(shù)及生成樹(shù)》PPT課件.ppt

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