離散數(shù)學第九章[共71頁]

《離散數(shù)學第九章[共71頁]》由會員分享，可在線閱讀，更多相關《離散數(shù)學第九章[共71頁]（71頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第九章第九章 樹樹第一節(jié)第一節(jié) 無向樹及生成樹無向樹及生成樹 內(nèi)容：內(nèi)容：無向樹，生成樹。重點：重點：1、無向樹的定義 (包括等價定義)，2、無向樹的性質(zhì)，3、生成樹的定義，由連通圖構(gòu)造最小生成樹的方法。本章中所談回路均指簡單回路或初級回路。一、無向樹。一、無向樹。1、無向樹無向樹 連通且不含回路的無向圖。無向樹簡稱樹，常用表示。T平凡樹平凡樹 平凡圖。森林森林 連通分支數(shù)大于等于2，且每個連通分支都是樹的無向圖。T樹葉度數(shù)為1的頂點樹 的頂點分支點度數(shù)大于1的頂點例例1、(1)fceadb(2)(3)例例1、(4)2、樹的六個等價定義。(1)連通且不含回路。G(2)的每對頂點間具有唯一的路徑

2、。G(3)連通且G1nm。(4)無回路且G1nm。定理：定理：設,GV EVnEm，則以下命題等價。2、樹的六個等價定義。(5)無回路，但在G中任兩個不相鄰的頂點G之間增加一條邊，就形成唯一的一條初級回路。(6)是連通的，但刪除任何一條邊后，就不G連通了。3、性質(zhì)性質(zhì)。(1) 樹中頂點數(shù)與邊數(shù)的關系：1nm。(2) 定理定理：非平凡樹至少2片樹葉。證明：證明：設為階非平凡樹，,TV En設有 片樹葉，則有Tk個頂點度數(shù)大于等()nk于2，12( )2()niimd vknk由握手定理，又由(1)1mn，代入上式，解得2k ，即至少2片葉。T例例2、畫出所有的6個頂點的非同構(gòu)的樹。解：解：所要畫

3、的樹有6個頂點，則邊數(shù)為5，因此6個頂點的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(1)1 1 1 1 151T例例2、畫出所有的6個頂點的非同構(gòu)的樹。解：解：所要畫的樹有6個頂點，則邊數(shù)為5，因此6個頂點的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(2)1 1 1 1242T例例2、畫出所有的6個頂點的非同構(gòu)的樹。解：解：所要畫的樹有6個頂點，則邊數(shù)為5，因此6個頂點的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(3)1 1 1 1333T例例2、畫出所有的6個頂點的非同構(gòu)的樹。解：解：所要畫的樹有6個頂點，則邊數(shù)為5，因此6個頂點的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(4)1 1 1

4、2234T5T例例2、畫出所有的6個頂點的非同構(gòu)的樹。解：解：所要畫的樹有6個頂點，則邊數(shù)為5，因此6個頂點的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(5)1 122226T例例3、(1) 一棵樹有7片葉，3個3度頂點，其余都是4度頂點，求4度頂點多少個？解：解：設有 個4度頂點，則頂點數(shù)x73x ，邊數(shù)731x，由握手定理，43 372(731)xx ，解得1x ，故這棵樹有1個4度頂點。例例3、(2) 一棵樹有2個4度頂點，3個3度頂點，其余都是樹葉，求這棵樹共有多少個頂點？解：解：設有 片樹葉，則頂點數(shù)x23x ，邊數(shù)231x，由握手定理，243 32(231)xx ，解得9x ，故頂

5、點總數(shù)為23914 個。二、生成樹。二、生成樹。1、定義：定義：設是無向連通圖，,GV ET是G的生成子圖，若T是樹，稱T是G的生成樹。樹枝樹枝弦弦余樹余樹GT在中的邊，GT不在中的邊，T的所有的弦的集合的導出子圖。例例4、(3)(2)(1)上圖中，(2)是(1)的生成樹，(3)是(2)的余樹。注意：注意：(1) 生成樹不唯一，(2) 余樹不一定是樹。2、連通圖的性質(zhì)連通圖的性質(zhì)。設,GV E為連通圖，Vn，Em，(1)至少有一棵生成樹，G(2)1mn，(3) 設是TG的生成樹，T是T的余樹，則T中有1mn條邊。已知連通圖，求其生成樹步驟。G3、最小生成樹。對于有向圖或無向圖的每條邊附加一個實

6、數(shù)G( )w e，則稱( )w e為邊e上的權(quán)權(quán)，G連同附加在各邊上的實數(shù)稱為帶權(quán)圖帶權(quán)圖，記為,GV E W。最小生成樹最小生成樹 各邊權(quán)和最小的生成樹。定義：定義：設無向連通帶權(quán)圖,GV E W，T是G的一棵生成樹，T各邊帶權(quán)之和稱為T的權(quán)，記作( )W T。求最小生成樹的方法Kruskal避圈法避圈法。設階無向連通帶權(quán)圖n,GV E W中有m條邊12,me ee，它們帶的權(quán)分別為12,ma aa，不妨設12maaa，(1) 取1e在T中 (非環(huán)，若1e為環(huán)，則棄1e)。(2) 若不與2e1e構(gòu)成回路，取2e在T中，否則棄2e，再查3e，繼續(xù)這一過程，直到形成樹為止。cdefba解：解：1

