離散數(shù)學71-2

1、1第第7 7章章 樹及其應用樹及其應用2第第7 7章章 樹及其應用樹及其應用 7.1 無向樹無向樹 7.2 根樹及其應用根樹及其應用37.1 無向樹無向樹 7.1.1 無向樹的定義及其性質(zhì)無向樹的定義及其性質(zhì) 7.1.2 生成樹與基本回路和基本割集生成樹與基本回路和基本割集 7.1.3 最小生成樹最小生成樹4無向樹的定義無向樹的定義無向樹無向樹: 連通無回路的無向圖連通無回路的無向圖平凡樹平凡樹: 平凡圖平凡圖森林森林: 每個連通分支都是樹的非連通的無向圖每個連通分支都是樹的非連通的無向圖樹葉樹葉: 樹中度數(shù)為樹中度數(shù)為1的頂點的頂點分支點分支點: 樹中度數(shù)樹中度數(shù) 2的頂點的頂點例如例如(a

2、)(b)5無向樹的性質(zhì)無向樹的性質(zhì)定理定理7.1 設設G=是是n階階m條邊的無向圖條邊的無向圖, 下面各命題是下面各命題是等價的：等價的：(1) G是樹是樹(連通無回路連通無回路);(2) G中任意兩個頂點之間存在惟一的路徑中任意兩個頂點之間存在惟一的路徑;(3) G是連通的且是連通的且m=n 1;(4) G中無回路且中無回路且m=n 1;(5) G中無回路中無回路, 但在任何兩個不相鄰的頂點之間加一條邊但在任何兩個不相鄰的頂點之間加一條邊 所得圖中有惟一的一條初級回路所得圖中有惟一的一條初級回路.(6) G是連通的且是連通的且G中任意一條邊均為橋中任意一條邊均為橋.P173(200)6定理定

3、理7.1的證明的證明(1)(2) 由連通性由連通性, 任意任意2個頂點之間有一條路徑個頂點之間有一條路徑. 又又, 假設假設某某2個頂點之間有個頂點之間有2條路徑條路徑, 則這則這2條路徑可組合成一條回條路徑可組合成一條回路路, 與樹的定義矛盾與樹的定義矛盾.(2)(3) 顯然連通顯然連通, 要證要證m=n 1. 對對n作歸納證明作歸納證明. 當當n=1時時, 顯然顯然m=0, 結(jié)論成立結(jié)論成立. 假設當假設當n k(k 1)時結(jié)論成立時結(jié)論成立, 考慮考慮n=k+1. 任取一條邊任取一條邊e=(u,v), 它是它是u,v之間惟一的通路之間惟一的通路, 刪去刪去e, G被分成被分成2個連通分個

4、連通分支支, 設它們分別有設它們分別有n1, n2個頂點和個頂點和m1, m2條邊條邊, n1 k, n2 k. 由歸納假設由歸納假設, m1=n1-1, m2=n2-1, 得得m= m1+m2+1= n-1.7定理定理7.1的證明的證明(續(xù)續(xù))(3)(4) 假設有回路假設有回路, 任取一個回路任取一個回路, 刪去回路中的一條邊刪去回路中的一條邊, 所得圖仍是連通的所得圖仍是連通的. 重復這個做法重復這個做法, 直到?jīng)]有回路為止直到?jīng)]有回路為止, 得得到一棵樹到一棵樹, 它有它有n個頂點個頂點m-r條邊條邊, r0. 由由(1)(2)(3), 得得m-r =n-1, 矛盾矛盾.(4)(1) 只

