離散數(shù)學(xué)第十六章課件

1、1,第十六章 樹,主要內(nèi)容無向樹及其性質(zhì)生成樹根樹及其應(yīng)用,2,16.1 無向樹及其性質(zhì),定義16.1 (1) 無向樹——連通無回路的無向圖(2) 平凡樹——平凡圖(3) 森林——至少由兩個(gè)連通分支（每個(gè)都是樹）組成的無向圖(4) 樹葉——1度頂點(diǎn)(5) 分支點(diǎn)——度數(shù)?2的頂點(diǎn),3,無向樹的等價(jià)定義,定理16.1 設(shè)G=是n階m條邊的無向圖，則下面各命題是等價(jià)的：(1) G 是樹(2) G 中任意兩個(gè)頂點(diǎn)之間存在

2、惟一的路徑.(3) G 中無回路且 m=n?1. (4) G 是連通的且 m=n?1.(5) G 是連通的且 G 中任何邊均為橋.(6) G 中沒有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到惟一的一個(gè)含新邊的圈.,4,由上式解出x ? 2.,定理16.2 設(shè)T是n階非平凡的無向樹，則T 中至少有兩片樹葉.,無向樹的性質(zhì),證 設(shè) T 有 x 片樹葉，由握手定理及定理16.1可知，,5,例題,例1 已知無向樹

3、T中有1個(gè)3度頂點(diǎn)，2個(gè)2度頂點(diǎn)，其余頂點(diǎn)全是樹葉，試求樹葉數(shù).,解 解本題用樹的性質(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片樹葉.,6,例2 已知無向樹T有5片樹葉，2度與3度頂點(diǎn)各1個(gè)，其余頂點(diǎn)的度數(shù)均為4，求T的階數(shù)n,例題,解 設(shè)T的階數(shù)為n, 則邊數(shù)為n?1，4

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è).,7,子圖,定義14.8 G=, G?=(1) G??G —— G?為G的子圖，G為G?的母圖(2) 若G??G且V?=V，則稱G?為G的生成子圖(3) 若V??V或E??E，稱G?為G的真子圖(4) V?（V??V且V???）的導(dǎo)出子圖，記作G[V?](5)

5、 E?（E??E且E???）的導(dǎo)出子圖，記作G[E?]　在圖中，設(shè)G為(1)中圖所表示，取V1={a，b，c}，則V1的導(dǎo)出子圖G[V1]為(2)中圖所示。取E1={e1，e3}，則E1的導(dǎo)出子圖G[E1]為(3)中圖所示。,8,不一定連通，也不一定不含回路，如圖所示,定義16.2 設(shè)G為無向圖(1) G的樹——T 是G 的子圖并且T是樹(2) G的生成樹——T 是G 的生成子圖并且T是樹(3) 生成樹T的樹枝——G 的在T

6、中的邊(4) 生成樹T的弦——G 的不在T 中的邊(5) 生成樹T的余樹 ——T的所有弦的導(dǎo)出子圖,16.2 生成樹,9,推論2 的邊數(shù)為m?n+1.,推論3 為G的生成樹T的余樹，C為G中任意一個(gè)圈，則C與 一定有公共邊.證 否則，C中的邊全在T中，這與T為樹矛盾.,定理16.3 無向圖G具有生成樹當(dāng)且僅當(dāng)G連通.,生成樹存在條件,推論1 G為n階m條邊的無向連通圖，則m?n?1.,證 必要

7、性顯然.充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞連通性）,由定理16.3和樹的邊數(shù)等于頂點(diǎn)數(shù)減1可立即得到下述推論。,10,基本回路系統(tǒng),定理16.4 設(shè)T為G的生成樹，e為T的任意一條弦，則T?e中含一個(gè)只有一條弦其余邊均為T的樹枝的圈. 不同的弦對(duì)應(yīng)的圈也不同. 證 設(shè)e=(u,v)，在T中u到v有惟一路徑?，則??e為所求的圈.,定義16.3 設(shè)T是n階m條邊的無向連通圖G的一棵生成樹，設(shè)e?1, e?2

