7-7 樹與生成樹.ppt

1、樹與生成樹,中國海洋大學(xué) 計算機系,主要內(nèi)容,無向樹及其相關(guān)概念 生成樹 基本回路與基本回路系統(tǒng) 基本割集與基本割集系統(tǒng) 最小生成樹 學(xué)習(xí)要點與基本要求 實例分析,無向樹的定義,定義7-7.1 一個連通且無回路的無向圖稱為樹。 樹葉：樹中度數(shù)為1的結(jié)點； 分枝點：度數(shù)大于1的結(jié)點 森林：每個連通分支都是樹的無向圖。,樹的6個等價定義,定理7-7.1 給定圖T，以下關(guān)于樹的定義是等價的。 （1）無回路的連通圖; （2） 無回路且e=v1，其中e是邊數(shù)，v是結(jié)點數(shù); （3） 連通且e=v1; （4）無回路, 但增加一條新邊，得到一個且僅有一個包含新邊的回路。 （5）連通且每條邊均為橋; （6）G中

2、任意兩個結(jié)點之間存在惟一的路徑;,Go,(1)(2)的證明,如果T是無回路的連通圖，則G中無回路且e=v1，其中e是邊數(shù)，v是結(jié)點數(shù) 證明 歸納法。 當(dāng)v=2時，因為T連通無回路， 所以只有e=1，故e=v-1成立。 假設(shè)v=k-1時命題成立，當(dāng)v=k時， 因T是無回路且連通，則至少有一個度為1的結(jié)點u， 設(shè)與其關(guān)聯(lián)的邊為(u,w)，刪去u，得到一個k-1個結(jié)點 的連通無向圖T，,(1)(2)的證明（續(xù)）,由歸納假設(shè)可知， T的邊數(shù)e=v-1=(k-1)-1=k-2。 再將結(jié)點u及(u,w)放入原位，恢復(fù)到圖T， 那么T的邊數(shù) e=e+1=(k-2)+1=k-1， 結(jié)點數(shù)v=v+1=k， 故e

3、=v-1成立。,return,(2)(3)的證明,如果T中無回路且e=v1，其中e是邊數(shù)，v是結(jié)點數(shù)，則連通且e=v1; 只須證明T是連通的。 證明 設(shè)T有k個連通分枝T1,Tk(k2），Ti有vi個結(jié) 點,ei條邊，因為Ti連通無回路，所以有 ei =vi-1，v=v1+v2+vk e=e1+e2+ek=(v1-1)+(v2-1)+(vk-1)=v-k 因為e=v-1，所以k=1，故T是連通的。,return,(3)(4)的證明,如果T連通且e=v1，則T中無回路, 但增加一條新邊，得到一個且僅有一個包含新邊的回路。 證明 歸納法。 當(dāng)v=2時，e=v-1=1，必?zé)o回路，如果增加一邊得到且僅

4、得到一個回路。 設(shè)v=k-1時命題成立?？疾靨=k時的情況。 因為T是連通的，所以每個結(jié)點u有deg(u)1， 下面證明至少有一個結(jié)點u0使deg(u0)=1。 若不存在，則每個結(jié)點的度至少為2，所以2v2e，即v e，這與e=v-1矛盾。,(3)(4)的證明,刪去u0及其關(guān)聯(lián)的邊，得到含有k-1個結(jié)點的圖T， T連通且e=v1。由歸納假設(shè)知T無回路。 在T中加入u0及其關(guān)聯(lián)的邊恢復(fù)到T，則T無回路。 若在T中增加一條邊(ui,uj)， 因為T連通，則在T中存在一條從ui到uj的路， 那么這條路與新加入的邊(ui,uj)構(gòu)成回路， 而且這個回路是唯一的。 若不唯一，刪掉邊(ui,uj)邊,T中

5、必有回路，矛盾。,return,(4) (5)的證明,如果T中無回路, 但增加一條新邊，得到一個且僅有一個包含新邊的回路，則T連通且每條邊均為橋。 證明 反證法。 假設(shè)T不連通， 則存在結(jié)點ui與uj，在ui和uj之間沒有路， 所以增加邊(ui,uj)不會產(chǎn)生回路，與已知矛盾。 由于T無回路，故刪掉任意條邊e都使T-e為非連通， 所以T中每條邊都是橋。,return,(5) (6)的證明,如果T連通且每條邊均為橋，則T中任意兩個結(jié)點之間存在惟一的路徑。 證明 由T是連通的可知，任意兩個結(jié)點間有一條路， 若存在兩點它們之間有多于一條的路， 則T中必有回路， 刪去該回路上任一邊， 圖仍是連通的，

