離散數(shù)學第十六章

1、1,第十六章 樹,主要內(nèi)容無向樹及其性質(zhì)生成樹根樹及其應用,2,16.1 無向樹及其性質(zhì),定義16.1 (1) 無向樹——連通無回路的無向圖(2) 平凡樹——平凡圖(3) 森林——至少由兩個連通分支（每個都是樹）組成(4) 樹葉——1度頂點(5) 分支點——度數(shù)?2的頂點,3,樹的舉例,判斷圖G1、G2、G3是否為樹？,是,不是,有回路,不是,不連通,4,無向樹的等價定義,定理16.1 設(shè)G=是n階m條邊的無向圖，則下面

2、各命題是等價的：(1) G 是樹(2) G 中任意兩個頂點之間存在惟一的路徑.(3) G 中無回路且 m=n?1. (4) G 是連通的且 m=n?1.(5) G 是連通的且 G 中任何邊均為橋.(6) G 中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到惟一的一個含新邊的圈.,5,(3)?(4). 只需證明G連通. 用反證法. 否則G有s（s?2）個連通分支都是小樹. 于是有mi=ni?1, ，這

3、與m=n?1矛盾.,證明思路,(2)?(3). 若G中有回路，則回路上任意兩點之間的路徑不惟一. 對n用歸納法證明m=n?1. n=1正確. 設(shè)n?k時對，證n=k+1時也對：取G中邊e，G?e有且僅有兩個連通分支G1,G2(為什么?) . ni?k，由歸納假設(shè)得mi=ni?1, i=1,2. 于是，m=m1+m2+1=n1+n2?2+1=n?1.,,(1)?(2). 關(guān)鍵一步是, 若路徑不惟一必有回路.,6,(4

4、)?(5). 只需證明G 中每條邊都是橋. 為此只需證明命題 “G 是 n 階 m 條邊的無向連通圖，則 m?n?1”. 命題的證明: 對n歸納. ?e?E, G?e只有n?2條邊，由命題可知G?e不連通，故e為橋.,證明思路,(5)?(6). 由(5)易知G為樹，由(1)?(2)知，?u,v?V（u?v）, u到v有惟一路徑，加新邊(u,v)得惟一的一個圈.,(6)?(1). 只需證明G連通，這是顯然的.

5、,7,由上式解出x ? 2.,定理16.2 設(shè)T是n階非平凡的無向樹，則T 中至少有兩片樹葉.,無向樹的性質(zhì),證 設(shè) T 有 x 片樹葉，由握手定理及定理16.1可知，,8,例題,例1 已知無向樹T中有1個3度頂點，2個2度頂點，其余頂點全是樹葉，試求樹葉數(shù)，并畫出滿足要求的非同構(gòu)的無向樹.,解 解本題用樹的性質(zhì)m=n?1，握手定理. 設(shè)有x片樹葉，于是 n = 1+2+x = 3+x, 2m = 2

6、(n?1) = 2?(2+x) = 1?3+2?2+x解出x = 3，故T有3片樹葉.,T 的度數(shù)列應為 1, 1, 1, 2, 2, 3，易知3度頂點與1個2度頂點相鄰與和2個2度頂點均相鄰是非同構(gòu)的，因而有2棵非同構(gòu)的無向樹T1, T2，如圖所示.,9,例2 已知無向樹T有5片樹葉，2度與3度頂點各1個，其余頂點的度數(shù)均為4，求T的階數(shù)n，并畫出滿足要求的所有非同構(gòu)的無向樹.,例題,解 設(shè)T的階數(shù)為n, 則邊數(shù)為n?1

7、，4度頂點的個數(shù)為n?7. 由握手定理得 2m = 2(n?1) = 5?1+2?1+3?1+4(n?7)解出n = 8，4度頂點為1個.,10,T的度數(shù)列為1, 1, 1, 1, 1, 2, 3, 4，共有3棵非同構(gòu)的無向樹，如圖所示.,例題,11,不一定連通，也不一定不含回路，如圖所示,定義16.2 設(shè)G為無向圖(1) G的生成樹——T 是G 的生成子圖并且是樹(2) 生成樹T的樹枝——T 中

