資源描述:
《北大離散數(shù)學(xué)chap9無向樹及生成樹.ppt》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第九章樹第一節(jié)無向樹及生成樹內(nèi)容:無向樹,生成樹。重點(diǎn):1、無向樹的定義(包括等價(jià)定義),2、無向樹的性質(zhì),3、生成樹的定義,由連通圖構(gòu)造最小生成樹的方法。本章中所談回路均指簡單回路或初級(jí)回路。一、無向樹。1、無向樹——連通且不含回路的無向圖。無向樹簡稱樹,常用表示。平凡樹——平凡圖。森林——連通分支數(shù)大于等于2,且每個(gè)連通分支都是樹的無向圖。例1、例1、2、樹的六個(gè)等價(jià)定義。(1)連通且不含回路。(2)的每對頂點(diǎn)間具有唯一的路徑。(3)連通且。(4)無回路且。定理:設(shè),,,則以下命題等價(jià)。2、樹的六個(gè)等價(jià)定義。(5)無回路,但在中任
2、兩個(gè)不相鄰的頂點(diǎn)之間增加一條邊,就形成唯一的一條初級(jí)回路。(6)是連通的,但刪除任何一條邊后,就不連通了。3、性質(zhì)。(1)樹中頂點(diǎn)數(shù)與邊數(shù)的關(guān)系:。(2)定理:非平凡樹至少2片樹葉。證明:設(shè)為階非平凡樹,設(shè)有片樹葉,則有個(gè)頂點(diǎn)度數(shù)大于等于2,由握手定理,又由(1),代入上式,解得,即至少2片葉。例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解:所要畫的樹有6個(gè)頂點(diǎn),則邊數(shù)為5,因此6個(gè)頂點(diǎn)的度數(shù)之和為10,可以產(chǎn)生以下五種度數(shù)序列:(1)例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解:所要畫的樹有6個(gè)頂點(diǎn),則邊數(shù)為5,因此6個(gè)頂點(diǎn)的度數(shù)之和為10,
3、可以產(chǎn)生以下五種度數(shù)序列:(2)例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解:所要畫的樹有6個(gè)頂點(diǎn),則邊數(shù)為5,因此6個(gè)頂點(diǎn)的度數(shù)之和為10,可以產(chǎn)生以下五種度數(shù)序列:(3)例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解:所要畫的樹有6個(gè)頂點(diǎn),則邊數(shù)為5,因此6個(gè)頂點(diǎn)的度數(shù)之和為10,可以產(chǎn)生以下五種度數(shù)序列:(4)例2、畫出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹。解:所要畫的樹有6個(gè)頂點(diǎn),則邊數(shù)為5,因此6個(gè)頂點(diǎn)的度數(shù)之和為10,可以產(chǎn)生以下五種度數(shù)序列:(5)例3、(1)一棵樹有7片葉,3個(gè)3度頂點(diǎn),其余都是4度頂點(diǎn),求4度頂點(diǎn)多少個(gè)?解:設(shè)有個(gè)4度頂
4、點(diǎn),則頂點(diǎn)數(shù),邊數(shù),由握手定理,,解得,故這棵樹有1個(gè)4度頂點(diǎn)。例3、(2)一棵樹有2個(gè)4度頂點(diǎn),3個(gè)3度頂點(diǎn),其余都是樹葉,求這棵樹共有多少個(gè)頂點(diǎn)?解:設(shè)有片樹葉,則頂點(diǎn)數(shù),邊數(shù),由握手定理,,解得,故頂點(diǎn)總數(shù)為個(gè)。二、生成樹。1、定義:設(shè)是無向連通圖,是的生成子圖,若是樹,稱是的生成樹。樹枝弦余樹——在中的邊,——不在中的邊,——的所有的弦的集合的導(dǎo)出子圖。例4、上圖中,(2)是(1)的生成樹,(3)是(2)的余樹。注意:(1)生成樹不唯一,(2)余樹不一定是樹。2、連通圖的性質(zhì)。設(shè)為連通圖,,,(1)至少有一棵生成樹,(2),(
5、3)設(shè)是的生成樹,是的余樹,則中有條邊。已知連通圖,求其生成樹步驟。3、最小生成樹。對于有向圖或無向圖的每條邊附加一個(gè)實(shí)數(shù),則稱為邊上的權(quán),連同附加在各邊上的實(shí)數(shù)稱為帶權(quán)圖,記為。最小生成樹——各邊權(quán)和最小的生成樹。定義:設(shè)無向連通帶權(quán)圖,是的一棵生成樹,各邊帶權(quán)之和稱為的權(quán),記作。求最小生成樹的方法——避圈法。設(shè)階無向連通帶權(quán)圖中有條邊,它們帶的權(quán)分別為,不妨設(shè),(1)取在中(非環(huán),若為環(huán),則棄)。(2)若不與構(gòu)成回路,取在中,否則棄,再查,繼續(xù)這一過程,直到形成樹為止。解:例5、求以下連通圖的最小生成樹及。解:例5、求以下連通圖的
6、最小生成樹及。解:例5、求以下連通圖的最小生成樹及。解:例5、求以下連通圖的最小生成樹及。注意:的最小生成樹可能不唯一,但的不同最小生成樹權(quán)的值一樣。第二節(jié)根樹及其應(yīng)用內(nèi)容:有向樹,根樹,最優(yōu)二元樹。重點(diǎn):1、有向樹及根樹的定義,2、家族樹,有序樹,元樹的概念,3、最優(yōu)2元樹的概念及哈夫曼算法。一、根樹。1、有向樹:一個(gè)有向圖,若略去有向邊的方向所得的無向圖為一棵無向樹,則稱為有向樹。2、根樹:一棵非平凡的有向樹,如果有一個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1,則稱此有向樹為根樹。根樹的頂點(diǎn)樹葉(入度為1,出度為0)分支點(diǎn)樹根(入度為
7、0)內(nèi)點(diǎn)(入度為1,出度大于0)例1、例1、3、樹高。的層數(shù)——從樹根到頂點(diǎn)的通路長度,記。樹高——樹中頂點(diǎn)的最大層數(shù),記。如例1(2)中,4、家族樹。一棵根樹可以看成一棵家族樹。(1)若頂點(diǎn)鄰接到頂點(diǎn),則稱為的兒子,為的父親,(2)若同為的兒子,則稱為兄弟,(3)若,而可達(dá),則稱為的祖先,為的后代。5、根子樹。樹的根子樹——的非樹根的頂點(diǎn)及其后代導(dǎo)出的子圖。例2、二、元樹。1、有序樹——每一層上都規(guī)定次序的根樹。2、元樹——每個(gè)分支點(diǎn)至多有個(gè)兒子的根樹。元正則樹——每個(gè)分支點(diǎn)恰有個(gè)兒子的根樹。元有序樹元有序正則樹二、元樹。元有序完全
8、正則樹注意:2元有序正則樹是最重要的一種元樹。1、有序樹——每一層上都規(guī)定次序的根樹。2、元完全正則樹的層數(shù)相同(等于樹高)?!齽t樹,且所有樹葉例3、2元有序樹2元有序正則樹例3、2元有序完全正則樹3、最優(yōu)2元樹。