《離散數(shù)學(xué)課件資料》PPT課件.ppt

2019/6/23,離散數(shù)學(xué),1,第九章 樹 9.1 無向樹及生成樹 9.2 根樹及其應(yīng)用,2019/6/23,離散數(shù)學(xué),2,樹：連通而不含回路的無向圖稱為無向樹，簡稱樹。 常記做T。,樹葉：樹中度數(shù)為1的結(jié)點(diǎn)。,分支點(diǎn)：樹中度數(shù)大于1的結(jié)點(diǎn)。,森林：連通分支數(shù)大于等于2,且每個(gè)連通分支都是樹的無向圖。,9.1 無向樹及生成圖,平凡樹：平凡圖。,本章所指回路為簡單回路或初級回路,2019/6/23,離散數(shù)學(xué),3,2019/6/23,離散數(shù)學(xué),4,一、無向樹,(1) G連通且不含回路； (2) G中無回路，且m = n-1，其中m為邊， n為結(jié)點(diǎn)數(shù)； (3) G是連通的，且m = n-1; (4) G中無回路，但在G中任意不相鄰兩結(jié)點(diǎn)之間增加一條邊，就得到唯一的一條初級回路； (5) G是連通的且G中每條邊都是橋； (6) G中每一對結(jié)點(diǎn)之間有唯一的一條基本通路。,樹的等價(jià) 定義,任意非平凡樹T (n, m)至少有兩片樹葉。,定理,設(shè)T 有k片樹葉，于是2 m k+ 2 (n - k)， 則2 (n-1) 2n - k，則k 2,2019/6/23,離散數(shù)學(xué),5,例：畫出6階所有非同構(gòu)的無向樹。,(1) 1，1，1，1，1，5 (2) 1，1，1，1，2，4 (3) 1，1，1，1，3，3 (4) 1，1，1，2，2，3 兩種 (5) 1，1，2，2，2，2,解：設(shè)T是6階無向樹，T的邊數(shù)m5， 由握手定理可知，d(v)10，且(T)1，(T)5。故T的度數(shù)列必為以下情況之一：,一、無向樹,2019/6/23,離散數(shù)學(xué),6,2019/6/23,離散數(shù)學(xué),7,二、生成樹,生成樹：若連通圖G的某個(gè)生成子圖是一棵樹， 則稱該樹為G的生成樹，記做TG。,樹枝：生成樹TG的邊。,弦：G中不在TG中的邊。,生成樹的余樹(補(bǔ))：TG的所有弦的集合的導(dǎo)出子圖。余樹不一定是樹,也不一定連通。,2019/6/23,離散數(shù)學(xué),8,二、生成樹,圖G,生成樹TG,生成樹TG的補(bǔ),無向連通圖如果本身不是樹，它的生成樹是不唯一的，但所有連通圖都具有生成樹。,2019/6/23,離散數(shù)學(xué),9,推論1 : G為n階m條邊的無向連通圖，則mn1。 (要把n個(gè)頂點(diǎn)聯(lián)系起來至少需要n-1條邊),推論2 : 設(shè)G是n階m條邊的無向連通圖，T為G的生成樹，則T的余樹中含有m-n+1條邊（即T有m-n+1條弦）。,定理,任何連通圖G至少存在一棵生成樹。,二、生成樹,2019/6/23,離散數(shù)學(xué),10,基本回路: 設(shè)T是n階m條邊的無向連通圖G的一棵生成樹，設(shè)e1, e2, , emn+1為T的弦。設(shè)Cr為T添加弦er產(chǎn)生的G的回路, 該回路只含生成樹T的一條弦er，其余邊均為樹枝，稱Cr為對應(yīng)T的弦er的基本回路，r1, 2, , mn+1。,二、生成樹,基本回路系統(tǒng)： C1, C2, , Cmn+1為G對應(yīng)T的基本回路系統(tǒng)。,一個(gè)連通圖對應(yīng)不同的生成樹的基本回路及基本回路系統(tǒng)可能不同，但是基本回路的個(gè)數(shù)相等，等于mn+1。,2019/6/23,離散數(shù)學(xué),11,三、最小生成樹,最小生成樹：設(shè)G = 是無向連通帶權(quán)圖，T 是G 的一棵生成樹，T 各邊帶權(quán)之和稱為T 的權(quán)，記為W(T)。G的所有生成樹中帶權(quán)最小的生成樹稱為G的最小生成樹。,Kruskal算法(避圈法)：設(shè)n階無向連通帶權(quán)圖G有m條邊 ，它們帶的權(quán)分別為 ，設(shè) 。,（1）取e1在T中（ e i非環(huán)，若是環(huán)，則放棄）,（2）若e2不與e1構(gòu)成回路，取e2在T中，否則放棄e2，考查e3，繼續(xù)這一過程，直到形成生成樹T為止。,2019/6/23,離散數(shù)學(xué),12,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,Kruskal算法:,7,12,18,19,2019/6/23,離散數(shù)學(xué),13,9.2 根樹及其應(yīng)用,其中：入度為0的頂點(diǎn)稱為樹根，,有向樹：一個(gè)有向圖，若略去所有有向邊的方向后得到的無向圖是一棵樹，則稱該有向圖為有向樹。,根樹：非平凡的有向樹，若恰有一個(gè)結(jié)點(diǎn)的入度為0， 其余所有頂點(diǎn)的入度均為1，則稱此有向樹為根樹。,入度為1，出度為0的頂點(diǎn)稱為樹葉，,入度為1出度大于0的頂點(diǎn)稱為內(nèi)點(diǎn)，,內(nèi)點(diǎn)和樹根統(tǒng)稱為分支點(diǎn)。,2019/6/23,離散數(shù)學(xué),14,一、有向樹,層數(shù):從樹根到任意頂點(diǎn)v的通路長度，稱為v的層數(shù)，記為l(v).,樹高:層數(shù)最大的頂點(diǎn)的層數(shù)，記為h(T)。 （本書樹根為第0層。）,2019/6/23,離散數(shù)學(xué),15,根樹可看成是家族樹： (1) 若從a到b可達(dá)，則稱a是b的祖先， b是a的后代； (2) 若是根樹中的有向邊，則稱a是b的父親， b是a的兒子； (3) 若b、c同為a的兒子，則稱b、c為兄弟。,一、有向樹,根子樹：根樹T 中，任一不為樹根的頂點(diǎn)v及其所有后代導(dǎo)出的子圖, 稱為T 的以v為根的子樹。,2019/6/23,離散數(shù)學(xué),16,二、有序樹,r元樹：每個(gè)分支點(diǎn)至多有r個(gè)兒子； r元有序樹：r元樹是有序的； r元正則樹：每個(gè)分支點(diǎn)恰有r個(gè)兒子； r元正則有序樹：r元正則樹是有序的； r元完全正則樹：樹葉層數(shù)均為樹高的r元正則樹； r元完全正則有序樹：r元完全正則樹是有序的。,有序樹：每層上的頂點(diǎn)都規(guī)定了次序的根樹。,分類：根據(jù)根樹T中每個(gè)分支點(diǎn)兒子數(shù)以及是否有序：,2019/6/23,離散數(shù)學(xué),17,二、有序樹,將有序樹轉(zhuǎn)換為二元樹： (1) 從樹根開始，保留每個(gè)父親頂點(diǎn)和最左邊兒子 的連線，撤消與其他兒子的連線； (2) 兄弟間用從左至右的水平有向邊連接。 (3) 以位于給定頂點(diǎn)下面的頂點(diǎn)作為左兒子，以給定 頂點(diǎn)的水平右鄰頂點(diǎn)（兄弟）作為右兒子。,將森林轉(zhuǎn)換為二元樹：將每棵樹表示為二元樹，除第一棵二元樹外，將余下每棵二元樹作為前一棵二元樹的根的右子樹。,2019/6/23,離散數(shù)學(xué),18,三、最優(yōu)樹,帶權(quán)二元樹：設(shè)有一棵二元樹有t 片樹葉，分別帶權(quán)為w1、w2 、 、wt，則稱之為帶權(quán)二元樹； 權(quán)：稱 為該帶權(quán)二元樹的權(quán)，其中，權(quán)為wi的樹葉的層數(shù)為L(wi)。,最優(yōu)二元樹：所有帶權(quán)w1、w2 、 、wt的二元樹中， 帶權(quán)W( T)最小的二元樹。,2019/6/23,離散數(shù)學(xué),19,例：下圖所示的三棵二叉樹T1,T2,T3都是帶權(quán)為2、2、3、3、5的二叉樹。,W(T1)=22+22+33+53+32=38 W(T2)=34+54+33+22+21=47 W(T3)=33+33+52+22+22=36,三、最優(yōu)樹,2019/6/23,離散數(shù)學(xué),20,求最優(yōu)樹的算法(Huffman算法),給定實(shí)數(shù)w1,w2,wt，設(shè)w1w2wt。 連接權(quán)為w1, w2的兩片樹葉，得一個(gè)分支點(diǎn)，其權(quán)為w1+w2。,三、最優(yōu)樹, 重復(fù)，直到形成t-1個(gè)分支點(diǎn)、t片樹葉為止。, 在w1+w2, w3, , wt中選出兩個(gè)最小的權(quán)，連接它們對應(yīng)的頂點(diǎn)（不一定是樹葉），得新分支點(diǎn)及所帶的權(quán)。,2019/6/23,離散數(shù)學(xué),21,9,例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,2019/6/23,離散數(shù)學(xué),22,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,2019/6/23,離散數(shù)學(xué),23,例：求帶權(quán)為1、1、2、3、4、5的最優(yōu)樹。,三、最優(yōu)樹,W(T)=38,最優(yōu)樹不是唯一的，但是由Huffman算法得到的樹一定是最優(yōu)樹。,2019/6/23,離散數(shù)學(xué),24,前綴:設(shè)=12n-1n是長度為n的符號串，稱 其子串1,12,12n-1分別為的長 度為1,2, ,n-1的前綴。,四、最佳前綴碼,二元前綴碼:若i (i=1,2,m)中只出現(xiàn)0與1兩個(gè)符號， 則稱B為二元前綴碼。,前綴碼:設(shè)B=1, 2, , m為一個(gè)符號串集合，若對 于任意的i, j B，ij，i, j互不為前綴，則 稱B為前綴碼。,2019/6/23,離散數(shù)學(xué),25,四、最佳前綴碼,(2)如何產(chǎn)生二元前綴碼？ 定理:任何一棵二元正則樹對應(yīng)一個(gè)二元前綴碼。 定理:任何一個(gè)二元前綴碼對應(yīng)一顆二元正則樹。,0，10，110，1111,1，11，101，0010,1，01，001，000,00，11，011，0100，0101,例：判斷下列符號串集合是否是前綴碼。,2019/6/23,離散數(shù)學(xué),26,方法：用Huffman算法產(chǎn)生最佳前綴碼。,例、在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25%；1：20%；2：15%；3：10% 4：10%；5：10%；6：5%； 7：5% 求傳輸它們的最佳前綴碼？ 求傳輸10n（n2）個(gè)按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個(gè)二進(jìn)制數(shù)字？ 若用等長碼(長為3)傳輸需要多少個(gè)二進(jìn)制數(shù)字？,四、最佳前綴碼,最佳前綴碼：當(dāng)要傳輸按著一定比例出現(xiàn)的符號串 時(shí)，需要尋找傳輸它們最省二進(jìn)制數(shù)字 的前綴碼，即最佳前綴碼。,2019/6/23,離散數(shù)學(xué),27,例：以100乘各頻率為權(quán)，并按小到大排列，得w1=5,w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25。產(chǎn)生的最優(yōu)樹如下。, 0 01 (25%) 1 11 (20%) 2 001 (15%) 3 100 (10%) 4 101 (10%) 50001 (10%) 6 00000 (5%) 7 00001 (5%),傳100個(gè)按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字個(gè)數(shù)W(T)=285，所以傳10n(n2)個(gè)所用二進(jìn)制數(shù)字應(yīng)為2.8510n。,用等長碼（長為3）應(yīng)該用310n個(gè)數(shù)字,因此用最佳前綴碼可節(jié)省傳遞數(shù)字。,2019/6/23,離散數(shù)學(xué),28,（1）由于在每一步選擇兩個(gè)最小的權(quán)的選法不唯一。 （2）因?yàn)閮蓚€(gè)權(quán)對應(yīng)的頂點(diǎn)所放左右位置不同。 （3）畫出的最優(yōu)樹可能不同，最佳前綴碼并不唯一，但有一點(diǎn)是共同的，就是它們的權(quán)相等，即它們都應(yīng)該是最優(yōu)樹。,四、最佳前綴碼,2019/6/23,離散數(shù)學(xué),29,遍歷：對一棵根樹的每個(gè)頂點(diǎn)訪問且僅訪問一次稱為遍歷一棵樹。,中序遍歷法：b a (f d g) c e,五、樹的遍歷,前序遍歷法：a b (c (d f g) e),后序遍歷法：b (f g d) e c) a,對2元有序正則樹的遍歷方式：, 先序遍歷法：訪問次序?yàn)椋簶涓?、左子樹、右子? 后序遍歷法：訪問次序?yàn)椋鹤笞訕?、右子樹、樹? 中序遍歷法：訪問次序?yàn)椋鹤笞訕?、樹根、右子?2019/6/23,離散數(shù)學(xué),30,用2元有序正則樹存放算式： 最高層次的運(yùn)算符放在樹根上。 依次將運(yùn)算符放在根子樹的根上。 參加運(yùn)算的數(shù)放在樹葉上， 規(guī)定：被除數(shù)、被減數(shù)放在左子樹樹葉上。,五、樹的遍歷,2019/6/23,離散數(shù)學(xué),31,例：用二叉有序正則樹表示算式： (b+(c