第九章

樹(shù)第一節(jié)

無(wú)向樹(shù)及生成樹(shù)

第九章樹(shù)第一節(jié)無(wú)向樹(shù)及生成樹(shù)1內(nèi)容：無(wú)向樹(shù)，生成樹(shù)。重點(diǎn)：1、無(wú)向樹(shù)的定義

(包括等價(jià)定義)，2、無(wú)向樹(shù)的性質(zhì)，3、生成樹(shù)的定義，由連通圖構(gòu)造最小生成樹(shù)的方法。本章中所談回路均指簡(jiǎn)單回路或初級(jí)回路。內(nèi)容：無(wú)向樹(shù)，生成樹(shù)。重點(diǎn)：1、無(wú)向樹(shù)的定義(包括等價(jià)定義2一、無(wú)向樹(shù)。1、無(wú)向樹(shù)——連通且不含回路的無(wú)向圖。無(wú)向樹(shù)簡(jiǎn)稱樹(shù)，常用表示。平凡樹(shù)——平凡圖。森林

——連通分支數(shù)大于等于2，且每個(gè)連通分支都是樹(shù)的無(wú)向圖。一、無(wú)向樹(shù)。1、無(wú)向樹(shù)——連通且不含回路的無(wú)向圖。無(wú)向樹(shù)簡(jiǎn)稱3例1、例1、4例1、例1、52、樹(shù)的六個(gè)等價(jià)定義。(1)連通且不含回路。(2)的每對(duì)頂點(diǎn)間具有唯一的路徑。(3)連通且。(4)無(wú)回路且。定理：設(shè)，，，則以下命題等價(jià)。2、樹(shù)的六個(gè)等價(jià)定義。(1)連通且不含回路。(2)的每對(duì)頂點(diǎn)62、樹(shù)的六個(gè)等價(jià)定義。(5)無(wú)回路，但在中任兩個(gè)不相鄰的頂點(diǎn)之間增加一條邊，就形成唯一的一條初級(jí)回路。(6)是連通的，但刪除任何一條邊后，就不連通了。2、樹(shù)的六個(gè)等價(jià)定義。(5)無(wú)回路，但在中任兩個(gè)不相鄰的頂點(diǎn)73、性質(zhì)。(1)樹(shù)中頂點(diǎn)數(shù)與邊數(shù)的關(guān)系：。(2)定理：非平凡樹(shù)至少2片樹(shù)葉。證明：設(shè)為階非平凡樹(shù)，設(shè)有片樹(shù)葉，則有個(gè)頂點(diǎn)度數(shù)大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片葉。3、性質(zhì)。(1)樹(shù)中頂點(diǎn)數(shù)與邊數(shù)的關(guān)系：。(2)定理：非8例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)的非同構(gòu)的樹(shù)。解：所要畫(huà)的樹(shù)有6個(gè)頂9例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ù)序列：(2)例2、畫(huà)出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹(shù)。解：所要畫(huà)的樹(shù)有6個(gè)頂10例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è)頂11例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è)頂12例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ù)序列：(5)例2、畫(huà)出所有的6個(gè)頂點(diǎn)的非同構(gòu)的樹(shù)。解：所要畫(huà)的樹(shù)有6個(gè)頂13例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、(1)一棵樹(shù)有7片葉，3個(gè)3度頂點(diǎn)，其余都是4度頂點(diǎn)14例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è)。例3、(2)一棵樹(shù)有2個(gè)4度頂點(diǎn)，3個(gè)3度頂點(diǎn)，其余都是樹(shù)15二、生成樹(shù)。1、定義：設(shè)是無(wú)向連通圖，是的生成子圖，若是樹(shù)，稱是的生成樹(shù)。樹(shù)枝弦余樹(shù)——在中的邊，——不在中的邊，——的所有的弦的集合的導(dǎo)出子圖。二、生成樹(shù)。1、定義：設(shè)是無(wú)向連通圖，是的生成子圖，若是樹(shù)，16例4、上圖中，(2)是(1)的生成樹(shù)，(3)是(2)的余樹(shù)。注意：(1)生成樹(shù)不唯一，(2)余樹(shù)不一定是樹(shù)。例4、上圖中，(2)是(1)的生成樹(shù)，(3)是(2)的余樹(shù)。172、連通圖的性質(zhì)。設(shè)為連通圖，，，(1)至少有一棵生成樹(shù)，(2)，(3)設(shè)是的生成樹(shù)，是的余樹(shù)，則中有條邊。已知連通圖，求其生成樹(shù)步驟。2、連通圖的性質(zhì)。設(shè)為連通圖，，，(1)至少有一棵生成樹(shù)，(183、最小生成樹(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)，記作。3、最小生成樹(shù)。對(duì)于有向圖或無(wú)向圖的每條邊附加一個(gè)實(shí)數(shù)，則稱19求最小生成樹(shù)的方法——避圈法。設(shè)階無(wú)向連通帶權(quán)圖中有條邊，它們帶的權(quán)分別為，不妨設(shè)，(1)取在中

(非環(huán)，若為環(huán)，則棄)。(2)若不與構(gòu)成回路，取在中，否則棄，再查，繼續(xù)這一過(guò)程，直到形成樹(shù)為止。求最小生成樹(shù)的方法——避圈法。設(shè)階無(wú)向連通帶權(quán)圖中有條邊，它20解：例5、求以下連通圖的最小生成樹(shù)及。解：例5、求以下連通圖的最小生成樹(shù)及。21解：例5、求以下連通圖的最小生成樹(shù)及。解：例5、求以下連通圖的最小生成樹(shù)及。22解：例5、求以下連通圖的最小生成樹(shù)及。解：例5、求以下連通圖的最小生成樹(shù)及。23解：例5、求以下連通圖的最小生成樹(shù)及。解：例5、求以下連通圖的最小生成樹(shù)及。24注意：的最小生成樹(shù)可能不唯一，但的不同最小生成樹(shù)權(quán)的值一樣。注意：的最小生成樹(shù)可能不唯一，但的不同最小生成樹(shù)權(quán)的值一樣。25第二節(jié)

根樹(shù)及其應(yīng)用第二節(jié)根樹(shù)及其應(yīng)用26內(nèi)容：有向樹(shù)，根樹(shù)，最優(yōu)二元樹(shù)。重點(diǎn)：1、有向樹(shù)及根樹(shù)的定義，2、家族樹(shù)，有序樹(shù)，元樹(shù)的概念，3、最優(yōu)2元樹(shù)的概念及哈夫曼算法。內(nèi)容：有向樹(shù)，根樹(shù)，最優(yōu)二元樹(shù)。重點(diǎn)：1、有向樹(shù)及根樹(shù)的定義27一、根樹(shù)。1、有向樹(shù)：一個(gè)有向圖，若略去有向邊的方向所得的無(wú)向圖為一棵無(wú)向樹(shù)，則稱為有向樹(shù)。2、根樹(shù)：一棵非平凡的有向樹(shù)，如果有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則稱此有向樹(shù)為根樹(shù)。一、根樹(shù)。1、有向樹(shù)：一個(gè)有向圖，若略去有向邊的方向所得的無(wú)28根樹(shù)的頂點(diǎn)樹(shù)葉(入度為1，出度為0)分支點(diǎn)樹(shù)根(入度為0)內(nèi)點(diǎn)(入度為1，出度大于0)根樹(shù)的頂點(diǎn)樹(shù)葉(入度為1，出度為0)分支點(diǎn)樹(shù)根(入度為0)內(nèi)29例1、例1、30例1、例1、313、樹(shù)高。的層數(shù)——從樹(shù)根到頂點(diǎn)的通路長(zhǎng)度，記。樹(shù)高——樹(shù)中頂點(diǎn)的最大層數(shù)，記。3、樹(shù)高。的層數(shù)——從樹(shù)根到頂點(diǎn)的通路長(zhǎng)度，記。樹(shù)高——樹(shù)中32如例1(2)中，如例1(2)中，334、家族樹(shù)。一棵根樹(shù)可以看成一棵家族樹(shù)。(1)若頂點(diǎn)鄰接到頂點(diǎn)，則稱為的兒子，為的父親，(2)若同為的兒子，則稱為兄弟，(3)若，而可達(dá)，則稱為的祖先，為的后代。4、家族樹(shù)。一棵根樹(shù)可以看成一棵家族樹(shù)。(1)若頂點(diǎn)鄰接到345、根子樹(shù)。樹(shù)的根子樹(shù)——的非樹(shù)根的頂點(diǎn)及其后代導(dǎo)出的子圖。5、根子樹(shù)。樹(shù)的根子樹(shù)——的非樹(shù)根的頂點(diǎn)及其后代導(dǎo)出的子圖。35例2、例2、36二、元樹(shù)。1、有序樹(shù)——每一層上都規(guī)定次序的根樹(shù)。2、元樹(shù)——每個(gè)分支點(diǎn)至多有個(gè)兒子的根樹(shù)。元正則樹(shù)——每個(gè)分支點(diǎn)恰有個(gè)兒子的根樹(shù)。元有序樹(shù)元有序正則樹(shù)二、元樹(shù)。1、有序樹(shù)——每一層上都規(guī)定次序的根樹(shù)。2、元樹(shù)—37二、元樹(shù)。元有序完全正則樹(shù)注意：2元有序正則樹(shù)是最重要的一種元樹(shù)。1、有序樹(shù)——每一層上都規(guī)定次序的根樹(shù)。2、元完全正則樹(shù)的層數(shù)相同

(等于樹(shù)高)?！齽t樹(shù)，且所有樹(shù)葉二、元樹(shù)。元有序完全正則樹(shù)注意：2元有序正則樹(shù)是最重要的一種38例3、2元有序樹(shù)2元有序正則樹(shù)例3、2元有序樹(shù)2元有序正則樹(shù)39例3、2元有序完全正則樹(shù)例3、2元有序完全正則樹(shù)40三、樹(shù)的遍歷。1、前序遍歷——根，左，右。2、中序遍歷——左，根，右。3、后序遍歷——左，右，根。三、樹(shù)的遍歷。1、前序遍歷——根，左，右。2、中序遍歷——左413、最優(yōu)2元樹(shù)。(1)的權(quán)最優(yōu)2元樹(shù)——權(quán)最小的2元樹(shù)?！忻科瑯?shù)葉所帶權(quán)與其層高乘積的和。記為3、最優(yōu)2元樹(shù)。(1)的權(quán)最優(yōu)2元樹(shù)——權(quán)最小的2元樹(shù)?！?2例4、下圖中的都是帶權(quán)1，3，4，5，6的2元樹(shù)，求，，。解：例4、下圖中的都是帶權(quán)1，3，4，5，6的2元樹(shù)，求，，。解43例4、下圖中的都是帶權(quán)1，3，4，5，6的2元樹(shù)，求，，。解：例4、下圖中的都是帶權(quán)1，3，4，5，6的2元樹(shù)，求，，。解44例4、下圖中的都是帶權(quán)1，3，4，5，6的2元樹(shù)，求，，。解：但不能判定是最優(yōu)2元樹(shù)。例4、下圖中的都是帶權(quán)1，3，4，5，6的2元樹(shù)，求，，。解45(2)求最優(yōu)2元樹(shù)的算法。算法：給定實(shí)數(shù)片樹(shù)葉的權(quán))，且(，選連接得一分支點(diǎn)，從中選兩個(gè)最小的，連接得一分支點(diǎn)，重復(fù)。(2)求最優(yōu)2元樹(shù)的算法。算法：給定實(shí)數(shù)片樹(shù)葉的權(quán))，且(46例5、求帶權(quán)1,3,4,5,6的最優(yōu)2元樹(shù)及。解：其實(shí)等于的各分支點(diǎn)的權(quán)之和，即例5、求帶權(quán)1,3,4,5,6的最優(yōu)2元樹(shù)及。解：其47例5、求帶權(quán)1,3,4,5,6的最優(yōu)2元樹(shù)及。解：其實(shí)等于的各分支點(diǎn)的權(quán)之和，即最優(yōu)樹(shù)是不唯一的，但算法得到的樹(shù)一定是最優(yōu)樹(shù)。例5、求帶權(quán)1,3,4,5,6的最優(yōu)2元樹(shù)及。解：其48例6、(1)求帶權(quán)為2,3,5,7,8,9的最優(yōu)2元樹(shù)，解：(2)例6、(1)求帶權(quán)為2,3,5,7,8,9的最優(yōu)49例6、(1)求帶權(quán)為2,3,5,7,8,9的最2優(yōu)元樹(shù)，解：(3)例6、(1)求帶權(quán)為2,3,5,7,8,9的最250例6、(1)求帶權(quán)為2,3,5,7,8,9的最2優(yōu)元樹(shù)，解：(4)有___片樹(shù)葉。例6、(1)求帶權(quán)為2,3,5,7,8,9的最251例6、(1)求帶權(quán)為2,3,5,7,8,9的最2優(yōu)元樹(shù)，解：(5)有__個(gè)2度頂點(diǎn)，__個(gè)3度頂點(diǎn)，__個(gè)4度頂點(diǎn)。例6、(1)求帶權(quán)為2,3,5,7,8,9的最2524、求最佳前綴碼。(了解)最優(yōu)2元樹(shù)的用途之一是求最佳前綴碼。在通訊中，我們常用0和1的符號(hào)串作為英文字母的傳送信息，26個(gè)英文字母被使用的頻率往往是不同的。為了使整個(gè)信息的長(zhǎng)度盡可能短，自然希望用較短的符號(hào)串去表示使用頻率高的英文字母，用較長(zhǎng)的符號(hào)串表示使用頻率低的英文字母。

4、求最佳前綴碼。(了解)最優(yōu)2元樹(shù)的用途之一是求最佳前綴碼534、求最佳前綴碼。(了解)最優(yōu)元樹(shù)的用途之一是求最佳前綴碼。為了使編碼在使用中既快速又準(zhǔn)確，可以用求

最優(yōu)2元樹(shù)的算法解決這個(gè)問(wèn)題。4、求最佳前綴碼。(了解)最優(yōu)元樹(shù)的用途之一是求最佳前綴碼。54第九章

小結(jié)與例題第九章小結(jié)與例題55一、無(wú)向樹(shù)及生成樹(shù)。1、基本概念。無(wú)向樹(shù)；樹(shù)葉，分支點(diǎn)；森林；平凡樹(shù)；生成樹(shù)，最小生成樹(shù)。2、運(yùn)用。(1)無(wú)向樹(shù)的六個(gè)等價(jià)定義。(2)畫(huà)頂點(diǎn)數(shù)為的所有非同構(gòu)的無(wú)向樹(shù)。一、無(wú)向樹(shù)及生成樹(shù)。1、基本概念。無(wú)向樹(shù)；樹(shù)葉，分支點(diǎn)；森林56一、無(wú)向樹(shù)及生成樹(shù)。1、基本概念。無(wú)向樹(shù)；樹(shù)葉，分支點(diǎn)；森林；平凡樹(shù)；生成樹(shù)，最小生成樹(shù)。2、運(yùn)用。(3)根據(jù)握手定理及樹(shù)的某些性質(zhì)，求頂點(diǎn)數(shù)或某些頂點(diǎn)的度數(shù)。(4)求生成樹(shù)，最小生成樹(shù)。一、無(wú)向樹(shù)及生成樹(shù)。1、基本概念。無(wú)向樹(shù)；樹(shù)葉，分支點(diǎn)；森林57二、根樹(shù)及其應(yīng)用。1、基本概念。有向樹(shù)；根樹(shù)；樹(shù)根，內(nèi)點(diǎn)，樹(shù)葉，分支點(diǎn)；頂點(diǎn)的層數(shù)與樹(shù)高；有序樹(shù)，正則樹(shù)，完全樹(shù)；最優(yōu)二元樹(shù)。二、根樹(shù)及其應(yīng)用。1、基本概念。有向樹(shù)；根樹(shù)；樹(shù)根，內(nèi)點(diǎn)，樹(shù)58二、根樹(shù)及其應(yīng)用。2、運(yùn)用。(1)按定義畫(huà)出等等。元樹(shù)，元正則樹(shù)，元有序樹(shù)(2)利用算法求最優(yōu)二元樹(shù)。二、根樹(shù)及其應(yīng)用。2、運(yùn)用。(1)按定義畫(huà)出等等。元樹(shù)，元59例1、畫(huà)出滿足下列要求的所有非同構(gòu)的無(wú)向樹(shù)。(1)2個(gè)頂點(diǎn)(2)3個(gè)頂點(diǎn)(3)4個(gè)頂點(diǎn)例1、畫(huà)出滿足下列要求的所有非同構(gòu)的無(wú)向樹(shù)。(1)2個(gè)頂點(diǎn)60例1、畫(huà)出滿足下列要求的所有非同構(gòu)的無(wú)向樹(shù)。(4)5個(gè)頂點(diǎn)例1、畫(huà)出滿足下列要求的所有非同構(gòu)的無(wú)向樹(shù)。(4)5個(gè)頂點(diǎn)61例2、若無(wú)向圖中有個(gè)頂點(diǎn)，條邊，則為樹(shù)。這個(gè)命題正確嗎？解：命題不正確。反例：例2、若無(wú)向圖中有個(gè)頂點(diǎn)，條邊，則為樹(shù)。這個(gè)命題正確嗎？解：62例3、設(shè)連通圖如下圖所示，分別求出它們的所有非同構(gòu)的生成樹(shù)。解：的生成樹(shù)有：例3、設(shè)連通圖如下圖所示，分別求出它們的所有非同構(gòu)的生成樹(shù)。63例3、設(shè)連通圖如下圖所示，分別求出它們的所有非同構(gòu)的生成樹(shù)。解：的生成樹(shù)有：例3、設(shè)連通圖如下圖所示，分別求出它們的所有非同構(gòu)的生成樹(shù)。64例4、一棵樹(shù)有個(gè)頂點(diǎn)的度數(shù)為2，個(gè)頂點(diǎn)的