高等數(shù)學(xué)-離散數(shù)學(xué)及其應(yīng)用-課件-第十章樹(shù)的介紹

1、1,第十章 樹(shù)的介紹,主要內(nèi)容無(wú)向樹(shù)及其性質(zhì)生成樹(shù)根樹(shù)及其應(yīng)用,10.1 無(wú)向樹(shù)及其性質(zhì),定義10.1 連通無(wú)回路的無(wú)向圖稱為無(wú)向樹(shù), 簡(jiǎn)稱樹(shù). 每個(gè)連通分支都是樹(shù)的無(wú)向圖稱為森林. 平凡圖稱為平凡樹(shù). 在無(wú)向樹(shù)中, 懸掛頂點(diǎn)稱為樹(shù)葉, 度數(shù)大于或等于2的頂點(diǎn)稱為分支點(diǎn)．例,f,f,f,星形樹(shù),3,無(wú)向樹(shù)的性質(zhì),定理10.1 設(shè)G=是n階m條邊的無(wú)向圖，則下面各命題是等價(jià)的：(1) G 是樹(shù)(2) G 中任意兩個(gè)頂

2、點(diǎn)之間存在惟一的路徑.(3) G 中無(wú)回路且 m=n?1. (4) G 是連通的且 m=n?1.(5) G 是連通的且 G 中任何邊均為橋.(6) G 中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈.,4,(3)?(4). 只需證明G連通. 用反證法. 否則G有s(s?2)個(gè)連通分支, 它們都是樹(shù). 于是, 有mi=ni?1,這與m=n?1矛盾.,證明,(2)?(3). 若G中有回路，則

3、回路上任意兩點(diǎn)之間的路徑不惟一. 對(duì)n用歸納法證明m=n?1. 當(dāng)n=1時(shí)成立. 設(shè)n?k時(shí)成立，證n=k+1時(shí)也成立：任取一條邊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). 若路徑不惟一, 必有回路.,5,(4)?(5). 只需證明G

4、中每條邊都是橋. 下述命題顯然成立: G 是 n 階 m 條邊的無(wú)向連通圖，則 m?n?1. ?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連通，這是顯然的.,解得 x ? 2.,定理10.2 設(shè)T是n階非平凡的無(wú)向樹(shù)，則T 中至

5、少有兩片樹(shù)葉.,無(wú)向樹(shù)的性質(zhì),證 設(shè) T 有 x 片樹(shù)葉，由握手定理及定理10.1可知，,例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è)有x片樹(shù)葉，n = 3+x. 2m = 2(n?1) = 2?(2+x) = 1?3+2?2+x解出x = 3，故T有3片樹(shù)葉.,7,例2 已知無(wú)向樹(shù)T有5片樹(shù)葉，2度與3度頂點(diǎn)各1個(gè)，其余頂

6、點(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è).,8,10.2 生成樹(shù),定義10.2 如果無(wú)向圖G的生成子圖T是樹(shù)，則稱T是G的生成樹(shù). 設(shè)T是G的生成樹(shù)，G的在T中的邊稱為T的樹(shù)枝，不在T中的邊為T的弦. 稱T的所有弦

7、的導(dǎo)出子圖為T的余樹(shù)，記作 . 例,9,定理10.3 無(wú)向圖G有生成樹(shù)當(dāng)且僅當(dāng)G連通.,生成樹(shù)存在條件,推論 G為n階m條邊的無(wú)向連通圖，則m?n?1.,證 必要性顯然. 證充分性．若G中無(wú)回路，則G為自己的生成樹(shù)．若G中含圈，任取一圈，隨意地刪除圈上的一條邊; 若仍有圈, 再任取一個(gè)圈并刪去這個(gè)圈上的一條邊，重復(fù)進(jìn)行, 直到最后無(wú)圈為止. 最后得到的圖無(wú)圈（當(dāng)然無(wú)回路）、連通且是G的生成子圖，因而是G的生成樹(shù)．

8、這個(gè)產(chǎn)生生成樹(shù)的方法稱為破圈法．,10,最小生成樹(shù),定義10.3 設(shè)無(wú)向連通帶權(quán)圖G=，T是G的一棵生成樹(shù)，T的各邊權(quán)之和稱為T的權(quán)，記作W(T)．G的所有生成樹(shù)中權(quán)最小的生成樹(shù)稱為G的最小生成樹(shù).,避圈法（Kruskal）輸入: 連通圖G=輸出: G的最小生成樹(shù)T 1. 將G中非環(huán)邊按權(quán)從小到大排列: W(e1)?W(e2)? …?W(em).2. 令T?{e1}, i?2.3. 若ei與T中的邊不構(gòu)成回路,

