北大離散數學chap9

第九章

樹第一節(jié)

無向樹及生成樹

2021/3/111內容：無向樹，生成樹。重點：1、無向樹的定義(包括等價定義)，2、無向樹的性質，3、生成樹的定義，由連通圖構造最小生成樹的方法。本章中所談回路均指簡單回路或初級回路。2021/3/112一、無向樹。1、無向樹——連通且不含回路的無向圖。無向樹簡稱樹，常用表示。平凡樹——平凡圖。森林

——連通分支數大于等于2，且每個連通分支都是樹的無向圖。2021/3/113例1、2021/3/114例1、2021/3/1152、樹的六個等價定義。(1)連通且不含回路。(2)的每對頂點間具有唯一的路徑。(3)連通且。(4)無回路且。定理：設，，，則以下命題等價。2021/3/1162、樹的六個等價定義。(5)無回路，但在中任兩個不相鄰的頂點之間增加一條邊，就形成唯一的一條初級回路。(6)是連通的，但刪除任何一條邊后，就不連通了。2021/3/1173、性質。(1)樹中頂點數與邊數的關系：。(2)定理：非平凡樹至少2片樹葉。證明：設為階非平凡樹，設有片樹葉，則有個頂點度數大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片葉。2021/3/118例2、畫出所有的6個頂點的非同構的樹。解：所要畫的樹有6個頂點，則邊數為5，因此6個頂點的度數之和為10，可以產生以下五種度數序列：(1)2021/3/119例2、畫出所有的6個頂點的非同構的樹。解：所要畫的樹有6個頂點，則邊數為5，因此6個頂點的度數之和為10，可以產生以下五種度數序列：(2)2021/3/1110例2、畫出所有的6個頂點的非同構的樹。解：所要畫的樹有6個頂點，則邊數為5，因此6個頂點的度數之和為10，可以產生以下五種度數序列：(3)2021/3/1111例2、畫出所有的6個頂點的非同構的樹。解：所要畫的樹有6個頂點，則邊數為5，因此6個頂點的度數之和為10，可以產生以下五種度數序列：(4)2021/3/1112例2、畫出所有的6個頂點的非同構的樹。解：所要畫的樹有6個頂點，則邊數為5，因此6個頂點的度數之和為10，可以產生以下五種度數序列：(5)2021/3/1113例3、(1)一棵樹有7片葉，3個3度頂點，其余都是4度頂點，求4度頂點多少個？解：設有個4度頂點，則頂點數，邊數，由握手定理，，解得，故這棵樹有1個4度頂點。2021/3/1114例3、(2)一棵樹有2個4度頂點，3個3度頂點，其余都是樹葉，求這棵樹共有多少個頂點？解：設有片樹葉，則頂點數，邊數，由握手定理，，解得，故頂點總數為個。2021/3/1115二、生成樹。1、定義：設是無向連通圖，是的生成子圖，若是樹，稱是的生成樹。樹枝弦余樹——在中的邊，——不在中的邊，——的所有的弦的集合的導出子圖。2021/3/1116例4、上圖中，(2)是(1)的生成樹，(3)是(2)的余樹。注意：(1)生成樹不唯一，(2)余樹不一定是樹。2021/3/11172、連通圖的性質。設為連通圖，，，(1)至少有一棵生成樹，(2)，(3)設是的生成樹，是的余樹，則中有條邊。已知連通圖，求其生成樹步驟。2021/3/11183、最小生成樹。對于有向圖或無向圖的每條邊附加一個實數，則稱為邊上的權，連同附加在各邊上的實數稱為帶權圖，記為。最小生成樹——各邊權和最小的生成樹。定義：設無向連通帶權圖，是的一棵生成樹，各邊帶權之和稱為的權，記作。2021/3/1119求最小生成樹的方法——避圈法。設階無向連通帶權圖中有條邊，它們帶的權分別為，不妨設，(1)取在中(非環(huán)，若為環(huán)，則棄)。(2)若不與構成回路，取在中，否則棄，再查，繼續(xù)這一過程，直到形成樹為止。2021/3/1120解：例5、求以下連通圖的最小生成樹及。2021/3/1121解：例5、求以下連通圖的最小生成樹及。2021/3/1122解：例5、求以下連通圖的最小生成樹及。2021/3/1123解：例5、求以下連通圖的最小生成樹及。2021/3/1124注意：的最小生成樹可能不唯一，但的不同最小生成樹權的值一樣。2021/3/1125第二節(jié)

