資源描述：
《定義7.5設(shè)圖G的頂點(diǎn)非空真子集為V1V, 在G中一個(gè)端.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。
1、定義7.5:設(shè)圖G的頂點(diǎn)非空真子集為V1?V,在G中一個(gè)端點(diǎn)在V1中,另一端點(diǎn)在V(G)-V1中的所有邊組成的集合稱為G的一個(gè)斷集或稱邊割,記為E(V1?(V(G)-V1)),簡記為(V1,V(G)-V1)。當(dāng)
2、(V1,V(G)-V1)
3、=1時(shí),(V1,V(G)-V1)中的那條邊稱為割邊或橋。圖7.2(b)中邊集{e1,e2}和{e1,e2,e3,e4}都是斷集(邊割)。割集是斷集,反之不一定。對(duì)于連通圖G(V,E),刪去一個(gè)割集D,得到兩個(gè)分支,頂點(diǎn)集分別為V1和V(G)-V1,割集D是G中一個(gè)端點(diǎn)在V1中,另一端點(diǎn)在V(G)-V1中的邊的全體。如
4、果在連通圖G中,刪去一個(gè)斷集而不是一個(gè)割集,那么將得到多于兩個(gè)分支。三、割集與回路定理7.4：任何一條回路和任何生成樹的余樹至少有一條公共邊。證明：如果一條回路和一棵生成樹的余樹沒有公共邊,則這回路含在該生成樹中,這是不可能的。定理7.5：任何一個(gè)割集和任何生成樹至少有一條公共邊。證明：如果一個(gè)割集和一棵生成樹沒有公共邊,則刪去該割集后留下一棵完整的生成樹,也就是說,刪去一個(gè)割集后,不能將圖G分為兩個(gè)分支,這與割集的定義相矛盾。定理7.6：任何一個(gè)回路和任何一個(gè)割集有偶數(shù)條公共邊。證明：從連通圖G中刪去一個(gè)割集D后,得到兩個(gè)頂點(diǎn)子集V1和V2,考察G
5、中任一條回路C:(1)如果C中所有頂點(diǎn)在V1(或V2)中,則C與D沒有公共邊。(2)如果C中頂點(diǎn)既有一些在V1中,又有一些在V2中,先看D中任何一邊,它的一個(gè)端點(diǎn)在V1中,另一個(gè)端點(diǎn)在V2中,且G中除D中邊以外,不再有任何邊連接V1與V2中的頂點(diǎn)。定義7.6：設(shè)連通圖G中給定生成樹T,對(duì)于只包含T中一條枝的割集,稱此割集為關(guān)于T的基本割集。在連通圖G中,對(duì)于給定的生成樹T,每一枝恰對(duì)應(yīng)唯一的一個(gè)基本割集。因?yàn)閺纳蓸銽中刪去一條枝,將T分為兩棵樹,它將G的頂點(diǎn)集V劃分為V1和V-V1,在G中這兩個(gè)頂點(diǎn)集之間的連邊,便對(duì)應(yīng)這一枝的唯一的基本割集。設(shè)連通
6、圖G有e條邊,n個(gè)頂點(diǎn),給定的生成樹T應(yīng)有n-1條枝,所以恰有n-1個(gè)基本割集,這些基本割集的全體稱為生成樹T基本割集組。定義7.7:設(shè)連通圖G中給定生成樹T,在T中加一條弦,恰產(chǎn)生一條回路,稱此回路為關(guān)于T的基本回路。由定理7.1的等價(jià)定義(4),可知在T中加一弦,產(chǎn)生唯一的回路。設(shè)連通圖G有e條邊,n個(gè)頂點(diǎn),給定的生成樹應(yīng)有n-1條枝,e-n+1條弦,所以恰有e-n+1條基本回路,這些基本回路的全體稱為生成樹T的基本回路組。例如圖(a)中給定T={e1,e4,e5,e6},關(guān)于T的基本割集組:{e1,e2,e8},{e4,e3,e2,e8},{e
7、5,e3,e2,e7},{e6,e7}基本回路組:{e2,e1,e4,e5},{e3,e4,e5},{e7,e5,e6},{e8,e1,e4,}7.3最小生成樹定義7.10:設(shè)G(V,E,w)是帶權(quán)連通簡單圖,w是從E到實(shí)數(shù)集的函數(shù)。又設(shè)T是G的一棵生成樹,T中所有枝的權(quán)之和稱為T的權(quán),記為W(T)。具有權(quán)minTW(T)的生成樹稱為最小生成樹。這個(gè)問題是具有實(shí)際意義的。例如G的頂點(diǎn)表示城市,G的邊表示城市間的道路,邊的權(quán)表示對(duì)應(yīng)道路的長度,現(xiàn)在沿著道路架設(shè)通訊線路,將這些城市聯(lián)系起來,要求架設(shè)的線路最短,這個(gè)問題就是求一棵最小生成樹的問題克魯斯科爾
8、算法的步驟,通俗地說,就是先將G中的邊按權(quán)從小到大順序排列,再從小到大依次取出每一邊作檢查。一開始取權(quán)最小的邊{v1,v6}為e1,且w(e1)=l,由e1導(dǎo)出一個(gè)部分子圖,然后依次每取一邊加入已得部分子圖。若保持無回路,將該邊與原有部分子圖中邊導(dǎo)出一個(gè)新的部分子圖;若得到回路,將該邊放棄。上述過程繼續(xù)進(jìn)行,直到所有邊均檢查完,得到的部分子圖就是所求的一棵最小生成樹,如圖(b)所示,這里e1={v1,v6}和e2={v7,v2}取出后,取e3為{v2,v3},?;若改取e3為{v3,v7},可得到另一棵最小生成樹求最小生成樹的克魯斯科爾(Kruska
9、l)算法克魯斯科爾算法:設(shè)G(V,E,w)是有n個(gè)頂點(diǎn)的帶權(quán)連通簡單圖。(1)選取G的一邊e1,使w(e1)最小,令E1={e1},1?i。(2)若已選Ei={e1,e2,?,ei},那么從E-Ei中選取一邊ei+1,滿足:1)Ei∪{ei+1}的導(dǎo)出子圖中不含有回路;同時(shí)2)w(ei+1)為滿足1)E-Ei中的最小;3)若ei+1存在,則令Ei+1=Ei∪{ei+1},i+1?i,轉(zhuǎn)(2);若ei+1不存在,則停,此時(shí)Ei導(dǎo)出的子圖就是所求的最小生成樹,記為T。定理7.8:克魯斯科爾算法所得到的圖T是最小生成樹。證明:首先由定理7.1等價(jià)定義(4)
10、(T是無回路圖,且在T的任兩個(gè)不相鄰的頂點(diǎn)之間添加一邊,恰得到一條回路)知T是G的一棵子樹。并由等價(jià)定義(2