9、則令T?T?{ei}.4. 若|T|<n-1, 則令i?i+1, 轉(zhuǎn)3.,11,例4 求圖的一棵最小生成樹(shù).,W(T)=38,實(shí)例,12,16.3 根樹(shù)及其應(yīng)用,定義10.4 若有向圖的基圖是無(wú)向樹(shù), 則稱這個(gè)有向圖為有向樹(shù). 一個(gè)頂點(diǎn)的入度為0、其余頂點(diǎn)的入度為1的有向樹(shù)稱為根樹(shù)．入度為0的頂點(diǎn)稱為樹(shù)根，入度為1出度為0的頂點(diǎn)稱為樹(shù)葉，入度為1出度不為0的頂點(diǎn)稱為內(nèi)點(diǎn)，內(nèi)點(diǎn)和樹(shù)根統(tǒng)稱為分支點(diǎn)．從樹(shù)根到頂點(diǎn)v

10、的路徑的長(zhǎng)度(即, 路徑中的邊數(shù))稱為v的層數(shù). 所有頂點(diǎn)的最大層數(shù)稱為樹(shù)高．,根樹(shù)的畫(huà)法——樹(shù)根放上方，省去所有有向邊上的箭頭例,13,家族樹(shù)與根樹(shù)的分類,定義10.5 設(shè)T為一棵非平凡的根樹(shù), ?vi,vj?V(T), 若vi可達(dá)vj，則稱vi為vj的祖先, vj為vi的后代; 若vi鄰接到vj, 則稱vi為vj的父親, vj為vi的兒子. 若vj,vk的父親相同, 則稱vj與vk是兄弟． 將根樹(shù)T中層數(shù)相同

11、的頂點(diǎn)都標(biāo)定次序, 稱T為有序樹(shù)．根樹(shù)的分類： (1) 若T的每個(gè)分支點(diǎn)至多有r個(gè)兒子，則稱T為r叉樹(shù). (2) 若T的每個(gè)分支點(diǎn)都恰好有r個(gè)兒子, 則稱T為r叉正則樹(shù). (3) 若T是r叉正則樹(shù), 且所有樹(shù)葉的層數(shù)相同, 則稱T為r叉完全正則樹(shù). 有序的r叉樹(shù), r叉正則樹(shù), r叉完全正則樹(shù)分別稱作 r叉有序樹(shù), r叉正則有序樹(shù), r叉完全正則有序樹(shù)．,14,根子樹(shù)與最優(yōu)二叉樹(shù),定義10.6 設(shè)T

12、為一棵根樹(shù), ?v?V(T), 稱v及其后代的導(dǎo)出子圖Tv為以v為根的根子樹(shù)． 2叉正則有序樹(shù)的每個(gè)分支點(diǎn)的兩個(gè)兒子導(dǎo)出的根子樹(shù)分別稱為該分支點(diǎn)的左子樹(shù)和右子樹(shù)．定義10.7 設(shè)2叉樹(shù)T 有t片樹(shù)葉v1, v2, …, vt, 權(quán)分別為w1, w2,…, wt, 稱 為T 的權(quán), 其中l(wèi)i是vi 的層數(shù). 在所有有t片樹(shù)葉, 帶權(quán)w1, w2, …, wt 的2叉樹(shù)中, 權(quán)最小的2叉樹(shù)

13、稱為最優(yōu)2叉樹(shù).,15,Huffman算法,Huffman算法輸入: 實(shí)數(shù)w1, w2, …, wt輸出: 最優(yōu)二叉樹(shù)1. 作t片樹(shù)葉, 分別以w1, w2, …, wt為權(quán).2. 在所有入度為0的頂點(diǎn)(不一定是樹(shù)葉)中選出兩個(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)之和.,16,例 5 求權(quán)為2,

14、 2, 3, 3, 5的最優(yōu)樹(shù). 解,實(shí)例,W(T)=34,17,前綴碼,定義10.8 設(shè)?1?2…?n?1?n是長(zhǎng)為n的符號(hào)串, 稱其子串?1, ?1?2, …, ?1?2…?n為該符號(hào)串的前綴. 設(shè)A={?1,?2,…,?m}是一個(gè)符號(hào)串集合, 若A的任意兩個(gè)符號(hào)串都互不為前綴, 則稱A為前綴碼. 由0-1符號(hào)串構(gòu)成的前綴碼稱作二元前綴碼． 例 {1, 00, 011, 0101, 01001, 01000}為前綴

15、碼． {1, 00, 011, 0101, 0100, 01001, 01000}不是前綴碼．,18,用2叉樹(shù)產(chǎn)生二元前綴碼例,一棵正則2叉樹(shù)產(chǎn)生惟一的前綴碼（按左枝標(biāo)0，右枝標(biāo)1）,前綴碼的產(chǎn)生,19,最佳前綴碼,設(shè)符號(hào)Ai在傳輸中出現(xiàn)的頻率為pi, 二元前綴碼的長(zhǎng)為li, 1?i?t,傳輸m個(gè)符號(hào)需要m 個(gè)二進(jìn)制位. 最小的二元前綴碼稱作最佳前綴碼.最

16、佳前綴碼可用Huffman算法計(jì)算以頻率為權(quán)的最優(yōu)二叉樹(shù)產(chǎn)生.例6 設(shè)在通信中, 八進(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ù)

