1、離散數(shù)學(xué)圖論1第1頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五上節(jié)知識回顧圖G=，其中V是非空點(diǎn)集，E是邊集無向圖有向圖連通圖非連通圖樹：是一種特殊的圖無向樹有向樹2第2頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五上節(jié)知識回顧7-7 無向樹及其性質(zhì)定義7-7.1 連通無回路的無向圖稱為無向樹，簡稱樹,常用T表示樹。平凡圖稱為平凡樹。若無向圖G的每個(gè)連通分支都是樹，則稱G為森林。在無向樹中，度為1的結(jié)點(diǎn)稱為樹葉，度數(shù)大于或等于2的結(jié)點(diǎn)稱為分枝點(diǎn)或內(nèi)點(diǎn)。 。 。 。 。 。 。 。 。 。3第3頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五上節(jié)知識回顧定理7

2、-7.1 設(shè)G=是n階m條邊的無向圖,則下面各命題是等價(jià)的：（1）G是樹。（2）G中任意兩個(gè)結(jié)點(diǎn)之間有且僅有一條路。（3）G中無回路且m=n-1。（4）G是連通的且m=n-1。 (5) G是連通的且G中任何邊均為橋。 (6) G中沒有回路，但在任何兩個(gè)不同的結(jié)點(diǎn)之間加一條新邊，在所得的圖中得到唯一的一個(gè)含新邊的圈。 。 。 。 。4第4頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五7-8 根樹及其應(yīng)用1、根樹的相關(guān)定義2、根樹的性質(zhì)及應(yīng)用 二叉樹、m叉樹3、小結(jié)本節(jié)內(nèi)容安排5第5頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定義7-8.1設(shè)D是有向圖，若不考

3、慮D圖邊的方向時(shí)是一棵無向樹，則稱D為有向樹。V1。V2。V5。V3。V4。V6。V7。V8。V9。如：結(jié)點(diǎn)度的概念如前所講6第6頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論設(shè)T是n(n 2)階有向樹，若T中恰好有一個(gè)結(jié)點(diǎn)的入度為0，其余結(jié)點(diǎn)的入度均為1，則稱T為根樹定義7-8.2根樹入度為0的結(jié)點(diǎn)稱為根層次最大結(jié)點(diǎn)的層次稱為樹高入度為1出度為0的結(jié)點(diǎn)稱為葉出度不為0的結(jié)點(diǎn)稱為內(nèi)點(diǎn)或分枝點(diǎn)從樹根到T的任意結(jié)點(diǎn)v的單向通路長度稱為v的層次定義7-8.3：根樹包含一個(gè)或多個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)中某一個(gè)稱為根，其他所有結(jié)點(diǎn)被分成有限個(gè)子根樹平凡樹也稱為根樹。V1。V2。V5。V3

4、。V4。V6。V7。V8。V9。7第7頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論由于各有向邊的方向一致，故常省略，并且樹根在最上方。V1。V2。V5。V3。V4。V6。V7。V8。V9。V1。V2。V5。V3。V4。V6。V7。V8。V9。V1V2V3V4V5V6V7V8V9在根樹中，若將T中層數(shù)相同的結(jié)點(diǎn)都標(biāo)定次序，則稱T為有序樹。根樹的不同畫法：8第8頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論設(shè)T為一棵非平凡的根樹，vi,vjV(T),若vi 可達(dá)vj ,則稱vi為vj的祖先,vj 為vi的后代若vi鄰接到vj（即 E(T)），則稱v

5、i為vj的父親，而vj為vi的兒子若vj , vk的父親相同，則稱vj與vk是兄弟。補(bǔ)充定義V1。V2。V5。V3。V4。V6。V7。V8。V9。9第9頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定義7-8.4在根樹T中，若每個(gè)結(jié)點(diǎn)的出度的小于或等于r，則稱T為r叉樹。若每個(gè)結(jié)點(diǎn)的出度恰好等于r或0，則稱T為完全r叉樹。若完全r叉樹所有樹葉層次相同，則稱T為正則r叉樹。當(dāng)r=2時(shí)，稱為二叉樹。10第10頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論例：。二叉樹?正則二叉樹?請證明在完全二叉樹中，邊的總數(shù)等于2(nt-1)， nt為樹葉數(shù)。完全二

