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

上傳人:1528****253 文檔編號(hào):52068127 上傳時(shí)間:2022-02-07 格式:PPT 頁數(shù):71 大?。?.05MB
收藏 版權(quán)申訴 舉報(bào) 下載
離散數(shù)學(xué)第九章[共71頁]_第1頁
第1頁 / 共71頁
離散數(shù)學(xué)第九章[共71頁]_第2頁
第2頁 / 共71頁
離散數(shù)學(xué)第九章[共71頁]_第3頁
第3頁 / 共71頁

下載文檔到電腦,查找使用更方便

12 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《離散數(shù)學(xué)第九章[共71頁]》由會(huì)員分享,可在線閱讀,更多相關(guān)《離散數(shù)學(xué)第九章[共71頁](71頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

5、點(diǎn)總數(shù)為23914 個(gè)。二、生成樹。二、生成樹。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、最小生成樹。對(duì)于有向圖或無向圖的每條邊附加一個(gè)實(shí)

6、數(shù)G( )w e,則稱( )w e為邊e上的權(quán)權(quán),G連同附加在各邊上的實(shí)數(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)二元樹。重點(diǎn):重點(diǎn):1、有向樹及根樹的定義,2、家族樹,有序樹, 元樹的概念,r3、最優(yōu)2元樹的概念及哈夫曼()Huffman算法。一、根樹。一、根樹。1、有向樹有向樹:一個(gè)有向圖,若略去有向邊的D方向所得的無向圖為一棵無向樹,則稱D為有向樹有向樹。2、根樹根樹:一棵非平凡的有向樹,如果有一個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1,則稱此有向樹為根樹根樹。根樹的頂點(diǎn)樹葉(入度為1,出度為0)分支點(diǎn)樹根(入度為0)內(nèi)點(diǎn)(入度為1,出度大于0)例例1、例例1、3、樹高。的層數(shù)的層數(shù)v從樹根到頂點(diǎn)v的

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

10、樹 每個(gè)分支點(diǎn)恰有 個(gè)兒子的根樹。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í)數(shù)12,tw ww片樹葉的權(quán)),且t(12twww,( )a選12,w w連接得一分支點(diǎn),( )b123,tww ww從中選兩個(gè)最小的,連接得一分支點(diǎn),( )c重復(fù)( )b。例例5、求帶權(quán)1, 3, 4, 5, 6的最優(yōu)2元樹及T( )W T。34184116519解:解:( )(1 3) 3(456)242W T 其實(shí)( )W T等于T的各分支點(diǎn)的權(quán)之和,即( )48 11 19W T 42例例5、求帶權(quán)1, 3, 4, 5, 6的最優(yōu)2

13、元樹及T( )W T。34184116519解:解:其實(shí)( )W T等于T的各分支點(diǎn)的權(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有_個(gè)2度頂點(diǎn),_個(gè)3度頂點(diǎn),_個(gè)4度頂點(diǎn)。1404、求最佳前綴碼。(了解)最優(yōu)2元樹的用途之一是求最佳前綴碼。在通訊中,我們常用0和1的符號(hào)串作為英文字母的傳送信息,26個(gè)英文字母被使用的頻率往往是不同的。為了使整個(gè)信息的長(zhǎng)度盡可能短,自然希望用較短的符號(hào)串去表示使用頻率高的英文字母,用較長(zhǎng)的符號(hào)串表示使用頻率低的英文字母。 4、求最佳前綴碼。(了解)最優(yōu)元樹的用途之一是求最佳前綴碼。為了使編碼在使用中既快速又準(zhǔn)確,可以用求 最優(yōu)2元樹的Huffman算法解決

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

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

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

18、數(shù)。Tmt證明:,其中22mt2t 。證法二:證法二:在二元正則樹中,除樹葉外,每個(gè)頂點(diǎn)的出度為2,除樹根外,每個(gè)頂點(diǎn)的入度都為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é) 束 , 謝 謝 大 家 !

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!