8、的邊(3) 生成樹T的弦——不在T 中的邊(4) 生成樹T的余樹 ——全體弦組成的集合的導出子圖,16.2 生成樹,12,生成樹舉例,求圖G的生成樹,圖T1和T2均為G的生成樹。,13,定理16.3 無向圖G具有生成樹當且僅當G連通.,生成樹存在條件,證 必要性顯然.充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞連通性）,14,最小生成樹,定義16.5 T是G=的生成樹(1) W(T)——T各邊權(quán)之和(2)

9、最小生成樹——G的所有生成樹中權(quán)最小的,求最小生成樹的一個算法避圈法（Kruskal）設(shè)G=，將G中非環(huán)邊按權(quán)從小到大排序：e1, e2, …, em.(1) 取e1在T中(2) 查e2，若e2與e1不構(gòu)成回路，取e2也在T 中，否則棄e2.(3) 再查e3,…, 直到得到生成樹為止.,15,避圈法求最小生成樹舉例,用避圈法求圖G的最小生成樹,16,解答,(1)選擇權(quán)值為1的邊(c,d);,,1,(2)選擇權(quán)值為2的邊(b,f

10、);,,2,(3)選擇權(quán)值為3的邊(b,c);,,3,(4)選擇權(quán)值為4的邊(a,b);,,4,(5)權(quán)值為5的邊(a,f),形成回路,避開,,權(quán)值為6的邊(a,c),形成回路,避開;,,權(quán)值為7的邊(d,f),形成回路,避開;,,(6)選擇權(quán)值為8的邊(f,e);,,8,加權(quán)長度＝1＋2＋3＋4＋8＝18,最小生成樹,17,求最小生成樹舉例,求圖G的最小生成樹,(1)選擇權(quán)值為3的邊(v1,v5);,,3,(2)選擇權(quán)值為4的邊(v1

11、,v4);,,4,(3)選擇權(quán)值為4的邊(v4,v5);,,形成回路,避開,(4)選擇權(quán)值為5的邊(v2,v5);,,5,(5)選擇權(quán)值為6的邊(v3,v5);,,6,加權(quán)長度為3+4+5+6＝18,最小生成樹,18,解答(2),(1)選擇權(quán)值為3的邊(v1,v5);,,3,(2)選擇權(quán)值為4的邊(v4,v5);,,4,(3)選擇權(quán)值為4的邊(v1,v4);,,形成回路,避開,(4)選擇權(quán)值為5的邊(v2,v5);,,5,(5)選擇權(quán)值

12、為6的邊(v3,v5);,,6,加權(quán)長度為3+4+5+6＝18,最小生成樹不唯一，最小生成樹的加權(quán)長度相同,19,16.3 根樹及其應用,定義16.6 T是有向樹（基圖為無向樹）(1) T 為根樹——T 中一個頂點入度為0，其余的入度均為1.(2) 樹根——入度為0的頂點(3) 樹葉——入度為1，出度為0的頂點(4) 內(nèi)點——入度為1，出度不為0的頂點(5) 分支點——樹根與內(nèi)點的總稱(6) 頂點v的層數(shù)——從樹根到v的

13、通路長度(7) 樹高——T 中層數(shù)最大頂點的層數(shù)(8) 平凡根樹——平凡圖,20,根樹實例,根樹的畫法——樹根放上方，省去所有有向邊上的箭頭,根樹舉例,樹葉:,樹根,樹的高度：3,v4,v5,v6,v7,v8,v10,v11,v12,分枝結(jié)點：,v0,v1,v2,v3,v9,根結(jié)點是分枝結(jié)點,22,家族樹與根子樹,定義16.7 T 為非平凡根樹(1) 祖先與后代(2) 父親與兒子(3) 兄弟定義16.8 設(shè)v為根樹T中

14、任意一頂點，稱v及其后代的導出子圖為以v為根的根子樹.,有序樹舉例,不考慮同一層上結(jié)點的次序，是同一棵樹兩棵不同的有序樹。,大,小,(1) T 為有序根樹——同層上頂點標定次序的根樹,24,根樹的分類,(2) 分類 ① r 叉樹——每個分支點至多有r 個兒子 ② r 叉有序樹——r 樹是有序的 ③ r 叉正則樹——每個分支點恰有r 個兒子 ④ r 叉正則有序樹 ⑤ r 叉完全正則樹—