根樹及其應用2021/3/1126內容：有向樹，根樹，最優(yōu)二元樹。重點：1、有向樹及根樹的定義，2、家族樹，有序樹，元樹的概念，3、最優(yōu)2元樹的概念及哈夫曼算法。2021/3/1127一、根樹。1、有向樹：一個有向圖，若略去有向邊的方向所得的無向圖為一棵無向樹，則稱為有向樹。2、根樹：一棵非平凡的有向樹，如果有一個頂點的入度為0，其余頂點的入度均為1，則稱此有向樹為根樹。2021/3/1128根樹的頂點樹葉(入度為1，出度為0)分支點樹根(入度為0)內點(入度為1，出度大于0)2021/3/1129例1、2021/3/1130例1、2021/3/11313、樹高。的層數——從樹根到頂點的通路長度，記。樹高——樹中頂點的最大層數，記。2021/3/1132如例1(2)中，2021/3/11334、家族樹。一棵根樹可以看成一棵家族樹。(1)若頂點鄰接到頂點，則稱為的兒子，為的父親，(2)若同為的兒子，則稱為兄弟，(3)若，而可達，則稱為的祖先，為的后代。2021/3/11345、根子樹。樹的根子樹——的非樹根的頂點及其后代導出的子圖。2021/3/1135例2、2021/3/1136二、元樹。1、有序樹——每一層上都規(guī)定次序的根樹。2、元樹——每個分支點至多有個兒子的根樹。元正則樹——每個分支點恰有個兒子的根樹。元有序樹元有序正則樹2021/3/1137二、元樹。元有序完全正則樹注意：2元有序正則樹是最重要的一種元樹。1、有序樹——每一層上都規(guī)定次序的根樹。2、元完全正則樹的層數相同(等于樹高)?！齽t樹，且所有樹葉2021/3/1138例3、2元有序樹2元有序正則樹2021/3/1139例3、2元有序完全正則樹2021/3/11403、最優(yōu)2元樹。(1)的權最優(yōu)2元樹——權最小的2元樹。——中每片樹葉所帶權與其層高乘積的和。記為2021/3/1141例4、下圖中的都是帶權1，3，4，5，6的2元樹，求，，。解：2021/3/1142例4、下圖中的都是帶權1，3，4，5，6的2元樹，求，，。解：2021/3/1143例4、下圖中的都是帶權1，3，4，5，6的2元樹，求，，。解：但不能判定是最優(yōu)2元樹。2021/3/1144(2)求最優(yōu)2元樹的算法。算法：給定實數片樹葉的權)，且(，選連接得一分支點，從中選兩個最小的，連接得一分支點，重復。2021/3/1145例5、求帶權1,3,4,5,6的最優(yōu)2元樹及。解：其實等于的各分支點的權之和，即2021/3/1146例5、求帶權1,3,4,5,6的最優(yōu)2元樹及。解：其實等于的各分支點的權之和，即最優(yōu)樹是不唯一的，但算法得到的樹一定是最優(yōu)樹。2021/3/1147例6、(1)求帶權為2,3,5,7,8,9的最優(yōu)2元樹，解：(2)2021/3/1148例6、(1)求帶權為2,3,5,7,8,9的最2優(yōu)元樹，解：(3)2021/3/1149例6、(1)求帶權為2,3,5,7,8,9的最2優(yōu)元樹，解：(4)有___片樹葉。2021/3/1150例6、(1)求帶權為2,3,5,7,8,9的最2優(yōu)元樹，解：(5)有__個2度頂點，__個3度頂點，__個4度頂點。2021/3/11514、求最佳前綴碼。(了解)最優(yōu)2元樹的用途之一是求最佳前綴碼。在通訊中，我們常用0和1的符號串作為英文字母的傳送信息，26個英文字母被使用的頻率往往是不同的。為了使整個信息的長度盡可能短，自然希望用較短的符號串去表示使用頻率高的英文字母，用較長的符號串表示使用頻率低的英文字母。

2021/3/11524、求最佳前綴碼。(了解)最優(yōu)元樹的用途之一是求最佳前綴碼。為了使編碼在使用中既快速又準確，可以用求

最優(yōu)2元樹的算法解決這個問題。2021/3/1153第九章

小結與例題2021/3/1154一、無向樹及生成樹。1、基本概念。無向樹；樹葉，分支點；森林；平凡樹；生成樹，最小生成樹。2、運用。(1)無向樹的六個等價定義。(2)畫頂點數為的所有非同構的無向樹。2021/3/1155一、無向樹及生成樹。1、基本概念。無向樹；樹葉，分支點；森林；平凡樹；生成樹，最小生成樹。2、運用。(3)根據握手定理及樹的某些性質，求頂點數或某些頂點的度數。(4)求生成樹，最小生成樹。2021/3/1156二、根樹及其應用。1、基本概念。有向樹；根樹；樹根，內點，樹葉，分支點；頂點的層數與樹高；有序樹，正則樹，完全樹；最優(yōu)二元樹。2021/3/1157二、根樹及其應用。2、運用。(1)按定義畫出等等。元樹，元正則樹，元有序樹(2)利用算法求最優(yōu)二元樹。2021/3/1158例1、畫出滿足下列要求的所有非同構的無向樹。(1)2個頂點(2)3個頂點(3)4個頂點2021/3/1159例1、畫出滿足下列要求的所有非同構的無向樹。(4)5個頂點2021/3/1160例2、若無向圖中有個頂點，條邊，則為樹。這個命題正確嗎？解：命題不正確。反例：2021/3/1161例3、設連通圖如下圖所示，分別求出它們的所有非同構的生成樹。解：的生成樹有：2021/3/1162例3、設連通圖如下圖所示，分別求出它們的所有非同構的生成樹。解：的生成樹有：2021/3/1163例4、一棵樹有個頂點的度數為2，個頂點的度數為3，···，個頂點的度數為，而其余的頂點都是樹葉。求該樹的樹葉數。解：設有片樹葉，依握手定理及樹的性質，得解得：2021/3/1164解：不一定，反例：例5、一個有向圖，僅有一個頂點入度為0，其余頂點的入度均為1，一定是根樹嗎？2021/3/1165例6、設為二元正則樹，為邊數，為樹葉數。證明：，其中。證法一：設中頂點數為，分支點數為，由二元正則樹的定義，知由以上三個式子，得。2021/3/1166例6、