8、, …, e?m?n+1為T 的弦. 設(shè)Cr為T 添加弦e?r 產(chǎn)生的只含弦e?r、其余邊均為樹枝的圈. 稱Cr為G的對(duì)應(yīng)樹T 的弦e?r的基本回路或基本圈，r=1, 2, …, m?n+1. 并稱{C1, C2, …,Cm?n+1}為G對(duì)應(yīng)T 的基本回路系統(tǒng)，稱m?n+1為G的圈秩，記作 ?(G).,求基本回路的算法：設(shè)弦e=(u,v)，先求T中u到v的路徑?uv，再并上弦e，即得對(duì)應(yīng)e的基本回路.,11,Ca=aef,Cb=b

9、de,Cc=cdf,此圖的圈秩為3，基本回路系統(tǒng)為：{Ca, Cb, Cc},基本回路系統(tǒng),在下圖中，對(duì)應(yīng)生成樹的弦a，b，c的基本回路為：,12,基本割集的存在,定理16.5 設(shè)T是連通圖G的一棵生成樹，e為T的樹枝，則G中存在只含樹枝e，其余邊都是弦的割集，且不同的樹枝對(duì)應(yīng)的割集也不同.證 由定理16.1可知，e是T的橋，因而T?e有兩個(gè)連通分支T1和T2，令 Se={e | e?E(G)且 e 的兩個(gè)端點(diǎn)

10、分別屬于V(T1)和V(T2)}，由構(gòu)造顯然可知Se為G的割集，e?Se且Se中除e外都是弦，所以Se為所求. 顯然不同的樹枝對(duì)應(yīng)的割集不同.,13,定義16.4 設(shè)T是n階連通圖G的一棵生成樹，e?1, e?2, …, e?n?1為T 的樹枝，Si是G的只含樹枝e?i的割集，則稱Si為G的對(duì)應(yīng)于生成樹T由樹枝e?i生成的基本割集，i=1, 2, …, n?1. 并稱{S1,S2, …, Sn?1}為G 對(duì)應(yīng)T 的基本割集系

11、統(tǒng)，稱n?1為G的割集秩，記作?(G).,基本割集與基本割集系統(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)的基本割集.,14,Sa={a,f,g},Sb={b,g,h},Sd={d,h,i},Sc={c,f,h},Se={e,f,i},基本割集系統(tǒng)為：{Sa , Sb , Sc , Sd

12、 , Se}割集秩為5.,基本割集與基本割集系統(tǒng),在下圖中，對(duì)應(yīng)樹枝a，b，c，d，e的基本割集分別為：,15,解 弦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

13、g}, Sd={d, g}, S基={Sa, Sb, Sc, Sd}.,例 下圖實(shí)線邊所示為生成樹，求基本回路系統(tǒng)與基本割集系統(tǒng),實(shí)例,16,最小生成樹,定義16.5 T是無向連通帶權(quán)圖G=的生成樹(1) T的權(quán)W(T)——T的各邊權(quán)之和(2) G的最小生成樹——G的所有生成樹中權(quán)最小的生成樹,求最小生成樹的一個(gè)算法避圈法（Kruskal）設(shè)G=，將G中非環(huán)邊按權(quán)從小到大排序：e1, e2, …, em.(1) 取e1在

14、T中(2) 查e2，若e2與e1不構(gòu)成回路，取e2也在T 中，否則棄去e2.(3) 再查e3,…, 直到得到生成樹為止.,17,例4 求圖的一棵最小生成樹.,所求最小生成樹如圖所示，W(T)=38.,實(shí)例,18,16.3 根樹及其應(yīng)用,定義16.6 有向樹T ——基圖為無向樹的有向圖。(1) T 為根樹——T 中一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)入度均為1的有向樹.(2) 樹根——入度為0的頂點(diǎn)(3) 樹葉——入度為1，出

15、度為0的頂點(diǎn)(4) 內(nèi)點(diǎn)——入度為1，出度不為0的頂點(diǎn)(5) 分支點(diǎn)——樹根與內(nèi)點(diǎn)的總稱(6) 頂點(diǎn)v的層數(shù)——從樹根到任意頂點(diǎn)v的路徑的長度（即路徑中的邊數(shù)）(7) 樹高——T 中所有頂點(diǎn)的最大層數(shù)(8) 平凡根樹——平凡圖,19,根樹的畫法:樹根放上方,省去所有有向邊上的箭頭如右圖所示 a是樹根 b,e,f,h,i是樹葉 c,d,g是內(nèi)點(diǎn) a,c,d,g是分支點(diǎn) a為0層;1層有b