5、需證只需證G連通連通. 假設假設G不連通不連通, 有有p(p1)個連通分支個連通分支.設第設第k個連通分支有個連通分支有nk個頂點和個頂點和mk條邊條邊, 由由(1)(2)(3),mk= nk-1. 得到得到m= n-p, 矛盾矛盾.8定理定理7.1的證明的證明(續(xù)續(xù))(1)(5) 由由(1)(2), 任意任意2個不相鄰的頂點之間有一條惟個不相鄰的頂點之間有一條惟一的路徑一的路徑, 故在這故在這2個頂點之間添加一條新邊個頂點之間添加一條新邊, 必得到一條必得到一條惟一的初級回路惟一的初級回路.(5)(6) 首先首先, 任意任意2個不相鄰的頂點之間都有一條通路個不相鄰的頂點之間都有一條通路, 否

6、則在它們之間添加一條新邊不可能構(gòu)成回路否則在它們之間添加一條新邊不可能構(gòu)成回路, 故故G連通連通.其次其次, 若刪去一條邊若刪去一條邊G仍是連通的仍是連通的, 這條邊必在一條回路上這條邊必在一條回路上,與與G中無回路矛盾中無回路矛盾.(6)(1) G中無回路中無回路, 否則刪去回路上任意條邊否則刪去回路上任意條邊, G仍連通仍連通.9無向樹的性質(zhì)無向樹的性質(zhì)(續(xù)續(xù))定理定理7.2 非平凡的無向樹至少有兩片樹葉非平凡的無向樹至少有兩片樹葉 證證 設有設有n(n1)個頂點個頂點, x片樹葉片樹葉, 由握手定理和定理由握手定理和定理7.1, 有有 解得解得 x 2.)(2)()1(2xnxvdni

7、10實例實例例例1 已知無向樹已知無向樹T中中, 有有1個個3度頂點度頂點, 2個個2度頂點度頂點, 其余頂其余頂點全是樹葉點全是樹葉. 試求樹葉數(shù)試求樹葉數(shù), 并畫出滿足要求的非同構(gòu)的無并畫出滿足要求的非同構(gòu)的無向樹向樹. 解解 設有設有x片樹葉片樹葉,2 (2+x)=1 3+2 2+x解得解得x=3，故故T有有3片樹葉片樹葉.T的度數(shù)列為的度數(shù)列為1, 1, 1, 2, 2, 311實例實例例例2 畫出所有畫出所有6階非同構(gòu)的無向樹階非同構(gòu)的無向樹P201解解 5條邊條邊, 總度數(shù)等于總度數(shù)等于10可能的度數(shù)列可能的度數(shù)列:(1) 1,1,1,1,1,5(2) 1,1,1,1,2,4(3)

8、 1,1,1,1,3,3(4) 1,1,1,2,2,3(5) 1,1,2,2,2,2(1)(2)(3)(4a)(4b)(5)12生成樹生成樹定義定義7.2 設設G是無向連通圖是無向連通圖, 若若G的生成子圖的生成子圖T是一棵樹是一棵樹, 則則稱稱T是是G的的生成樹生成樹. G在在T中的邊稱作中的邊稱作T的的樹枝樹枝,不在不在T中的邊中的邊稱作稱作T的的弦弦. T的所有弦的集合的導出子圖稱作的所有弦的集合的導出子圖稱作T的的余樹余樹例如例如 圖中黑邊構(gòu)成生成樹圖中黑邊構(gòu)成生成樹紅邊構(gòu)成余樹紅邊構(gòu)成余樹注意注意: 余樹一般不是樹余樹一般不是樹13生成樹的存在性生成樹的存在性定理定理7.3 任何無向

9、連通圖都有生成樹任何無向連通圖都有生成樹.證證 用破圈法用破圈法. 若圖中無圈若圖中無圈, 則圖本身就是自己的生成樹則圖本身就是自己的生成樹. 否則刪去圈上的任一條邊否則刪去圈上的任一條邊, 不破壞連通性不破壞連通性, 重復進行直到重復進行直到無圈為止無圈為止, 得到圖的一棵生成樹得到圖的一棵生成樹.推論推論1 設設n階無向連通圖有階無向連通圖有m條邊條邊, 則則m n 1. 推論推論2 設設n階無向連通圖有階無向連通圖有m條邊條邊, 則它的生成樹的余樹則它的生成樹的余樹有有m n+1條邊條邊.14基本回路與基本回路系統(tǒng)基本回路與基本回路系統(tǒng)定義定義7.3 設設G是是n階階m條邊的無向連通圖條

10、邊的無向連通圖, T是是G的一棵生成的一棵生成樹樹, e1, e2, , em n+1為為T的弦的弦. G中僅含中僅含T的一條弦的一條弦er的圈的圈Cr稱作對應弦稱作對應弦er的的基本回路基本回路. 稱稱C1,C2, , Cm n+1為對應為對應T的的基本回路系統(tǒng)基本回路系統(tǒng)例例3 圖中紅邊為一棵生成樹圖中紅邊為一棵生成樹, ,對應它的基本回路系統(tǒng)為對應它的基本回路系統(tǒng)為bce, fae, gaed 15基本割集與基本割集系統(tǒng)基本割集與基本割集系統(tǒng)定義定義7.4 設設T是是n階連通圖階連通圖G的一棵生成樹的一棵生成樹, e1 , e2 , , e n 1為為T的樹枝，的樹枝，Si是是G的只含樹

11、枝的只含樹枝ei , 其他邊都是弦其他邊都是弦的割集的割集, 稱稱Si為對應樹枝為對應樹枝ei 的的基本割集基本割集. 稱稱S1, S2, , Sn 1為對應為對應T的的基本割集系統(tǒng)基本割集系統(tǒng)例例4 圖中紅邊為一棵生成樹圖中紅邊為一棵生成樹, ,對應它的基本割集系統(tǒng)為對應它的基本割集系統(tǒng)為a,f,g, e,b,f,g, c,b, d,g16最小生成樹最小生成樹圖圖G的每一條邊的每一條邊e附加一個實數(shù)附加一個實數(shù)w(e), 稱作邊稱作邊e的的權(quán)權(quán). 圖圖G連連同附加在邊上的權(quán)稱作同附加在邊上的權(quán)稱作帶權(quán)圖帶權(quán)圖, 記作記作G=. 設設H是是G的子圖的子圖, H所有邊的權(quán)的和稱作所有邊的權(quán)的和稱

12、作H的權(quán)的權(quán), 記作記作W(H). 最小生成樹最小生成樹: 帶權(quán)圖權(quán)最小的生成樹帶權(quán)圖權(quán)最小的生成樹避圈法避圈法 (Kruskal) P205(1) 將所有非環(huán)邊按權(quán)從小到大排列將所有非環(huán)邊按權(quán)從小到大排列, 設為設為e1, e2, , em(2) 令令T = (3) For k=1 to m Do 若若ek與與T 中的邊不構(gòu)成回路中的邊不構(gòu)成回路, 則將則將ek加入加入T 中中17實例實例例例5 求圖的一棵最小生成樹求圖的一棵最小生成樹W(T)=38187.2 根樹及其應用根樹及其應用 7.2.1 根樹及其分類根樹及其分類 7.2.2 最優(yōu)樹與哈夫曼算法最優(yōu)樹與哈夫曼算法 7.2.3 最佳前

13、綴碼最佳前綴碼 7.2.4 根樹的周游及其應用根樹的周游及其應用 中序行遍法、前序行遍法和后序行遍法中序行遍法、前序行遍法和后序行遍法 波蘭符號法與逆波蘭符號法波蘭符號法與逆波蘭符號法19根樹的定義根樹的定義有向樹有向樹: 略去方向后為無向樹的有向圖略去方向后為無向樹的有向圖根樹根樹: 有一個頂點入度為有一個頂點入度為0, 其余的入度均為其余的入度均為1的非平凡的的非平凡的有向樹有向樹樹根樹根: 有向樹中入度為有向樹中入度為0的頂點的頂點樹葉樹葉: 有向樹中入度為有向樹中入度為1, 出度為出度為0的頂點的頂點內(nèi)點內(nèi)點: 有向樹中入度為有向樹中入度為1, 出度大于出度大于0的頂點的頂點分支點分支

14、點: 樹根與內(nèi)點的總稱樹根與內(nèi)點的總稱頂點頂點v的層數(shù)的層數(shù): 從樹根到從樹根到v的通路長度的通路長度樹高樹高: 有向樹中頂點的最大層數(shù)有向樹中頂點的最大層數(shù)20實例實例根樹的畫法根樹的畫法: :樹根放最上方樹根放最上方, ,省去所有有向邊上的箭頭省去所有有向邊上的箭頭右圖中右圖中 a是樹根是樹根 b,e,f,h,i是樹葉是樹葉 c,d,g是內(nèi)點是內(nèi)點 a,c,d,g是分支點是分支點 a為為0層層;1層有層有b,c; 2層有層有d,e,f; 3層有層有g,h; 4層有層有i. 樹高為樹高為421家族樹家族樹把根樹看作一棵把根樹看作一棵家族樹家族樹:若頂點若頂點a鄰接到頂點鄰接到頂點b, 則稱則

15、稱b是是a的的兒子兒子, a是是b的的父親父親若若b和和c為同一個頂點的兒子為同一個頂點的兒子, 則稱則稱b和和c是是兄弟兄弟若若a b且且a可達可達b, 則稱則稱a是是b的的祖先祖先, b是是a的的后代后代設設v為根樹的一個頂點且不是樹根為根樹的一個頂點且不是樹根, 稱稱v及其所有后代的導及其所有后代的導出子圖為以出子圖為以v為根的為根的根子樹根子樹將根樹每一層上的頂點規(guī)定次序后稱作將根樹每一層上的頂點規(guī)定次序后稱作有序樹有序樹22根樹的分類根樹的分類r元樹元樹:根樹的每個分支點至多有根樹的每個分支點至多有r個兒子個兒子r元正則樹元正則樹: 根樹的每個分支點恰有根樹的每個分支點恰有r個兒子個

16、兒子r元完全正則樹元完全正則樹: 所有樹葉層數(shù)相同的所有樹葉層數(shù)相同的r元正則樹元正則樹r元有序樹元有序樹: 有序的有序的r元樹元樹r元正則有序樹元正則有序樹: 有序的有序的r元正則樹元正則樹r元完全正則有序樹元完全正則有序樹: 有序的有序的r元完全正則樹元完全正則樹23最優(yōu)最優(yōu)2元樹元樹定義定義7.10 設設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ù). 在所有有在所有有t片樹葉片樹葉, 帶權(quán)帶權(quán)w1, w2, , wt 的的 2元元樹中樹中