7、T例例5、求以下連通圖的最小生成樹及T( )W T。(1)6643215555fabcde123541( )15W T54321bcdefa解：解：1T例例5、求以下連通圖的最小生成樹及T( )W T。(1)6643215555fabcde1()15( )W TW Tfedcba解：解：2T例例5、求以下連通圖的最小生成樹及T( )W T。(2)987764321105abcdef123572()18W T75321fedcba解：解：2T例例5、求以下連通圖的最小生成樹及T( )W T。(2)987764321105abcdef2()18( )W TW T注意：注意：的最小生成樹可能不唯一，

8、G但G的不同最小生成樹權(quán)的值一樣。第二節(jié)第二節(jié) 根樹及其應用根樹及其應用內(nèi)容：內(nèi)容：有向樹，根樹，最優(yōu)二元樹。重點：重點：1、有向樹及根樹的定義，2、家族樹，有序樹， 元樹的概念，r3、最優(yōu)2元樹的概念及哈夫曼()Huffman算法。一、根樹。一、根樹。1、有向樹有向樹：一個有向圖，若略去有向邊的D方向所得的無向圖為一棵無向樹，則稱D為有向樹有向樹。2、根樹根樹：一棵非平凡的有向樹，如果有一個頂點的入度為0，其余頂點的入度均為1，則稱此有向樹為根樹根樹。根樹的頂點樹葉(入度為1，出度為0)分支點樹根(入度為0)內(nèi)點(入度為1，出度大于0)例例1、例例1、3、樹高。的層數(shù)的層數(shù)v從樹根到頂點v的

9、通路長度，記( )l v。樹高樹高 樹中頂點的最大層數(shù)，記( )h T。如例1(2)中，4、家族樹。一棵根樹可以看成一棵家族樹家族樹。(1) 若頂點 鄰接到頂點，則稱為abba的兒子，為ab的父親，(2) 若a, b c同為 的兒子，則稱, b c為兄弟兄弟，(3) 若ad，而 可達a，則稱da為d的祖先祖先，d為a的后代后代。5、根子樹。樹的根子樹根子樹TT的非樹根的頂點a及其后代導出的子圖。T8v7v6v5v4v3v2v1v例例2、3vT8v7v6v5v4v二、二、 元樹。元樹。r1、有序樹有序樹 每一層上都規(guī)定次序的根樹。2、 元樹元樹r每個分支點至多有 個兒子的根樹。rr元正則樹元正則

10、樹 每個分支點恰有 個兒子的根樹。rr元有序樹元有序樹r元有序正則樹元有序正則樹二、二、 元樹。元樹。rr元有序完全正則樹元有序完全正則樹注意：注意：2元有序正則樹是最重要的一種r元樹。1、有序樹有序樹 每一層上都規(guī)定次序的根樹。2、r元完全正則樹元完全正則樹的層數(shù)相同 (等于樹高)。元正則樹，且所有樹葉r例例3、(1)22111(2)2221112元有序樹2元有序正則樹(3)222111例例3、2元有序完全正則樹三、三、樹的遍歷。樹的遍歷。1、前序遍歷前序遍歷 根，左，右。2、中序遍歷中序遍歷左，根，右。3、后序遍歷后序遍歷左，右，根。3、最優(yōu)2元樹。(1)的權(quán)權(quán)T最優(yōu)最優(yōu)2元樹元樹 權(quán)最小