16、,c; 2層有d,e,f; 3層有g(shù),h; 4層有i. 樹高為4,,根樹實(shí)例,20,家族樹與根子樹,定義16.7 設(shè)T 為一顆非平凡的根樹(1) 祖先與后代——?vi ，vj ∈V(T)， vi ≠vj ，若vi 可達(dá)vj ，則稱vi 為vj的祖先 ， vj為vi的后代 。(2) 父親與兒子——?vi ，vj ∈V(T)， vi ≠vj ，若vi 鄰接到vj（即 ∈E(T) ） ，則稱vi 為vj的

17、父親 ， vj為vi的兒子 。(3) 兄弟——?vj ，vk∈V(T)， vj ≠vk ，若vj ，vk的父親相同 ，則稱vj與vk是兄弟 。定義16.8 設(shè)v為根樹T中的任意一個(gè)頂點(diǎn)，稱v及其后代的導(dǎo)出子圖Tv為T的以v為根的根子樹.,常將根樹看成家族樹，家族中成員之間的關(guān)系由下面的定義給出：,21,根樹的分類,(1) T 為有序根樹——同層上的頂點(diǎn)都標(biāo)定次序的根樹(2) 根據(jù)根樹T中的每個(gè)分支點(diǎn)兒子數(shù)以及是否有序，

18、可以將根樹分為下列各類： ① r 叉樹——每個(gè)分支點(diǎn)至多有r 個(gè)兒子 ② r 叉有序樹——r叉樹是有序的 ③ r 叉正則樹——每個(gè)分支點(diǎn)恰有r 個(gè)兒子 ④ r 叉正則有序樹——又若r 叉正則樹是有序的 ⑤ r 叉完全正則樹——樹葉層數(shù)相同的r叉正則樹 ⑥ r 叉完全正則有序樹——又若r 叉完全正則樹是有序的,2叉正則有序樹的每個(gè)分支點(diǎn)的兩個(gè)兒子導(dǎo)出的根子樹分別稱為該分支點(diǎn)的左子

19、樹和右子樹。 在所有的r叉樹中，最常用的是2叉樹。下面介紹2叉樹的應(yīng)用。,22,定義16.9 設(shè)2叉樹T 有t片樹葉v1, v2, …, vt，權(quán)分別為w1, w2, …, wt，稱 為T 的權(quán)，其中l(wèi)(vi)是vi 的層數(shù). 在所有有t片樹葉，帶權(quán)w1, w2, …, wt 的2叉樹中，權(quán)最小的2叉樹稱為最優(yōu)2叉樹.,最優(yōu)二叉樹,求最優(yōu)2叉樹的算法—— Huffman算法

20、給定實(shí)數(shù)w1, w2, …, wt ，且w1?w2?…?wt . （1）作t片樹葉, 分別以w1, w2, …, wt為權(quán).（2）在所有入度為0的頂點(diǎn)(不一定是樹葉)中選出兩個(gè)權(quán)最小的頂點(diǎn), 添加一個(gè)新分支點(diǎn), 以這2個(gè)頂點(diǎn)為兒子, 其權(quán)等于這2個(gè)兒子的權(quán)之和.（3）重復(fù)（2）, 直到只有1個(gè)入度為0 的頂點(diǎn)為止. W(T)等于所有分支點(diǎn)的權(quán)之和,23,例 5 求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹. 解題過程

21、由下圖給出，W(T)=38,最優(yōu)二叉樹的算法——Huffman算法,24,最佳前綴碼,定義16.10 設(shè)?1?2…?n-1?n是長度為 n 的符號(hào)串(1) 前綴——該符號(hào)串的子串 ?1, ?1?2, …, ?1?2…?n?1 (2) 前綴碼——符號(hào)串集合A={?1, ?2, …, ?m}中的任意兩個(gè)符號(hào)串都互不為前綴(3) 二元前綴碼——?i (i=1, 2, …, m) 中只出現(xiàn)兩個(gè)符號(hào)，如0與1.,如何產(chǎn)生二元前綴碼？定

