7-7 樹(shù)與生成樹(shù).ppt

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

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

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

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

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

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

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

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

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

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

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

12、為對(duì)應(yīng)生成樹(shù)T由樹(shù)枝ei生成的基本割集, i=1, 2, , n1. 稱(chēng)S1, S2, , Sn1為對(duì)應(yīng)T的基本割集系統(tǒng). 求基本割集的算法: 設(shè)e為生成樹(shù)T的樹(shù)枝, Te由兩棵子樹(shù)T1與T2組成, 令Se=e | eE(G)且e的兩個(gè)端點(diǎn)分別屬于T1與T2 ，則Se為e對(duì)應(yīng)的基本割集.,舉例,例 圖中紅邊為一棵生成樹(shù), 求對(duì)應(yīng)它的基本回路系統(tǒng) 與基本割集系統(tǒng),解 弦e,f,g對(duì)應(yīng)的基本回路分別為 Ce=e,b,c, Cf=f,a,b,c, Cg=g,a,b,c,d, C基=Ce, Cf, Cg. 樹(shù)枝a,b,c,d對(duì)應(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ù),設(shè)G是具有n個(gè)結(jié)點(diǎn)的連通圖，對(duì)于G的每一條邊e指定一個(gè)正實(shí)數(shù)C(e)，稱(chēng)作邊e的權(quán). 圖連同附加在邊上的權(quán)稱(chēng)作帶權(quán)圖, 記作G=. 設(shè)G是G的子圖, G的權(quán)C(G)：G所有邊的權(quán)之和稱(chēng)作。 設(shè)T是G的生成樹(shù)， 樹(shù)權(quán)C(T)：T的所有邊權(quán)之和。 定義7-7.3 在圖G的所有生成樹(shù)中，樹(shù)權(quán)最小的那棵生成樹(shù)，稱(chēng)作最小生成樹(shù)。,最小生成樹(shù)的算法,求最小生成樹(shù)的算法避圈法 (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中無(wú)回路且ei+1是滿(mǎn)足此條件的最小邊。 (4) ii+1，轉(zhuǎn)(2).,Kruskal的證明,證明 設(shè)T0是上述算法構(gòu)造的一個(gè)圖， 它的結(jié)點(diǎn)是G的結(jié)點(diǎn)，T0的邊是e1,e2,e3,en-1。 根據(jù)構(gòu)造過(guò)程，T0無(wú)回路且邊數(shù)為n-1， 所以T0是樹(shù)，且為G的生成樹(shù)。 下面證明T0是最小生成樹(shù)。 假設(shè)G的最小生成樹(shù)是T， (1) 如果T與T0相同，則T0是最小生成樹(shù)。 (2) 若T與T0不同，則必存在一條邊ei+1T0且ei+1T， 而e1,e2,eiT。,Kruskal的證明（續(xù)）,因?yàn)門(mén)是樹(shù)，所以T+ ei+1必存在回路r. 由于T0是樹(shù)，所以r中必存在邊f(xié)T0且fT 對(duì)于樹(shù)T，以ei+1 代替f得到新樹(shù)T， 即在T+ ei+1中刪除f，得到樹(shù)T，所以有 C(T)=C(T)+C(ei+1)-C(f) 因?yàn)镃(T) C(T)，所以C(ei+1)-C(f) 0，因此 C(ei+1) C(f) 因?yàn)閑1,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的一棵最小生成樹(shù)， 但是T與T0的