離散數(shù)學(xué)——樹ppt課件.ppt

1、離 散 數(shù) 學(xué),本章說明,樹是圖論中重要內(nèi)容之一。 本章所談回路均指初級回路（圈）或簡單回路，不含復(fù)雜回路（有重復(fù)邊出現(xiàn)的回路）。,2,16.1 無向樹及其性質(zhì),定義16.1 無向樹連通無回路的無向圖，簡稱樹，用T表示。 平凡樹平凡圖。 森林若無向圖G至少有兩個連通分支（每個都是樹）。 樹葉無向圖中懸掛頂點。 分支點度數(shù)大于或等于2的頂點。 舉例如圖為九個頂點的樹。,3,定理16.1 設(shè)G是n階m條邊的無向圖，則下面各命題是等價的： （1）G是樹。 （2）G中任意兩個頂點之間存在唯一的路徑。 （3）G中無回路且mn1。 （4）G是連通的且mn1。 （5）G是連通的且G中任何邊均為橋。 （6）G

2、中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈。,無向樹的等價定義,4,(1)(2),如果G是樹，則G中任意兩個頂點之間存在唯一的路徑。,存在性。 由G的連通性及定理14.5的推論（在n階圖G中，若從頂點vi到vj(vivj)存在通路，則vi到vj 一定存在長度小于等于n-1的初級通路(路徑)）可知， u,vV，u與v之間存在路徑。 唯一性（反證法）。 若路徑不是唯一的，設(shè)1與2都是u到v的路徑， 易知必存在由1和2上的邊構(gòu)成的回路， 這與G中無回路矛盾。,5,(2)(3),如果G中任意兩個頂點之間存在唯一的路徑， 則G中無回路且mn-1。,首先證明 G中

3、無回路。 若G中存在關(guān)聯(lián)某頂點v的環(huán)， 則v到v存在長為0和1的兩條路經(jīng) (注意初級回路是路徑的特殊情況)， 這與已知矛盾。 若G中存在長度大于或等于2的圈， 則圈上任何兩個頂點之間都存在兩條不同的路徑， 這也與已知矛盾。,6,(2)(3),如果G中任意兩個頂點之間存在唯一的路徑， 則G中無回路且mn-1。,其次證明 mn-1。（歸納法） n1時，G為平凡圖，結(jié)論顯然成立。 設(shè)nk(k1)時結(jié)論成立， 當(dāng)n=k+1時，設(shè)e(u,v)為G中的一條邊， 由于G中無回路，所以G-e為兩個連通分支G1、G2。 設(shè)ni、mi分別為Gi中的頂點數(shù)和邊數(shù)，則nik ，i1,2， 由歸納假設(shè)可知mini-1，

4、于是 mm1+m2+1n1-1+n2-1+1n1+n2-1n-1。,7,只需證明G是連通的。（采用反證法） 假設(shè)G是不連通的，由s(s2)個連通分支G1,G2,Gs組成，并且Gi中均無回路，因而Gi全為樹。 由(1)(2)(3)可知，mini-1。于是，,由于s2，與mn-1矛盾。,(3)(4),如果G中無回路且mn-1，則G是連通的且mn -1。,8,如果G是連通的且mn1，則G是連通的且G中任何邊均為橋。,只需證明G中每條邊均為橋。 eE，均有|E(G-e)|n-1-1n-2， 由習(xí)題十四題49（若G是n階m條邊的無向連通圖，則mn-1）可知，G-e已不是連通圖， 所以，e為橋。,(4)(

5、5),9,如果G是連通的且G中任何邊均為橋，則G中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈。,因為G中每條邊均為橋，刪掉任何邊，將使G變成不連通圖，所以，G中沒有回路，也即G中無圈。 又由于G連通，所以G為樹，由(1) (2)可知， u,vV，且uv，則u與v之間存在唯一的路徑， 則(u,v)（(u,v)為加的新邊）為G中的圈， 顯然圈是唯一的。,(5)(6),10,如果G中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈，則G是樹。,只需證明G是連通的。 u,vV，且uv，則新邊(u,v)G產(chǎn)生唯一的圈C， 顯然有C

6、 -(u,v)為G中u到v的通路，故uv， 由u,v的任意性可知，G是連通的。,(6)(1),11,定理16.2 設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉。,設(shè)T有x片樹葉，由握手定理及定理16.1可知，,證明,由上式解出x2。,無向樹的性質(zhì),12,例16.1,例16.1 畫出6階所有非同構(gòu)的無向樹。 解答 設(shè)Ti是6階無向樹。 由定理16.1可知，Ti的邊數(shù)mi5， 由握手定理可知，dTi(vj)10，且(Ti)1，(Ti)5。 于是Ti的度數(shù)列必為以下情況之一。,(1) 1，1，1，1，1，5 (2) 1，1，1，1，2，4 (3) 1，1，1，1，3，3 (4) 1，1，1，2，2