6、與T中每條邊都是橋矛盾。,return,(6) (1)的證明,如果T中任意兩個結(jié)點之間存在惟一的路徑，則T是無回路的連通圖。 證明 因為任意兩結(jié)點間有唯一條路，則圖T必連通。 若T有回路， 則在回路上任意兩結(jié)點間有兩條路， 與已知矛盾。,return,無向樹的性質(zhì),定理7-7.2 任一棵樹中至少有兩片樹葉。 證 設(shè)T=是無向樹，其中|V|=v，|E|=e 設(shè)T有x片樹葉，則剩余的v-x各結(jié)點的度均大于等于2， 由握手定理及定理7-7.1可知，,解上式可得 x2.,定理得證。,關(guān)于無向樹計算的實例,例 一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是3度結(jié)點，問T有幾個結(jié)點。 解 設(shè)有n

7、個結(jié)點，則 5+32+(n-8)3=2(n-1) 得n=11,實例,例 下面兩個正整數(shù)序列中，哪個能充當(dāng)無向樹的度數(shù)序列？若能畫出2棵非同構(gòu)的無向樹。 （1）1,1,1,1,2,3,3,4 （2）1,1,1,1,2,2,3,3 解 （1）不可以，因為所有度數(shù)之和等于16，而結(jié)點數(shù)為8，假設(shè)可以構(gòu)成樹，則度數(shù)之和應(yīng)為14，所以不可以。 （2）可以。,實例,例 設(shè)G為n（n5）階簡單圖，證明G或G的補圖中必含圈。 證 設(shè)簡單圖G和其補圖的邊數(shù)分別為m和m，則 m+m= n(n-1)/2 根據(jù)鴿巢原理，G與其補圖必有一個邊數(shù) n(n-1)/4 ， 不妨設(shè)G的邊數(shù)m n(n-1)/4 ，下面證G中必含

8、有圈。 假設(shè)G中沒有圈，設(shè)G有w個連通分支，則每個連通分支 都是樹，mi=ni-1，i=1,w，mi,ni分別為第i個連通分支 的邊數(shù)與階數(shù)，所以有,（接上頁）,得不等式,整理得,解得 1n4， 與n5矛盾。,生成樹,定義7-7.2 若圖G的生成子圖是一棵樹，則該樹稱為G的生成樹。 生成樹T的樹枝: G在T中的邊 生成樹T的弦: G不在T中的邊,生成樹T的補 （或余樹）: 所有弦的集合的導(dǎo)出子圖,注意： 不一定連通, 也不一定不含回路.,舉例,例 如下圖，T=e1,e6,e7,e4,e3，,黑線表示生成樹，紅線構(gòu)成樹的補。,=e2,e5,e8,余樹是非連通的，無回路,余樹是非連通的，有回路,舉

9、例,例 設(shè)T是6階無向簡單圖G的一棵生成樹，討論下面的問題： (1) 當(dāng)G的邊數(shù)e=9時，T的補是G的生成樹嗎？ (2) 當(dāng)G的邊數(shù)e=12時，T的補是G的生成樹嗎？ (3) 當(dāng)G的邊數(shù)e=10時，T的補可能有哪幾種情況？ 解 對于樹T，e=v-1，而任何ev或ev-1的圖都不是樹 （1）T的補的邊數(shù)為9-5=4，所以不可能是樹。 （2） T的補的邊數(shù)為12-5=7，也不可能是樹。 （3）有兩種情況：T的補是生成樹； T的補不連通且含圈。,生成樹的存在性定理,定理7-7.3 連通圖至少有一棵生成樹。 證 用破圈法. 若圖中無圈, 則圖本身就是生成樹. 否則刪去圈上的任一條邊, 這不破壞連通性,

10、 重復(fù)進(jìn)行直到無圈為止,剩下的圖是一棵生成樹. 注意：連通圖的生成樹不唯一。,舉例,幾個結(jié)論,設(shè)n階無向連通圖有m條邊, 則mn1. 設(shè)n階無向連通圖有m條邊, 則它的生成樹的補 有mn+1條邊. m-n+1稱為連通圖G的秩。 小練習(xí)： 含有n個結(jié)點且至少有n條邊的無向簡單圖，必有回路。,基本回路,定理7-7.4 一條回路和任何一棵生成樹的補至少有一條公共邊。 證明 若有一條回路和一棵生成樹的補無公共邊， 則回路必在生成樹中， 這是不可能的， 故必有公共邊。,基本回路的定義,定義 設(shè)T是n階m條邊的無向連通圖G的一棵生成樹，設(shè)e1, e2, , emn+1為T的弦. 設(shè)Cr為T添加弦er產(chǎn)生的

