《離散數(shù)學第九章[共71頁]》由會員分享,可在線閱讀,更多相關(guān)《離散數(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。定理:定理:設(shè),GV EVnEm,則以下命題等價。2、樹的六個等價定義。(5)無回路,但在G中任兩個不相鄰的頂點G之間增加一條邊,就形成唯一的一條初級回路。(6)是連通的,但刪除任何一條邊后,就不G連通了。3、性質(zhì)性質(zhì)。(1) 樹中頂點數(shù)與邊數(shù)的關(guān)系:1nm。(2) 定理定理:非平凡樹至少2片樹葉。證明:證明:設(shè)為階非平凡樹,,TV En設(shè)有 片樹葉,則有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度頂點多少個?解:解:設(shè)有 個4度頂點,則頂點數(shù)x73x ,邊數(shù)731x,由握手定理,43 372(731)xx ,解得1x ,故這棵樹有1個4度頂點。例例3、(2) 一棵樹有2個4度頂點,3個3度頂點,其余都是樹葉,求這棵樹共有多少個頂點?解:解:設(shè)有 片樹葉,則頂點數(shù)x23x ,邊數(shù)231x,由握手定理,243 32(231)xx ,解得9x ,故頂
5、點總數(shù)為23914 個。二、生成樹。二、生成樹。1、定義:定義:設(shè)是無向連通圖,,GV ET是G的生成子圖,若T是樹,稱T是G的生成樹。樹枝樹枝弦弦余樹余樹GT在中的邊,GT不在中的邊,T的所有的弦的集合的導(dǎo)出子圖。例例4、(3)(2)(1)上圖中,(2)是(1)的生成樹,(3)是(2)的余樹。注意:注意:(1) 生成樹不唯一,(2) 余樹不一定是樹。2、連通圖的性質(zhì)連通圖的性質(zhì)。設(shè),GV E為連通圖,Vn,Em,(1)至少有一棵生成樹,G(2)1mn,(3) 設(shè)是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)和最小的生成樹。定義:定義:設(shè)無向連通帶權(quán)圖,GV E W,T是G的一棵生成樹,T各邊帶權(quán)之和稱為T的權(quán),記作( )W T。求最小生成樹的方法Kruskal避圈法避圈法。設(shè)階無向連通帶權(quán)圖n,GV E W中有m條邊12,me ee,它們帶的權(quán)分別為12,ma aa,不妨設(shè)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é) 根樹及其應(yīng)用根樹及其應(yīng)用內(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及其后代導(dǎo)出的子圖。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重復(fù)( )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) 求生成樹,最小生成樹。二、根樹及其應(yīng)用。二、根樹及其應(yīng)用。1、基本概念。有向樹;根樹;樹根,內(nèi)點,樹葉,分支點;頂點的層數(shù)與樹高;有序樹,正則樹,完全樹;最優(yōu)二元樹。二、
16、根樹及其應(yīng)用。二、根樹及其應(yīng)用。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、設(shè)連通圖12,G G如下圖所示,分別求出它們的所有非同構(gòu)的生成樹。1G解:解:1G的生成樹有:例例3、設(shè)連通圖12,G G如下圖所示,分別求出它們的所有非同構(gòu)的生成樹。解:解:2G的生成樹有:2G例例4
17、、一棵樹有個頂點的度數(shù)為2,2n3n個頂點的度數(shù)為3,kn個頂點的度數(shù)為k,而其余的頂點都是樹葉。求該樹的樹葉數(shù)。解:解:設(shè)有片樹葉,1n依握手定理及樹的性質(zhì)1mn,1231232321kknnnknmnnnnm得解得:1342(2)2knnnkn解:解:不一定,反例:例例5、一個有向圖,僅有一個頂點入度為0,D其余頂點的入度均為1, 一定是根樹嗎?D例例6、設(shè) 為二元正則樹, 為邊數(shù), 為樹葉數(shù)。Tmt證明:,其中22mt2t 。證法一:證法一:設(shè)中頂點數(shù)為 ,分支點數(shù)為Tni,由二元正則樹的定義,知nit 2mi1mn由以上三個式子,得22mt。例例6、設(shè) 為二元正則樹, 為邊數(shù), 為樹葉
18、數(shù)。Tmt證明:,其中22mt2t 。證法二:證法二:在二元正則樹中,除樹葉外,每個頂點的出度為2,除樹根外,每個頂點的入度都為1,例例6、設(shè) 為二元正則樹, 為邊數(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é) 束 , 謝 謝 大 家 !