15、—樹葉層數(shù)相同的r叉正則樹 ⑥ r 叉完全正則有序樹,25,定義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)樹的算法—— Huffman算法給定實數(shù)w1,

16、 w2, …, wt，且w1?w2?…?wt. (1) 連接權(quán)為w1, w2的兩片樹葉，得一個分支點，其權(quán)為w1+w2.(2) 在w1+w2, w3, …, wt 中選出兩個最小的權(quán)，連接它們對應的頂點(不一定是樹葉)，得新分支點及所帶的權(quán). (3) 重復(2)，直到形成 t?1個分支點，t片樹葉為止.,26,例 5 求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹. 解題過程由圖9給出，W(T)=38,求最優(yōu)二叉樹舉

17、例,設(shè)有一組權(quán)2，3，5，7，11，13，17，19，20，求相應的最優(yōu)樹。,解答,,,23571113171920,5,571113171920,解答（續(xù)）,,,5 5 71113171920,10,71113171920,解答（續(xù)）,,,171113171920,24,17 17 1920,解答（續(xù)）,,,17 24171920,34

18、,241920,解答（續(xù)）,,,24341920,39,2434,解答（續(xù)）,,,2434 39,58,39,解答（續(xù)）,,,58 39,97,W(T)=6(2+3)+5*5+4*7+3(11+13+17)+2(19+20)=264,35,最佳前綴碼,定義16.10 設(shè)?1, ?2, …, ?n-1, ?n是長度為 n 的符號串(1) 前綴——?1, ?1?2, …, ?1?2…?n?1

19、(2) 前綴碼——{?1, ?2, …, ?m}中任何兩個元素互不為前綴(3) 二元前綴碼——?i (i=1, 2, …, m) 中只出現(xiàn)兩個符號，如0與1.,如何產(chǎn)生二元前綴碼？定理16.6 一棵2叉樹產(chǎn)生一個二元前綴碼.推論 一棵正則2叉樹產(chǎn)生惟一的前綴碼（按左子樹標0，右子樹標1）,36,圖所示二叉樹產(chǎn)生的前綴碼為 { 00, 10, 11, 011, 0100, 0101 }

20、,37,用Huffman算法產(chǎn)生最佳前綴碼,例6 在通信中，八進制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%求傳輸它們的最佳前綴碼，并求傳輸10n（n?2）個按上述比例出現(xiàn)的八進制數(shù)字需要多少個二進制數(shù)字？若用等長的（長為3）的碼字傳輸需要多少個二

21、進制數(shù)字？,38,解 用100個八進制數(shù)字中各數(shù)字出現(xiàn)的個數(shù)，即以100乘各頻率為權(quán)，并將各權(quán)由小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 用此權(quán)產(chǎn)生的最優(yōu)樹如圖所示.,求最佳前綴碼,01-----0 11-----1 001-----2 100-----3 101-----4 0001---

22、--500000-----6 00001-----7,W(T)=285，傳10n(n?2)個用二進制數(shù)字需2.85?10n個， 用等長碼需3?10n個數(shù)字.,39,波蘭符號法與逆波蘭符號法,行遍或周游根樹T——對T的每個頂點訪問且僅訪問一次. 對2叉有序正則樹的周游方式：① 中序行遍法——次序為：左子樹、根、右子樹② 前序行遍法——次序為：根、左子樹、右子樹③ 后序行遍法——次序為：左子樹、右子樹、根,對圖所

23、示根樹按中序、前序、后序行遍法訪問結(jié)果分別為： b a (f d g) c e， a b (c (d f g) e)， b ((f g d) e c) a,40,用2叉有序正則樹存放算式,存放規(guī)則最高層次運算放在樹根后依次將運算符放在根子樹的根上數(shù)放在樹葉上規(guī)定：被除數(shù)、被減數(shù)放在左子樹樹葉上,算式 ((b+(c+d))?a)?((e?f)?(g+h)?(i?j))存放在圖所示2叉樹上.