6、叉樹?11第11頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論二叉樹在實(shí)際生活中應(yīng)用廣泛。例如：M和E兩人進(jìn)行象棋比賽，規(guī)定一人連勝兩盤或共勝三盤即為獲勝，則所有可能的比賽結(jié)果可用如下二叉樹來描述。在m叉樹中，二叉樹相對來講比較容易處理，所以常常把m叉樹的問題轉(zhuǎn)換到二叉樹上來討論。比賽開始12第12頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論根樹應(yīng)用1：一棵m叉有序樹改寫為一棵二叉樹方法任何一棵有序樹都可以改寫為一個(gè)對應(yīng)的二叉樹：除了最左邊的分枝結(jié)點(diǎn)外，刪去所有從每一個(gè)結(jié)點(diǎn)長出的分枝。在同一層次中，兄弟結(jié)點(diǎn)之間用從左到右的有向邊連接。選定二叉樹

7、的左兒子和右兒子如下：直接處于給定結(jié)點(diǎn)下面的結(jié)點(diǎn)，作為左兒子，對于同一水平線上與給定結(jié)點(diǎn)右鄰的結(jié)點(diǎn)，作為右兒子，依次類推。13第13頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論例：把下面的m叉樹改寫為二叉樹。除了最左邊的分枝結(jié)點(diǎn)外，刪去所有從每一個(gè)結(jié)點(diǎn)長出的分枝在同一層次中，兄弟結(jié)點(diǎn)之間用從左到右的有向邊連接直接處于給定結(jié)點(diǎn)下面的結(jié)點(diǎn)，作為左兒子，對于同一水平線上與給定結(jié)點(diǎn)右鄰的結(jié)點(diǎn)，作為右兒子14第14頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論練習(xí)：把下面的有序樹改寫為二叉樹。 。 。 。 。 。知識點(diǎn)提示：此方法可推廣至有序森林到二叉樹

8、的轉(zhuǎn)換。此方法具有可逆性。課下自學(xué)15第15頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定理7-8.1 設(shè)有完全m叉樹，共有t片樹葉，i 個(gè)分枝點(diǎn)，則(m-1)i=t-1。證明：完全m叉樹中結(jié)點(diǎn)總數(shù)為: t+i也可表示為 mi+1故得 (m-1)i=t-1根樹應(yīng)用2：完全m叉樹的應(yīng)用。16第16頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論例：有28盞燈，擬用一個(gè)電源插座，問至少需要多少塊四插座的接線板？解：將四叉樹的每個(gè)分枝點(diǎn)看作是四插座的接線板，樹葉看作是燈，則根據(jù)定理7-8.1可知需要9塊。請思考？分析：四插座m叉樹m接線板分枝點(diǎn)i燈 樹

9、葉 t完全m叉樹，有t片樹葉，i 個(gè)分枝點(diǎn)，則(m-1)i=t-117第17頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論根樹應(yīng)用3：二叉樹的應(yīng)用最優(yōu)樹問題定義7-8.5 在根樹中，一個(gè)結(jié)點(diǎn)的通路長度為從樹根到此結(jié)點(diǎn)的通路中的邊數(shù)。分枝點(diǎn)的通路長度稱為內(nèi)部通路長度。樹葉的通路長度稱為外部通路長度。A18第18頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定理7-8.2 若完全二叉樹有n個(gè)分枝點(diǎn)，且內(nèi)部通路長度總和為L，外部通路長度總和為E，則 E=L+2n。證明： 對分枝點(diǎn)數(shù)目n進(jìn)行歸納證明。當(dāng)n=1時(shí)，如右圖所示， L=0， E=2，顯然， E

10、=L+2n成立。19第19頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定理7-8.2 若完全二叉樹有n個(gè)分枝點(diǎn)，且內(nèi)部通路長度總和為L，外部通路長度總和為E，則 E=L+2n。證明： 假設(shè)n=k-1時(shí)成立，即E=L+2(k-1)。當(dāng)n=k時(shí)，若刪去一個(gè)分枝點(diǎn)v(即變?yōu)槿~)，設(shè)v與根的通路長度為t ,且v的兩個(gè)兒子是樹葉，得到新樹T 。 由于T 有k-1個(gè)分枝點(diǎn)，則E=L+2(k-1) 在原樹T中，L=L+tE= E+2(t+1)-t= E+t+2。即得 E=L+2n 20第20頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論補(bǔ)充定義 給定一組權(quán)1

11、,2, ,t ，不妨設(shè)12 t 。設(shè)有一棵二叉樹，共有t片樹葉，分別帶權(quán)1,2, ,t ，該二叉樹稱為帶權(quán)二叉樹。21第21頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定義7-8.6 設(shè)二叉樹T有t片樹葉， v1,v2, ,vt權(quán)分別為1,2, ,t ，稱 (t)= 為T的權(quán)，其中L(vi)是vi的層數(shù)。在所有有t片樹葉，帶權(quán)1,2, ,t的二叉樹中，權(quán)最小的那棵二叉樹稱為最優(yōu)樹。例：求二叉樹T的權(quán)。32335解：(T)= =40是不是最優(yōu)二叉樹呢？22第22頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定理 7-8.3 設(shè)T為帶權(quán)12 t的最