11、的2元樹。中每片樹葉所帶權(quán)與其層高T乘積的和。記為1( )()tiiiW Tw L w例例4、下圖中的都是帶權(quán)1，3，4，5，6123,T T T的2元樹，求1( )W T，2()W T3()W T，。654311T解：解：1( )(63) 3(45 1)247W T 例例4、下圖中的都是帶權(quán)1，3，4，5，6123,T T T的2元樹，求1( )W T，2()W T3()W T，。解：解：2()(16)45 34 23 154W T 2T65431例例4、下圖中的都是帶權(quán)1，3，4，5，6123,T T T的2元樹，求1( )W T，2()W T3()W T，。解：解：3()(1 3) 3(

12、645)242W T 3T65431312()( )()W TW TW T但不能判定3T是最優(yōu)2元樹。(2) 求最優(yōu)2元樹的算法。Huffman算法：給定實數(shù)12,tw ww片樹葉的權(quán))，且t(12twww，( )a選12,w w連接得一分支點，( )b123,tww ww從中選兩個最小的，連接得一分支點，( )c重復( )b。例例5、求帶權(quán)1, 3, 4, 5, 6的最優(yōu)2元樹及T( )W T。34184116519解：解：( )(1 3) 3(456)242W T 其實( )W T等于T的各分支點的權(quán)之和，即( )48 11 19W T 42例例5、求帶權(quán)1, 3, 4, 5, 6的最優(yōu)2

13、元樹及T( )W T。34184116519解：解：其實( )W T等于T的各分支點的權(quán)之和，即( )48 11 19W T 42最優(yōu)樹是不唯一的，但Huffman算法得到的樹一定是最優(yōu)樹。例例6、(1) 求帶權(quán)為2, 3, 5, 7, 8, 9的最優(yōu)2元樹T，532105199158734解：解：( )_W T (2)5 10 19 153483例例6、(1) 求帶權(quán)為2, 3, 5, 7, 8, 9的最2優(yōu)元樹T，532105199158734解：解：(3)( )_h T 4例例6、(1) 求帶權(quán)為2, 3, 5, 7, 8, 9的最2優(yōu)元樹T，532105199158734解：解：(4)

14、T有_片樹葉。6例例6、(1) 求帶權(quán)為2, 3, 5, 7, 8, 9的最2優(yōu)元樹T，532105199158734解：解：(5)T有_個2度頂點，_個3度頂點，_個4度頂點。1404、求最佳前綴碼。(了解)最優(yōu)2元樹的用途之一是求最佳前綴碼。在通訊中，我們常用0和1的符號串作為英文字母的傳送信息，26個英文字母被使用的頻率往往是不同的。為了使整個信息的長度盡可能短，自然希望用較短的符號串去表示使用頻率高的英文字母，用較長的符號串表示使用頻率低的英文字母。 4、求最佳前綴碼。(了解)最優(yōu)元樹的用途之一是求最佳前綴碼。為了使編碼在使用中既快速又準確，可以用求 最優(yōu)2元樹的Huffman算法解決

15、這個問題。第九章第九章 小結(jié)與例題小結(jié)與例題一、無向樹及生成樹。一、無向樹及生成樹。1、基本概念。無向樹；樹葉，分支點；森林；平凡樹；生成樹，最小生成樹。2、運用。(1) 無向樹的六個等價定義。(2) 畫頂點數(shù)為6n 的所有非同構(gòu)的無向樹。一、無向樹及生成樹。一、無向樹及生成樹。1、基本概念。無向樹；樹葉，分支點；森林；平凡樹；生成樹，最小生成樹。2、運用。(3) 根據(jù)握手定理及樹的某些性質(zhì)，求頂點數(shù)或某些頂點的度數(shù)。(4) 求生成樹，最小生成樹。二、根樹及其應用。二、根樹及其應用。1、基本概念。有向樹；根樹；樹根，內(nèi)點，樹葉，分支點；頂點的層數(shù)與樹高；有序樹，正則樹，完全樹；最優(yōu)二元樹。二、

16、根樹及其應用。二、根樹及其應用。2、運用。(1) 按定義畫出等等。r元樹，r元正則樹，r元有序樹(2) 利用算法求最優(yōu)二元樹。Huffman例例1、畫出滿足下列要求的所有非同構(gòu)的無向樹。(1) 2個頂點(2) 3個頂點(3) 4個頂點例例1、畫出滿足下列要求的所有非同構(gòu)的無向樹。(4) 5個頂點例例2、若無向圖G中有n個頂點，條邊，則1nG為樹。這個命題正確嗎？解：解：命題不正確。反例：例例3、設連通圖12,G G如下圖所示，分別求出它們的所有非同構(gòu)的生成樹。1G解：解：1G的生成樹有：例例3、設連通圖12,G G如下圖所示，分別求出它們的所有非同構(gòu)的生成樹。解：解：2G的生成樹有：2G例例4

17、、一棵樹有個頂點的度數(shù)為2，2n3n個頂點的度數(shù)為3，kn個頂點的度數(shù)為k，而其余的頂點都是樹葉。求該樹的樹葉數(shù)。解：解：設有片樹葉，1n依握手定理及樹的性質(zhì)1mn，1231232321kknnnknmnnnnm得解得：1342(2)2knnnkn解：解：不一定，反例：例例5、一個有向圖，僅有一個頂點入度為0，D其余頂點的入度均為1， 一定是根樹嗎？D例例6、設 為二元正則樹， 為邊數(shù)， 為樹葉數(shù)。Tmt證明：，其中22mt2t 。證法一：證法一：設中頂點數(shù)為 ，分支點數(shù)為Tni，由二元正則樹的定義，知nit 2mi1mn由以上三個式子，得22mt。例例6、設 為二元正則樹， 為邊數(shù)， 為樹葉

18、數(shù)。Tmt證明：，其中22mt2t 。證法二：證法二：在二元正則樹中，除樹葉外，每個頂點的出度為2，除樹根外，每個頂點的入度都為1，例例6、設 為二元正則樹， 為邊數(shù)， 為樹葉數(shù)。Tmt證明：，其中22mt2t 。證法二：證法二：由握手定理知，1112( )( )( )nnniiiiiimd vdvdv2()1ntn321nt3(1)21mt所以，22mt。例例7、求帶權(quán)為0.5，1，2，3.5，4，5，6的最優(yōu) 二元樹，并求( )W T。1.510.53.5273.513654922解：解：( )(0.5 1) 5W T 2 43.5 3 (645)256結(jié) 束 語課 程 結(jié) 束 ， 謝 謝 大 家 ！