11、G中惟一的圈(由er和樹枝組成), 稱Cr為對應(yīng)弦er的基本回路或基本圈, r=1, 2, , mn+1. 稱C1, C2, , Cmn+1為對應(yīng)T的基本回路系統(tǒng). 求基本回路的算法: 設(shè)弦e=(u,v), 先求T中u到v的路徑uv, 再并上弦e, 即得對應(yīng)e的基本回路.,基本割集,定理7-7.5 一個邊割集和任何生成樹至少有一條公共邊。 證明 若一個邊割集與一個生成樹無公共邊， 則該邊割集必不屬于生成樹， 那么刪掉該邊割集，圖仍然連通， 矛盾。,基本割集（續(xù)）,定義 設(shè)T是n階連通圖G的一棵生成樹, e1, e2, , en1為T的樹枝，Si是G的只含樹枝ei, 其他邊都是弦的割集, 稱Si

12、為對應(yīng)生成樹T由樹枝ei生成的基本割集, i=1, 2, , n1. 稱S1, S2, , Sn1為對應(yīng)T的基本割集系統(tǒng). 求基本割集的算法: 設(shè)e為生成樹T的樹枝, Te由兩棵子樹T1與T2組成, 令Se=e | eE(G)且e的兩個端點分別屬于T1與T2 ，則Se為e對應(yīng)的基本割集.,舉例,例 圖中紅邊為一棵生成樹, 求對應(yīng)它的基本回路系統(tǒng) 與基本割集系統(tǒng),解 弦e,f,g對應(yīng)的基本回路分別為 Ce=e,b,c, Cf=f,a,b,c, Cg=g,a,b,c,d, C基=Ce, Cf, Cg. 樹枝a,b,c,d對應(yīng)的基本割集分別為 Sa=a, f, g, Sb=b, e, f, g, S

13、c=c, e, f g, Sd=d, g, S基=Sa, Sb, Sc, Sd.,最小生成樹,設(shè)G是具有n個結(jié)點的連通圖，對于G的每一條邊e指定一個正實數(shù)C(e)，稱作邊e的權(quán). 圖連同附加在邊上的權(quán)稱作帶權(quán)圖, 記作G=. 設(shè)G是G的子圖, G的權(quán)C(G)：G所有邊的權(quán)之和稱作。 設(shè)T是G的生成樹， 樹權(quán)C(T)：T的所有邊權(quán)之和。 定義7-7.3 在圖G的所有生成樹中，樹權(quán)最小的那棵生成樹，稱作最小生成樹。,最小生成樹的算法,求最小生成樹的算法避圈法 (Kruskal) 設(shè)G=, 將邊按權(quán)從小到大排序：e1, e2, , em. (1) 取最小權(quán)邊e1，置邊數(shù)i1； (2) i=n-1結(jié)束

14、，否則轉(zhuǎn)(3)； (3)設(shè)已選擇邊 e1, e2, , ei，在G中選取不同于e1, e2, , ei的邊ei+1，使e1, e2, , ei, ei+1中無回路且ei+1是滿足此條件的最小邊。 (4) ii+1，轉(zhuǎn)(2).,Kruskal的證明,證明 設(shè)T0是上述算法構(gòu)造的一個圖， 它的結(jié)點是G的結(jié)點，T0的邊是e1,e2,e3,en-1。 根據(jù)構(gòu)造過程，T0無回路且邊數(shù)為n-1， 所以T0是樹，且為G的生成樹。 下面證明T0是最小生成樹。 假設(shè)G的最小生成樹是T， (1) 如果T與T0相同，則T0是最小生成樹。 (2) 若T與T0不同，則必存在一條邊ei+1T0且ei+1T， 而e1,e2,eiT。,Kruskal的證明（續(xù)）,因為T是樹，所以T+ ei+1必存在回路r. 由于T0是樹，所以r中必存在邊f(xié)T0且fT 對于樹T，以ei+1 代替f得到新樹T， 即在T+ ei+1中刪除f，得到樹T，所以有 C(T)=C(T)+C(ei+1)-C(f) 因為C(T) C(T)，所以C(ei+1)-C(f) 0，因此 C(ei+1) C(f) 因為e1,e2,ei+1是T0的邊，根據(jù)T0的構(gòu)造可知 C(ei+1) C(f) ，所以C(ei+1) =C(f) ，故C(T)=C(T),Kruskal的證明（續(xù)）,因此T也是G的一棵最小生成樹， 但是T與T0的