12、優(yōu)樹，則 (1) 帶權(quán)1 ， 2的樹葉v1 ，v2是兄弟。 (2) 以樹葉v1 ，v2 為兒子的分枝點(diǎn)，其通路長度最長。定理 7-8.4 設(shè)T為帶權(quán)12 t的最優(yōu)樹，若將以帶權(quán)1 ， 2的樹葉為兒子的分枝點(diǎn)改為帶權(quán)1+2 的樹葉，得到新樹T ,則T也是最優(yōu)樹。23第23頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論Huffman算法 一種求最優(yōu)樹的算法給定實(shí)數(shù)1,2, ,t ，且1 2 t 。（1）連接權(quán)為1,2的兩片樹葉，得一個(gè)分枝點(diǎn)，其權(quán)為1+2 。（2）在1+2 ,3, ,t中選出兩個(gè)最小的權(quán)，連接它們對應(yīng)的結(jié)點(diǎn)（不一定是樹葉），得新分枝點(diǎn)及所帶的權(quán)。用此算法求上

13、例的最優(yōu)二叉樹。（3）重復(fù)（2），直到形成t-1個(gè)分枝點(diǎn)，t片樹葉為止。24第24頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論共分為四個(gè)步驟：。235。336。235。336。2355。10。336。2355。1016最優(yōu)樹為(4)所示，(T)=37(1)(2)(3)(4)練習(xí)： 畫一棵權(quán)為3,4,5,6,7,8,9的最優(yōu)二叉樹，并計(jì)算其權(quán)。25第25頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定義7-8.7 設(shè)12 n-1n為長為n的符號串，稱其子串1 , 12 , , 12 n-1分別為該符號串的長度為1,2, n-1的前綴，設(shè)A=1 ,

14、 2 , ,m為一個(gè)符號串集合，若對于任意的i , j A，i j, i , j互不為前綴，則稱A為前綴碼，若符號串中i(i=1,2, , m)只出現(xiàn)0，1兩個(gè)符號，則稱A為二元前綴碼。如：1,0,10,01,11,001abc,cba,bca,bac,acb,cab1,00,011,01001,01000是(二元)前綴碼嗎？如何產(chǎn)生二元前綴碼呢？根樹應(yīng)用4：二叉樹的應(yīng)用前綴碼問題26第26頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論定理7-8.5 任意一棵2叉樹的樹葉可對應(yīng)一個(gè)前綴碼。定理7-8.6 任意一個(gè)前綴碼都對應(yīng)一棵2叉樹。用二叉樹產(chǎn)生二元前綴碼之做法給定一

15、棵2叉樹T，設(shè)它有t片樹葉。設(shè)v為T的一個(gè)分枝點(diǎn)，則v至少有一個(gè)兒子，最多有兩個(gè)兒子。若v有兩個(gè)兒子，在由v引出的兩條邊上，左邊的標(biāo)上0，右邊的標(biāo)上1；若v有一個(gè)兒子，在由v引出的邊上可標(biāo)上0，也可標(biāo)上1。設(shè)vi為T的任一片樹葉，從樹根到vi的通路上各邊的標(biāo)號組成的0，1串組成的符號串放在vi處，t片樹葉處的t個(gè)符號串組成的集合為一個(gè)二元前綴碼。27第27頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論由上面做法知， vi處的符號串的前綴均在vi所在的通路上除vi外的結(jié)點(diǎn)處達(dá)到，因而所得符號串集合為二元前綴碼。若T存在單子分枝點(diǎn)，則由T產(chǎn)生的前綴碼可能不唯一。若T為正則2叉樹，則由T產(chǎn)生的前綴碼唯一。注意：因最優(yōu)2叉樹構(gòu)造的不唯一性，最佳前綴碼也可能不唯一，但其各自對應(yīng)的最優(yōu)2叉樹的權(quán)應(yīng)該相等。28第28頁，共31頁，2022年，5月20日，11點(diǎn)10分，星期五第七章 圖論練：在某通信系統(tǒng)中，a、b、c、d、e、f、g、h各字符的傳輸頻率依次為25%、 20%、 15%、 10%、 10%、 10%、 5%、 5%，求傳輸?shù)淖罴亚熬Y碼，并求傳輸10n(n=