22、理16.6 一棵2叉樹產(chǎn)生一個(gè)二元前綴碼.推論 一棵正則2叉樹產(chǎn)生惟一的一個(gè)二元前綴碼（按左子樹標(biāo)0，右子樹標(biāo)1）,25,一棵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è)前綴碼，如右圖所示：,,樹的編碼：,最優(yōu)2進(jìn)制編碼：使

23、信息傳遞的2進(jìn)制數(shù)最短由最優(yōu)2叉樹產(chǎn)生的前綴碼為最佳前綴碼。用最佳前綴碼傳輸?shù)亩M(jìn)制位數(shù)最省。,最佳前綴碼,26,圖所示二叉樹產(chǎn)生的前綴碼為 { 00, 10, 11, 011, 0100, 0101 },二叉樹產(chǎn)生的前綴碼,27,用Huffman算法產(chǎn)生最佳前綴碼,例16.7 在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15%

24、 3：10% 4：10% 5：10% 6：5% 7：5%求傳輸它們的最佳前綴碼，并求傳輸10n（n?2）個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？若用等長的（長為3）的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字？,28,解 用100個(gè)八進(jìn)制數(shù)字中各數(shù)字出現(xiàn)的個(gè)數(shù)，即以100乘各頻率為權(quán)，并將各權(quán)由小到大排列，得w1=5, w2=5, w3=10, w4=10,

25、w5=10, w6=15, w7=20, w8=25。用Huffman算法求以頻率(乘以100)為權(quán)的最優(yōu)2叉樹。用此權(quán)產(chǎn)生的最優(yōu)2叉樹如下圖所示：,求最佳前綴碼,傳100個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字的個(gè)數(shù)為 W(T)=285，傳10n(n?2)個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字需要2.85?10n個(gè)二進(jìn)制數(shù)字，用等長碼(長為3)傳輸需3?10n個(gè)二進(jìn)制數(shù)字.,01-----0 11-----1 001--

26、---2 100-----3 101-----4 0001-----500000-----6 00001-----7,,它產(chǎn)生的最優(yōu)前綴碼,29,波蘭符號(hào)法與逆波蘭符號(hào)法,行遍或周游根樹T——對(duì)根樹T的每個(gè)頂點(diǎn)訪問且僅訪問一次. 對(duì)于2叉有序正則樹有以下三種周游方式：① 中序行遍法——訪問的次序?yàn)椋鹤笞訕?、根、右子樹?前序行遍法——訪問的次序?yàn)椋焊?、左子樹、右子樹?后序行遍法——

27、訪問的次序?yàn)椋鹤笞訕洹⒂易訕?、?對(duì)如右圖所示的根樹T（2叉有序正則樹）按中序、前序、后序行遍的周游結(jié)果分別為： b a (f d g) c e， a b (c (d f g) e)， b ((f g d) e c) a,30,用2叉有序正則樹存放算式,存放規(guī)則最高層次運(yùn)算放在樹根然后依次將運(yùn)算符放在根子樹的根上數(shù)放在樹葉上規(guī)定：被除數(shù)、被減數(shù)放在左子樹樹葉上,算式((b+(c+d))?a)

28、?((e?f)?(g+h)?(i?j))存放在如上圖所示的2叉有序正則樹上.,31,波蘭符號(hào)法,波蘭符號(hào)法按前序行遍法訪問存放算式的2叉有序正則樹，其結(jié)果不加括號(hào)，規(guī)定從右到左每個(gè)運(yùn)算符對(duì)它后面緊鄰的兩個(gè)數(shù)進(jìn)行運(yùn)算。在這種算法中，由于運(yùn)算符在它的兩個(gè)運(yùn)算對(duì)象之前，所以稱此種算法為前綴符號(hào)法或波蘭符號(hào)法. 對(duì)下圖的訪問結(jié)果為 ? ? ? b + c d a ? ? e f ? + g h

29、? i j 逆波蘭符號(hào)法按后序行遍法訪問存放算式的2叉有序正則樹，其結(jié)果不加括號(hào)，規(guī)定從左到右每個(gè)運(yùn)算符對(duì)它前面緊鄰的兩個(gè)數(shù)進(jìn)行運(yùn)算。在這種算法中，由于運(yùn)算符在它的兩個(gè)運(yùn)算對(duì)象之后，所以稱此種算法為后綴符號(hào)法或逆波蘭符號(hào)法. 對(duì)上圖的訪問結(jié)果為 b c d + + a ? e f ? g h + i j ? ? ? ?,32,重點(diǎn),主要內(nèi)容無向樹及其性質(zhì)生成樹、最小生成樹、基本回

