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

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

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

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

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

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

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

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

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

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