離散數(shù)學第九章課件.ppt

《離散數(shù)學第九章課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

2、樹的六個等價定義。(5)無回路，但在中任兩個不相鄰的頂點之間增加一條邊，就形成唯一的一條初級回路。(6)是連通的，但刪除任何一條邊后，就不連通了。3、性質(zhì)。(1)樹中頂點數(shù)與邊數(shù)的關(guān)系：。(2)定理：非平凡樹至少2片樹葉。證明：設(shè)為階非平凡樹，設(shè)有片樹葉，則有個頂點度數(shù)大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片葉。例2、畫出所有的6個頂點的非同構(gòu)的樹。解：所要畫的樹有6個頂點，則邊數(shù)為5，因此6個頂點的度數(shù)之和為10，可以產(chǎn)生以下五種度數(shù)序列：(1)例2、畫出所有的6個頂點的

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

4、生以下五種度數(shù)序列：(5)例3、(1)一棵樹有7片葉，3個3度頂點，其余都是4度頂點，求4度頂點多少個？解：設(shè)有個4度頂點，則頂點數(shù)，邊數(shù)，由握手定理，，解得，故這棵樹有1個4度頂點。例3、(2)一棵樹有2個4度頂點，3個3度頂點，其余都是樹葉，求這棵樹共有多少個頂點？解：設(shè)有片樹葉，則頂點數(shù)，邊數(shù)，由握手定理，，解得，故頂點總數(shù)為個。二、生成樹。1、定義：設(shè)是無向連通圖，是的生成子圖，若是樹，稱是的生成樹。樹枝弦余樹——在中的邊，——不在中的邊，——的所有的弦的集合的導出子圖。例4、上圖中，(

5、2)是(1)的生成樹，(3)是(2)的余樹。注意：(1)生成樹不唯一，(2)余樹不一定是樹。2、連通圖的性質(zhì)。設(shè)為連通圖，，，(1)至少有一棵生成樹，(2)，(3)設(shè)是的生成樹，是的余樹，則中有條邊。已知連通圖，求其生成樹步驟。3、最小生成樹。對于有向圖或無向圖的每條邊附加一個實數(shù)，則稱為邊上的權(quán)，連同附加在各邊上的實數(shù)稱為帶權(quán)圖，記為。最小生成樹——各邊權(quán)和最小的生成樹。定義：設(shè)無向連通帶權(quán)圖，是的一棵生成樹，各邊帶權(quán)之和稱為的權(quán)，記作。求最小生成樹的方法——避圈法。設(shè)階無向連通帶權(quán)圖中有條邊

6、，它們帶的權(quán)分別為，不妨設(shè)，(1)取在中(非環(huán)，若為環(huán)，則棄)。(2)若不與構(gòu)成回路，取在中，否則棄，再查，繼續(xù)這一過程，直到形成樹為止。解：例5、求以下連通圖的最小生成樹及。解：例5、求以下連通圖的最小生成樹及。解：例5、求以下連通圖的最小生成樹及。解：例5、求以下連通圖的最小生成樹及。注意：的最小生成樹可能不唯一，但的不同最小生成樹權(quán)的值一樣。第二節(jié)根樹及其應用內(nèi)容：有向樹，根樹，最優(yōu)二元樹。重點：1、有向樹及根樹的定義，2、家族樹，有序樹，元樹的概念，3、最優(yōu)2元樹的概念及哈夫曼算法。一、

7、根樹。1、有向樹：一個有向圖，若略去有向邊的方向所得的無向圖為一棵無向樹，則稱為有向樹。2、根樹：一棵非平凡的有向樹，如果有一個頂點的入度為0，其余頂點的入度均為1，則稱此有向樹為根樹。根樹的頂點樹葉(入度為1，出度為0)分支點樹根(入度為0)內(nèi)點(入度為1，出度大于0)例1、例1、3、樹高。的層數(shù)——從樹根到頂點的通路長度，記。樹高——樹中頂點的最大層數(shù)，記。如例1(2)中，4、家族樹。一棵根樹可以看成一棵家族樹。(1)若頂點鄰接到頂點，則稱為的兒子，為的父親，(2)若同為的兒子，則稱為兄弟，

8、(3)若，而可達，則稱為的祖先，為的后代。5、根子樹。樹的根子樹——的非樹根的頂點及其后代導出的子圖。例2、二、元樹。1、有序樹——每一層上都規(guī)定次序的根樹。2、元樹——每個分支點至多有個兒子的根樹。元正則樹——每個分支點恰有個兒子的根樹。元有序樹元有序正則樹二、元樹。元有序完全正則樹注意：2元有序正則樹是最重要的一種元樹。1、有序樹——每一層上都規(guī)定次序的根樹。2、元完全正則樹的層數(shù)相同(等于樹高)?！齽t樹，且所有樹葉例3、2元有序樹2元有序正則樹例3、2元有序完全正則樹三、樹的遍歷。1