30、路系統(tǒng)、基本割集系統(tǒng)根樹及其分類、最優(yōu)樹、二叉樹產(chǎn)生的前綴碼、最佳前綴碼、波蘭符號(hào)法、逆波蘭符號(hào)法基本要求深刻理解無向樹的定義及性質(zhì)熟練地求解無向樹準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹深刻理解基本回路、基本割集的概念，并會(huì)計(jì)算理解根樹及其分類等概念熟練掌握求最優(yōu)樹及最佳前綴碼的方法掌握波蘭符號(hào)法與逆波蘭符號(hào)法,33,第十六章 習(xí)題課,主要內(nèi)容無向樹及其性質(zhì)生成樹、最小生成樹、基本回路系統(tǒng)、基本割集系統(tǒng)根樹及其分類

31、、最優(yōu)樹、最佳前綴碼、波蘭符號(hào)法、逆波蘭符號(hào)法基本要求深刻理解無向樹的定義及性質(zhì)熟練地求解無向樹準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹深刻理解基本回路、基本割集的概念，并會(huì)計(jì)算理解根樹及其分類等概念會(huì)畫n階（n較?。┓峭瑯?gòu)的無向樹及根樹（1?n?6）熟練掌握求最優(yōu)樹及最佳前綴碼的方法掌握波蘭符號(hào)法與逆波蘭符號(hào)法,34,（2）,（3）,從而解出,練習(xí)1,1. 無向樹 T 有ni個(gè)i 度頂點(diǎn)，i=2, 3, …,k，其余頂點(diǎn)

32、全是樹葉，求T 的樹葉數(shù).,解 用樹的性質(zhì)：邊數(shù) m=n?1（n為階數(shù)），及握手定理. (1),35,2．設(shè)n階非平凡的無向樹T中，?(T) ? k，k ? 1. 證明T至少 有k片樹葉.,證 反證法. 否則，T至多有s片樹葉，s < k，下面利用握手定理及樹的性質(zhì)m = n?1推出矛盾. 由于?(T) ? k，故存在v0，d(v0) ? k. 于是，,,由此解出s ? k，這與s < k矛盾. 證本

33、題的方法有多種，請(qǐng)用分支點(diǎn)都是割點(diǎn)來證明.,練習(xí)2,36,3．設(shè)G為n 階無向簡單圖，n?5，證明G 或 中必含圈.,本題的方法很多，證明中用：G與 邊數(shù)之和為Kn的邊數(shù) ，以及樹的性質(zhì)：m = n?1.,方法一. 反證法. 否則G與 的各連通分支都是樹. 設(shè)G與 的連通分支分別為G1, G2, …, Gs和G?1, G?2, …, G?s?. 令ni, mi與 n?j, m?j

34、分別為Gi, G?j的頂點(diǎn)數(shù)和邊數(shù). 于是,得 n2?5n+4 ? 0， 解出 1 ? n ? 4, 矛盾于n ? 5.,練習(xí)3,37,方法二. 在G與 中存在一個(gè)，比如說G，它的邊數(shù)用反證法證明G中必含圈. 比方法一簡單.,方法三. 不妨設(shè)G的邊數(shù)由于n?5，得m?n. 再用反證法證明之，更簡單.,練習(xí)3,38,4．畫出基圖為圖所示無向樹的所有非同構(gòu)的根樹,練習(xí)4,以a, b, c 或d為根的根樹同構(gòu)

35、，選a為根，則根樹如圖(1); 以 e 與 g 為根的根樹同構(gòu)，取 g為根，則根樹如圖(2)； 以 f 為根，如圖(3) 所示.,(1) (2) (3),39,5．設(shè)T 是正則2叉樹，T 有t 片樹葉，證明T的階數(shù) n=2t?1.,方法一. 利用正則2叉樹的定義及樹的性質(zhì)直接證明.(1) n = t+i (i為分支點(diǎn)數(shù))