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

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

2、各命題是等價(jià)的：(1) G 是樹(shù)(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,(3)?(4). 只需證明G連通. 用反證法. 否則G有s（s?2）個(gè)連通分支都是小樹(shù). 于是有mi=ni?1, ，這

3、與m=n?1矛盾.,證明思路,(2)?(3). 若G中有回路，則回路上任意兩點(diǎn)之間的路徑不惟一. 對(duì)n用歸納法證明m=n?1. n=1正確. 設(shè)n?k時(shí)對(duì)，證n=k+1時(shí)也對(duì)：取G中邊e，G?e有且僅有兩個(gè)連通分支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 條邊的無(wú)向連通圖，則 m?n?1”. 命題的證明: 對(duì)n歸納. ?e?E, G?e只有n?2條邊，由命題可知G?e不連通，故e為橋.,證明思路,(5)?(6). 由(5)易知G為樹(shù)，由(1)?(2)知，?u,v?V（u?v）, u到v有惟一路徑，加新邊(u,v)得惟一的一個(gè)圈.,(6)?(1). 只需證明G連通，這是顯然的.

5、,7,由上式解出x ? 2.,定理16.2 設(shè)T是n階非平凡的無(wú)向樹(shù)，則T 中至少有兩片樹(shù)葉.,無(wú)向樹(shù)的性質(zhì),證 設(shè) T 有 x 片樹(shù)葉，由握手定理及定理16.1可知，,8,例題,例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

6、(n?1) = 2?(2+x) = 1?3+2?2+x解出x = 3，故T有3片樹(shù)葉.,T 的度數(shù)列應(yīng)為 1, 1, 1, 2, 2, 3，易知3度頂點(diǎn)與1個(gè)2度頂點(diǎn)相鄰與和2個(gè)2度頂點(diǎn)均相鄰是非同構(gòu)的，因而有2棵非同構(gòu)的無(wú)向樹(shù)T1, T2，如圖所示.,9,例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

7、，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è).,10,T的度數(shù)列為1, 1, 1, 1, 1, 2, 3, 4，共有3棵非同構(gòu)的無(wú)向樹(shù)，如圖所示.,例題,11,不一定連通，也不一定不含回路，如圖所示,定義16.2 設(shè)G為無(wú)向圖(1) G的生成樹(shù)——T 是G 的生成子圖并且是樹(shù)(2) 生成樹(shù)T的樹(shù)枝——T 中

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

9、最小生成樹(shù)——G的所有生成樹(shù)中權(quán)最小的,求最小生成樹(shù)的一個(gè)算法避圈法（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,…, 直到得到生成樹(shù)為止.,15,避圈法求最小生成樹(shù)舉例,用避圈法求圖G的最小生成樹(shù),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),形成回路,避開(kāi),,權(quán)值為6的邊(a,c),形成回路,避開(kāi);,,權(quán)值為7的邊(d,f),形成回路,避開(kāi);,,(6)選擇權(quán)值為8的邊(f,e);,,8,加權(quán)長(zhǎng)度＝1＋2＋3＋4＋8＝18,最小生成樹(shù),17,求最小生成樹(shù)舉例,求圖G的最小生成樹(shù),(1)選擇權(quán)值為3的邊(v1,v5);,,3,(2)選擇權(quán)值為4的邊(v1

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

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

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

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

15、—樹(shù)葉層數(shù)相同的r叉正則樹(shù) ⑥ r 叉完全正則有序樹(shù),25,定義16.9 設(shè)2叉樹(shù)T 有t片樹(shù)葉v1, v2, …, vt，權(quán)分別為w1, w2, …, wt，稱 為T 的權(quán)，其中l(wèi)(vi)是vi 的層數(shù). 在所有有t片樹(shù)葉，帶權(quán)w1, w2, …, wt 的2叉樹(shù)中，權(quán)最小的2叉樹(shù)稱為最優(yōu)2叉樹(shù).,最優(yōu)二叉樹(shù),求最優(yōu)樹(shù)的算法—— Huffman算法給定實(shí)數(shù)w1,

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

17、例,設(shè)有一組權(quán)2，3，5，7，11，13，17，19，20，求相應(yīng)的最優(yōu)樹(shù)。,解答,,,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是長(zhǎng)度為 n 的符號(hào)串(1) 前綴——?1, ?1?2, …, ?1?2…?n?1

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

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

21、進(jìn)制數(shù)字？,38,解 用100個(gè)八進(jìn)制數(shù)字中各數(shù)字出現(xiàn)的個(gè)數(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)樹(shù)如圖所示.,求最佳前綴碼,01-----0 11-----1 001-----2 100-----3 101-----4 0001---

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

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

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

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

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

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

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

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

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