17、, 權(quán)最小的權(quán)最小的2元樹稱為元樹稱為最優(yōu)最優(yōu)2元樹元樹)()(1itiivlwtW 例如例如134 561345613456W(T1)=47W(T2)=54W(T3)=4324求最優(yōu)求最優(yōu)2元樹的算法元樹的算法哈夫曼哈夫曼(Huffman)算法算法給定實數(shù)給定實數(shù)w1, w2, , wt 作作t片樹葉片樹葉, 分別以分別以w1, w2, , wt為權(quán)為權(quán) 在所有入度為在所有入度為0的頂點的頂點(不一定是樹葉不一定是樹葉)中選出兩個權(quán)最中選出兩個權(quán)最小的頂點小的頂點, 添加一個新分支點添加一個新分支點, 以這以這2個頂點為兒子個頂點為兒子, 其其權(quán)等于這權(quán)等于這2個兒子的權(quán)之和個兒子的權(quán)之和

18、重復重復, 直到只有直到只有1個入度為個入度為0 的頂點為止的頂點為止 W(T)等于所有分支點的權(quán)之和等于所有分支點的權(quán)之和25實例實例例例1 求以求以1,3,4,5,6為權(quán)的最優(yōu)為權(quán)的最優(yōu)2元樹元樹, 并計算它的權(quán)并計算它的權(quán)解解134(a)13448(b)134456811(c)1344 5681119(d)W(T)=4+8+11+19=4226最佳前綴碼最佳前綴碼定義定義7.11 設設 = 1 2 n-1 n是長度為是長度為n的符號串的符號串, 1 2 k稱作稱作 的長度為的長度為k的的前綴前綴, k=1,2,n-1. 若非空字符串若非空字符串 1, 2, , m中任何兩個互不為前綴中任

19、何兩個互不為前綴, 則稱則稱 1, 2, , m為為前綴碼前綴碼只出現(xiàn)兩個符號只出現(xiàn)兩個符號(如如0與與1)的前綴碼稱作的前綴碼稱作2元前綴碼元前綴碼例如例如 0,10,110, 1111, 10,01,001,110是是2元前綴碼元前綴碼 0,10,010, 1010 不是前綴碼不是前綴碼27用用2元樹產(chǎn)生元樹產(chǎn)生2元前綴碼的方法元前綴碼的方法對每個分支點對每個分支點, 若關聯(lián)若關聯(lián)2條邊條邊, 則給左邊標則給左邊標0, 右邊標右邊標1; 若只若只關聯(lián)關聯(lián)1條邊條邊, 則可以給它標則可以給它標0(看作左邊看作左邊), 也可以標也可以標1(看作右看作右邊邊). 將從樹根到每一片樹葉的通路上標的

20、數(shù)字組成的字將從樹根到每一片樹葉的通路上標的數(shù)字組成的字符串記在樹葉處符串記在樹葉處, 所得的字符串構(gòu)成一個前綴碼所得的字符串構(gòu)成一個前綴碼.P209例如例如前綴碼前綴碼00, 11, 011, 010028實例實例例例2 在通信中在通信中,設八進制數(shù)字出現(xiàn)的頻率設八進制數(shù)字出現(xiàn)的頻率(%)如下如下: 0: 25, 1: 20, 2: 15, 3: 10, 4: 10, 5: 10, 6: 5, 7: 5采用采用2元前綴碼元前綴碼, 求傳輸數(shù)字最少的求傳輸數(shù)字最少的2元前綴碼元前綴碼 (稱作稱作最佳最佳前綴碼前綴碼), 并求傳輸并求傳輸100個按上述比例出現(xiàn)的八進制數(shù)字需個按上述比例出現(xiàn)的八進

21、制數(shù)字需要多少個二進制數(shù)字？若用等長的要多少個二進制數(shù)字？若用等長的 (長為長為3) 的碼字傳輸需的碼字傳輸需要多少個二進制數(shù)字要多少個二進制數(shù)字?解解 用用Huffman算法求以頻率算法求以頻率(乘以乘以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.29實例實例(續(xù)續(xù))編碼編碼:0-01 1-112-0013-1004-1015-00016-000007-00001傳傳100個按比例出現(xiàn)的八進制數(shù)字需個按比例出現(xiàn)的八進制數(shù)字需W(T)=285個二進制數(shù)個二進制數(shù)字字, 用等長碼用等長碼(長為長為3)需要用需要用 300個數(shù)字個數(shù)字.w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=2530根樹的周游及其應用根樹的周游及其應用對一棵根樹的每個頂點訪問一次且僅訪問一次稱作對根對一棵根樹的每個頂點訪問一次且僅訪問一次稱作對根樹的樹的行遍行遍或或周游周游 行遍行遍2元有序正則樹的方式：元有序正則樹的方式： 中序行遍法中序行遍法: 左子樹、樹根、右子樹左子樹、樹根、右子樹 前序行遍法前序行遍法:樹根、左子樹、右子樹樹根、左子樹、右子樹 后序行遍法后