7、，3 (5) 1，1，2，2，2，2,(4)對應(yīng)兩棵非同構(gòu)的樹， 在一棵樹中兩個2度頂點相鄰， 在另一棵樹中不相鄰， 其他情況均能畫出一棵非同構(gòu)的樹。,13,例16.1,人們常稱只有一個分支點，且分支點的度數(shù)為n-1的n(n3)階無向樹為星形圖，稱唯一的分支點為星心。,14,例16.2,例16.2 7階無向圖有3片樹葉和1個3度頂點，其余3個頂點的度數(shù)均無1和3。試畫出滿足要求的所有非同構(gòu)的無向樹。 解答 設(shè)Ti為滿足要求的無向樹，則邊數(shù)mi6，于是 d(vj)12e+3+d(v4)+d(v5)+d(v6)。 由于d(vj)1d(vj)3，而且d(vj)1且d(vj)6，j4,5,6， 可知d

8、(vj)2，j4,5,6。于是Ti 的度數(shù)列為 1，1，1，2，2，2，3 由度數(shù)列可知，Ti中有一個3度頂點vi，vi的鄰域N(vi)中有3個頂點，這3個頂點的度數(shù)列只能為以下三種情況之一： 1,1,21,2,22,2,2 設(shè)它們對應(yīng)的樹分別為T1，T2，T3。此度數(shù)列只能產(chǎn)生這三棵非同構(gòu)的7階無向樹。,15,例16.2,16,例題,例題 已知無向樹T中，有1個3度頂點，2個2度頂點，其余頂點全是樹葉，試求樹葉數(shù)，并畫出滿足要求的非同構(gòu)的無向樹。 解答 設(shè)有x片樹葉，于是結(jié)點總數(shù)為 n1+2+x3+x 由握手定理和樹的性質(zhì)mn1可知， 2m2(n1)2(2+x) 13+22+x 解出x3，故

9、T有3片樹葉。 故T的度數(shù)應(yīng)為1、1、1、2、2、3。,17,例題 已知無向樹T有5片樹葉，2度與3度頂點各1個，其余頂點的度數(shù)均為4，求T的階數(shù)n，并畫出滿足要求的所有非同構(gòu)的無向樹。 解答設(shè)T的階數(shù)為n, 則邊數(shù)為n1，4度頂點的個數(shù)為n7。 由握手定理得 2m = 2(n1) = 51+21+31+4(n7) 解出n = 8，所以4度頂點為1個。 故T的度數(shù)列為1、1、1、1、1、2、3、4。,例題,18,小節(jié)結(jié)束,例題,19,16.2 生成樹,定義16.2 設(shè)G為無向圖， （1）T為G的樹T是G的子圖并且是樹。 （2）T為G的生成樹T是G的生成子圖并且是樹。 （3）e為T的樹枝設(shè)T是G

10、的生成樹，eE(G)，若eE(T)。 （4）e為T的弦設(shè)T是G的生成樹，eE(G)，若eE(T)。 （5）生成樹T的余樹導(dǎo)出子圖GE(G)-E(T) 。記作,20,注意： 不一定連通，也不一定不含回路。,說明,21,定理16.3 無向圖G具有生成樹當(dāng)且僅當(dāng)G連通。 證明必要性，顯然。 充分性（破圈法）。 若G中無回路，G為自己的生成樹。 若G中含圈，任取一圈，隨意地刪除圈上的一條邊， 若再有圈再刪除圈上的一條邊，直到最后無圈為止。 易知所得圖無圈(當(dāng)然無回路)、連通且為G的生成子圖， 所以為G的生成樹。,生成樹的存在條件,22,最小生成樹,定義16.5 設(shè)T是無向連通帶權(quán)圖G的一棵生成樹， T

11、的各邊權(quán)之和稱為T的權(quán)，記作W(T)。 G的所有生成樹中權(quán)最小的生成樹稱為G的最小生成樹。 求最小生成樹的算法（避圈法(Kruskal)） (1)設(shè)n階無向連通帶權(quán)圖G有m條邊。不妨設(shè)G中沒有環(huán)（否則，可以將所有的環(huán)先刪去），將m條邊按權(quán)從小到大排序：e1,e2,em。 (2)取e1在T中。 (3)依次檢查e2,em ，若ej(j2)與已在T中的邊不構(gòu)成回路，取ej也在T中，否則棄去ej。 (4)算法停止時得到的T為G的最小生成樹為止。,23,例16.3,例16.3 求下圖所示兩個圖中的最小生成樹。,W(T1)6,W(T2)12,24,例題,例如 求所示圖的一棵最小生成樹。,解答,最小生成樹

12、W(T)=38,小節(jié)結(jié)束,25,16.3 根樹及其應(yīng)用,設(shè)D是有向圖，若D的基圖是無向樹，則稱D為有向樹。 在所有的有向樹中，根樹最重要，所以我們只討論根樹。 二叉樹的應(yīng)用,26,根樹的定義,定義16.6 T是n(n2)階有向樹， (1) T為根樹 T中有一個頂點入度為0，其余頂點的入度均為1 (2) 樹根入度為0的頂點 (3) 樹葉入度為1，出度為0的頂點 (4) 內(nèi)點入度為1，出度不為0的頂點 (5) 分支點樹根與內(nèi)點的總稱 (6) 頂點v的層數(shù)從樹根到v的通路長度 (7) 樹高T中層數(shù)最大頂點的層數(shù) (8) 根樹平凡樹,27,根樹的畫法,樹根放上方，省去所有有向邊上的箭頭。,樹葉8片 內(nèi)