24、,41,波蘭符號法,波蘭符號法按前序行遍法訪問存放算式的2叉有序正則樹，其結(jié)果不加括號，規(guī)定每個運算符號與其后面緊鄰兩個數(shù)進行運算，運算結(jié)果正確. 稱此算法為波蘭符號法或前綴符號法. 對上圖的訪問結(jié)果為 ? ? ? b + c d a ? ? e f ? + g h ? i j 逆波蘭符號法按后序行遍法訪問，規(guī)定每個運算符與前面緊鄰兩數(shù)運算，稱為逆波蘭符號法或后綴符號法. 對

25、上圖的訪問結(jié)果為 b c d + + a ? e f ? g h + i j ? ? ? ?,42,第十六章 習題課,主要內(nèi)容無向樹及其性質(zhì)生成樹、最小生成樹、基本回路系統(tǒng)、基本割集系統(tǒng)根樹及其分類、最優(yōu)樹、最佳前綴碼、波蘭符號法、逆波蘭符號法基本要求深刻理解無向樹的定義及性質(zhì)熟練地求解無向樹準確地求出給定帶權(quán)連通圖的最小生成樹深刻理解基本回路、基本割集的概念，并會計算理解根樹

26、及其分類等概念會畫n階（n較?。┓峭瑯?gòu)的無向樹及根樹（1?n?6）熟練掌握求最優(yōu)樹及最佳前綴碼的方法掌握波蘭符號法與逆波蘭符號法,43,（2）,（3）,從而解出,練習1,1. 無向樹 T 有ni個i 度頂點，i=2, 3, …,k，其余頂點全是樹葉，求T 的樹葉數(shù).,解 用樹的性質(zhì)：邊數(shù) m=n?1（n為階數(shù)），及握手定理. (1),44,2．設(shè)n階非平凡的無向樹T中，?(T) ? k，k ? 1. 證明T至少 有k片樹

27、葉.,證 反證法. 否則，T至多有s片樹葉，s < k，下面利用握手定理及樹的性質(zhì)m = n?1推出矛盾. 由于?(T) ? k，故存在v0，d(v0) ? k. 于是，,,由此解出s ? k，這與s < k矛盾. 證本題的方法有多種，請用分支點都是割點來證明.,練習2,45,3．設(shè)G為n 階無向簡單圖，n?5，證明G 或 中必含圈.,本題的方法很多，證明中用：G與 邊數(shù)之和為Kn的邊數(shù)

28、 ，以及樹的性質(zhì)：m = n?1.,方法一. 反證法. 否則G與 的各連通分支都是樹. 設(shè)G與 的連通分支分別為G1, G2, …, Gs和G?1, G?2, …, G?s?. 令ni, mi與 n?j, m?j 分別為Gi, G?j的頂點數(shù)和邊數(shù). 于是,得 n2?5n+4 ? 0， 解出 1 ? n ? 4, 矛盾于n ? 5.,練習3,46,方法二. 在G與 中存在一個，比如說G，它

29、的邊數(shù)用反證法證明G中必含圈. 比方法一簡單.,方法三. 不妨設(shè)G的邊數(shù)由于n?5，得m?n. 再用反證法證明之，更簡單.,練習3,47,4．畫出基圖為圖所示無向樹的所有非同構(gòu)的根樹,練習4,以a, b, c 或d為根的根樹同構(gòu)，選a為根，則根樹如圖(1); 以 e 與 g 為根的根樹同構(gòu)，取 g為根，則根樹如圖(2)； 以 f 為根，如圖(3) 所示.,(1) (

30、2) (3),48,5．設(shè)T 是正則2叉樹，T 有t 片樹葉，證明T的階數(shù) n=2t?1.,方法一. 利用正則2叉樹的定義及樹的性質(zhì)直接證明.(1) n = t+i (i為分支點數(shù))(2) n = m+1 （m為T的邊數(shù)）(3) m = 2i （正則2叉樹定義）由(2)、(3)得 ，代入（1）得n = 2t?1.,練習5,方法二.