17、字？若用等長(zhǎng)的(長(zhǎng)為3)的碼字傳輸需要多少個(gè)二進(jìn)制數(shù)字？,20,解 傳輸100個(gè)八進(jìn)制數(shù)字中各數(shù)字出現(xiàn)的個(gè)數(shù), 即以100乘各頻率為: 25, 20, 15, 10, 10, 10, 5, 5, 以它們?yōu)闄?quán)構(gòu)造最優(yōu)二叉樹(shù).,實(shí)例,最佳前綴碼 01-----0 11-----1 001-----2 100-----3 101-----4 0001-----5

18、00000-----6 00001-----7,W(T)=285，傳輸10n(n?2)個(gè)八進(jìn)制數(shù)字, 用最佳前綴碼需2.85?10n位， 用等長(zhǎng)碼需3?10n位.,21,有序樹(shù)的行遍方式,行遍(周游)有序樹(shù)——對(duì)每個(gè)頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次. 對(duì)2叉有序正則樹(shù)的周游方式：① 中序行遍法. 訪問(wèn)次序?yàn)椋鹤笞訕?shù)、根、右子樹(shù)② 前序行遍法. 訪問(wèn)次序?yàn)椋焊?、左子?shù)、右子樹(shù)③ 后序行遍法. 訪問(wèn)次序?yàn)椋鹤笞訕?shù)、右子樹(shù)、根,例

19、 用中序, 前序, 后序行遍法訪問(wèn)的結(jié)果分別為： b a (f d g) c e， a b (c (d f g) e)， b ((f g d) e c) a,22,用2叉有序樹(shù)存放算式,用2叉有序樹(shù)表示含有2元運(yùn)算和1元運(yùn)算的算式: 每個(gè)分支點(diǎn)放一個(gè)運(yùn)算符, 其運(yùn)算對(duì)象是以它的兒子為樹(shù)根的子樹(shù)所表示的子算式. 規(guī)定運(yùn)算對(duì)象的排列順序, 如被除數(shù)、被減數(shù)放在左邊．所有的變量和常量都放在樹(shù)葉上.,

20、例 ((b+(c+d))?a)?((e?f)?(g+h)?(i?j))用中序行遍法訪問(wèn)還原算式,23,波蘭符號(hào)法,波蘭符號(hào)法(前綴符號(hào)法): 按前序行遍法訪問(wèn)存放算式的2叉有序樹(shù), 且不加括號(hào).運(yùn)算規(guī)則: 從右到左每個(gè)運(yùn)算符號(hào)對(duì)其后面緊鄰的兩個(gè)或一個(gè)對(duì)象進(jìn)行運(yùn)算.如對(duì)上頁(yè)的算式 ? ? ? b + c d a ? ? e f ? + g h ? i j 逆波蘭符號(hào)法(后綴符號(hào)法): 按后序行遍

21、法訪問(wèn),且不加括號(hào).運(yùn)算規(guī)則:從左到右每個(gè)運(yùn)算符對(duì)其前面緊鄰的兩個(gè)或一個(gè)對(duì)象進(jìn)行運(yùn)算.如對(duì)上頁(yè)的算式 b c d + + a ? e f ? g h + i j ? ? ? ?,24,第十章 習(xí)題課,主要內(nèi)容無(wú)向樹(shù)及其性質(zhì)生成樹(shù)、最小生成樹(shù)根樹(shù)及其分類、最優(yōu)二叉樹(shù)、最佳前綴碼、波蘭符號(hào)法、逆波蘭符號(hào)法基本要求深刻理解無(wú)向樹(shù)的定義及性質(zhì)熟練地求解無(wú)向樹(shù)準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹(shù)理解根樹(shù)及其

22、分類等概念熟練掌握求最優(yōu)二叉樹(shù)及最佳前綴碼的方法掌握波蘭符號(hào)法與逆波蘭符號(hào)法,25,練習(xí)1,1. 無(wú)向樹(shù) T 有ni個(gè)i 度頂點(diǎn)，i=2, 3, …,k，其余頂點(diǎn)全是樹(shù)葉，求T 的樹(shù)葉數(shù).,26,2．設(shè)n階非平凡的無(wú)向樹(shù)T中，?(T) ? k，k ? 1. 證明T至少 有k片樹(shù)葉.,,練習(xí)2,27,3．設(shè)G為n 階無(wú)向簡(jiǎn)單圖，n?5，證明G 或 中必含圈.,練習(xí)3,28,證二. 在G與 中有一個(gè)(不妨設(shè)為G)邊數(shù)

23、若G是森林, 則m?n-1, 矛盾.,練習(xí)3,29,4．畫(huà)出基圖為圖所示無(wú)向樹(shù)的所有非同構(gòu)的根樹(shù),練習(xí)4,解 以a, b, c, d為根的根樹(shù)同構(gòu), 選a為根, 如(1); 以 e, g 為根的根樹(shù)同構(gòu)，取 g為根，如(2)； 以 f 為根，如(3) .,(1) (2) (3),30,5．設(shè)T 是正則2叉樹(shù)，T 有t 片樹(shù)葉

24、，證明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,證二. 利用握手定理及樹(shù)的性質(zhì)證.T的樹(shù)根為2度頂點(diǎn)，所有內(nèi)點(diǎn)為3度頂點(diǎn)，葉為1度頂點(diǎn)，有(1) 2m = 2+3(i