13、點 6個 分支點 7個 高度 5,28,家族樹,常將根樹看成家族樹，家族中成員之間的關(guān)系如下定義。 定義16.7 設(shè)T為一棵非平凡的根樹， vi、vjV(T)，若vi可達(dá)vj，則稱vi為vj的祖先，vj為vi的后代。 若vi鄰接到vj（即E(T)），則稱vi為vj的父親，而vj為vi的兒子。 若vj、vk的父親相同，則稱vj與vk是兄弟。 定義16.8 設(shè)v為根樹T中任意一頂點，稱v及其后代的導(dǎo)出子圖為以v為根的根子樹。,29,根樹的分類,(1)設(shè)T為根樹，若將T中層數(shù)相同的頂點都標(biāo)定次序， 則稱T為有序樹。 (2)分類：根據(jù)根樹T中每個分支點兒子數(shù)以及是否有序 r叉樹每個分支點至多有r個兒子

14、 r叉有序樹r叉樹是有序的 r叉正則樹每個分支點恰有r個兒子 r叉正則有序樹r叉正則樹是有序的 r叉完全正則樹樹葉層數(shù)均為樹高的r叉正則樹 r叉完全正則有序樹r叉完全正則樹是有序的,30,最優(yōu)二叉樹,定義16.9 設(shè)2叉樹T有t片樹葉v1, v2, , vt，權(quán)分別為w1, w2, , wt，稱 為T的權(quán)，其中l(wèi)(vi)是vi的層數(shù)，在所有有t片樹葉、帶權(quán)w1, w2, , wt的2叉樹中，權(quán)最小的2叉樹稱為最優(yōu)2叉樹。,31,舉例,下圖所示的三棵2叉樹T1,T2,T3都是帶權(quán)為2、2、3、3、5的2叉樹。,W(T1)=22+22+33+53+32=38 W(T2)=34+54+33+22+2

15、1=47 W(T3)=33+33+52+22+22=36,32,求最優(yōu)樹的算法(Huffman算法),給定實數(shù)w1, w2, , wt，且w1w2 wt。 連接權(quán)為w1, w2的兩片樹葉，得一個分支點，其權(quán)為w1+w2。 在w1+w2, w3, , wt中選出兩個最小的權(quán)，連接它們對應(yīng)的頂點（不一定是樹葉），得新分支點及所帶的權(quán)。 重復(fù) ，直到形成t1個分支點、t片樹葉為止。,33,算法舉例,例如：求帶權(quán)為1、1、2、3、4、5的最優(yōu)樹。,解答,W(T)=38,34,(1)最佳前最碼的定義 定義16.10 設(shè)1, 2, , n-1, n是長度為n的符號串， 稱其子串1, 12, , 12n1

16、分別為該字符串的長度為1,2, ,n的前綴。 設(shè)A=1, 2, , m為一個符號串集合，若對于任意的i, jA，ij，i, j互不為前綴，則稱A為前綴碼。 若i(i=1,2,m)中只出現(xiàn)0與1兩個符號，則稱A為二元前綴碼。 (2)如何產(chǎn)生二元前綴碼？ 定理16.6 由一棵給定的2叉正則樹，可以產(chǎn)生唯一的一個二元前綴碼。,最佳前綴碼,35,方法： 將每個分支點引出的兩條邊分別標(biāo)上0和1。 結(jié)果： 圖所示樹產(chǎn)生的前綴碼為00, 10, 11, 011, 0100, 0101。,36,用Huffman算法產(chǎn)生最佳前綴碼,例16.6 在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：1

17、5% 3：10% 4：10% 5：10% 6： 5% 7： 5% 求傳輸它們的最佳前綴碼？ 求傳輸10n（n2）個按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少個二進(jìn)制數(shù)字？ 若用等長的（長為3）的碼字傳輸需要多少個二進(jìn)制數(shù)字？,37,解答,以100乘各頻率為權(quán)，并按小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25。產(chǎn)生的最優(yōu)樹如下。, 0 01 1 11 2 001 3 100 4 101 5 0001 6 00000 7 00001,傳100個按比例出現(xiàn)的八進(jìn)制數(shù)字所需二進(jìn)制數(shù)字個數(shù)W(T)=285 ，所以傳10n(n2)個所用二進(jìn)制數(shù)字應(yīng)為2.8510n。 用等長碼（長為3）應(yīng)該用310n個數(shù)字。,38,由于在每一步選擇兩個最小的權(quán)的選法不唯一。 因為兩個權(quán)對應(yīng)的頂點所放左右位置不同。 畫出的最優(yōu)樹可能不同，最佳前綴碼并不唯一，但有一點是共同的，就是它們的權(quán)應(yīng)該相等，即它們都應(yīng)該是最優(yōu)樹。,說明,39,3、