圖論中幾個典型問題

1、圖論中幾個典型問題的算法及其Matlab實現(xiàn) 圖論的產(chǎn)生與發(fā)展 1.格尼斯堡七橋問題 哥尼希堡城有一座橫貫全市的普雷格爾 河，河中有兩個島嶼，兩岸及島嶼有七座橋相連，如圖(1)2.四色問題3.哈密爾頓周游世界問題第一節(jié) 圖的基本概念 1.圖的定義 圖由一些點和點之間的連線所組成。 用V=v1,v2,表示全體頂點的集合，用E=e1,e2,表示所有邊的集合，如果對于E中任一條邊，在V中都有一對定點(vi,vj)和它對應，則稱由V和G組成的集體為一個圖，記為G=(V,E),簡記為G。 2.基本概念 關(guān)聯(lián)：如果頂點v是邊e的一個端點，則稱邊e和頂點v相關(guān)聯(lián)。 鄰接：對于頂點u和v，若(u,v)屬于E，

2、則稱u和v是鄰接的，對于兩條邊，若有共同的頂點，則稱這兩條邊是鄰接的。 階：圖中頂點的個數(shù)。 度：與圖中某個頂點關(guān)聯(lián)的邊的個數(shù)，稱為該頂點的度。 環(huán)：兩個端點重合的邊。 多重邊：關(guān)聯(lián)于同一對頂點的兩條或兩條以上的邊。 簡單圖：沒有環(huán)也沒有重邊的圖。 途徑：圖G=(V,E)的一個點和邊交替出現(xiàn)的有限非空序列。 跡：一條沒有重復邊的途徑。 路：一條各頂點互不相同的途徑。 閉途徑：起點與終點相同的途徑。 閉跡：起點與終點相同的跡。 圈(回路)：起點與終點重合的路。 連通：若頂點u和v之間存在一條路，則稱u和v連通。 連通圖：任意兩個頂點都連通的圖。 完全圖：任意兩個頂點之間都有一個頂點相連的簡單圖

3、橋(割邊)：設G是連通圖，若從G中刪除邊e后，圖不再連通，則稱邊e為圖G的橋(割邊)。 無向圖：每條邊都沒有方向的圖。 有向圖：每條邊都有方向的圖。 賦權(quán)圖：在圖的每條邊上標明了數(shù)量關(guān)系，可能是距離、時間、費用、電阻等等，這些數(shù)值稱為相應邊的權(quán)，邊上帶權(quán)的圖稱為賦權(quán)圖。同時稱帶權(quán)的有向圖為網(wǎng)絡。 子圖：設有兩個圖G=(V,E),G1=(V1,E1),若V1是V的子集，E1是E的子集，則稱G1是G的子圖。 第二節(jié) 圖的矩陣表示 要將圖的信息存到計算機中，需要使用專門設計的數(shù)據(jù)結(jié)構(gòu)，比較常見的是鄰接矩陣、前向星、鄰接表、鏈式前向星這四種方式。此外還有結(jié)構(gòu)比較復雜的十字鏈表方式。 無向圖的關(guān)聯(lián)矩陣：

4、設圖G=(V,E)的頂點集和邊集分別為V(G)=v1,v2,vn ,E(G)=e1,e2,em，用Bij表示頂點vi與邊ej關(guān)聯(lián)的次數(shù)，把行對應頂點，列對應邊的矩陣B(G)=(bij)nm稱為圖G的關(guān)聯(lián)矩陣。 無向圖的鄰接矩陣：設圖G=(V,E)的頂點集為V(G)=v1,v2,vn ，用aij表示G中頂點vi與vj之間的邊數(shù)，則n階方陣M(G)=(aij)nn稱為G的鄰接矩陣。 無向賦權(quán)圖鄰接矩陣的定義：設圖G=(V,E)的頂點集為V(G)=v1,v2,vn，其鄰接矩陣為n階對稱陣A，元素定義為aii=0,當頂點vi與vj之間沒有連線時，aij=inf，當頂點vi與vj之間有連線時，aij=邊

5、vivj的權(quán)值。 例：寫出下圖的鄰接矩陣 有向圖的關(guān)聯(lián)矩陣：設圖G=(V,E)的頂點集和邊集分別為V(G)=v1,v2,vn ,E(G)=e1,e2,em，則矩陣B=(bij)nm為有向圖G的關(guān)聯(lián)矩陣，其元素定義為，bij=1,頂點vi是邊ej的起點； bij=-1,頂點vi是邊ej的終點； bij=0,頂點vi是邊ej不關(guān)聯(lián)； bij=-2，ej為環(huán)，且關(guān)聯(lián)與vi。例：寫出下圖的關(guān)聯(lián)矩陣 有向圖的鄰接矩陣：設圖G=(V,E)的頂點集為V(G)=v1,v2,vn ，用aij表示G中以頂點vi為起點與以vj為終點之間的邊數(shù)，則n階方陣M(G)=(aij)nn稱為G的鄰接矩陣。 有向賦權(quán)圖鄰接矩陣

6、的定義：設圖G=(V,E)的頂點集為V(G)=v1,v2,vn，其鄰接矩陣為n階矩陣A，元素定義為,當起點vi與終點vj之間沒有連線時，aij=inf，當起點vi與終vj之間有連線時，aij=邊vivj的權(quán)值。第三節(jié) 幾個典型問題 1.最短路徑問題 實際問題：給定連接若干城市的鐵路網(wǎng)，找一條給定兩城市間的最短線路。 最短路徑定義：在賦權(quán)圖G=(V,E)中，設頂點vi,vj是圖的兩個頂點，從頂點vi到vj的路徑長度定義為路徑上各條邊的權(quán)值之和，從頂點vi到vj的所有路徑中，其中路徑長度最小的一條路徑。 重要性質(zhì)：最短路是一條路徑，且最短路上任一段也是最短路。求單源最短路徑的Dijkstra算法

7、算法描述： (1)算法思想：設G=(V,E)是一個賦權(quán)有向圖，設集合S用來保存已求得最短路徑的頂點序號，集合U為其余未確定最短路徑的頂點集合，按照最短路徑長度遞增的次序依次把U中頂點加入S。 總之，從源點v到各個頂點層層推進過程中，要保證每一步走的都是最短路徑。 (2)算法步驟： a.初始時，S只包含源點，S=v，U=其余頂點。 b.從U中選取一個頂點k，使dist(v,k)最短，把k加入S。 c.以k為新的中間點，對于U中頂點u，如果dist(v,k)+dist(k,u)fxy，則稱f為最大流(Maximum Flow)，記為fmax。 運輸網(wǎng)絡中一個重要的問題是要找出它的一個最大流fmax

8、。 定義4：給定網(wǎng)絡N=(V,A,C)是一個單源、單匯的網(wǎng)絡，若V被分成兩個非空子集S, ,使得源 ，稱 是分離x和y的一個割集(Cut Set)。割集 中所有始點在S中，終點在 中的弧的容量之和，稱為 的割集容量，記為 。割集容量最小的割稱為最小割(Minimum Cut)。 例：在右圖所示的網(wǎng)絡中，選S=x,v3,v4, ，則(x,v1),(v3,y),(v4,y)是N的一個割集，割集容量為 =4+2+3=9。 如選S=x, 則(x,v1),(x,v3),(x,v4) 也是N的一個割集，此時割集容量為11. 并且，在任何網(wǎng)絡中，最大流的流量等于最小割集的容量 定義5：設f是網(wǎng)絡N中的一個可

9、行流，P是一條xy路，則P滿足下列兩個條件之一的弧(vi,vj)稱為增廣弧(Incrementing Arc)。 a. ，且fij0。 如果P中的弧都是增廣弧，則P是關(guān)于f的增廣路(Incrementing Path)。并且若N中有一f增廣路P，則f不是最大流。如圖，(x,y)-路xv2v1v3y是f增廣路求最大流問題的FF算法 最大流問題的算法思想： 首先從任何一個可行流(如零流)出發(fā)，判斷網(wǎng)絡N中是否有關(guān)于f的xy增廣路。若沒有這樣的增廣路，則f就是最大流；若有這樣的增廣路，則對f進行調(diào)整，得到一個新的流量更大的可行流f ；對f 再重復上述過程，直到找不出xy增廣路為止。 算法關(guān)鍵與核心：

10、尋找xy增廣路。算法步驟：(1)標號過程1).給源x以標號 (永久標號)。2).選擇一個已標號的頂點vi，對vi的所有未給標號的鄰接點作如下處理：a.若弧 ，且fij0，令 ， 并給vj以標號 。c.重復2)過程直到匯y被標號，或不再有頂點可標號為止。如果y得到標號，說明存在一條xy增廣路，轉(zhuǎn)步驟(2)調(diào)整過程；若y未獲得標號，標號過程無法進行，這時，令S是所有標號點集，T是所有未標號點集，則(S,T)是一個割集，則割集(S,T)的容量就是最大流的流量。(2)調(diào)整過程a.令 ，調(diào)整增廣路P中的流量如下：得到新的可行流f =fij，顯然總流量為b.去掉所有標號，回到步驟(1)，重復上述過程，直到

11、無法進行為止，結(jié)束。 例：求下圖所示的網(wǎng)絡最大流 C=0 5 4 3 0 0 0 0; 0 0 0 0 5 3 0 0; 0 0 0 0 0 3 2 0; 0 0 0 0 0 0 2 0; 0 0 0 0 0 0 0 4; 0 0 0 0 0 0 0 3; 0 0 0 0 0 0 0 5; 0 0 0 0 0 0 0 0; 算法Matlab實現(xiàn)： q = 0 5 4 2 0 0 0 0 0 0 0 0 4 1 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 w = 11 e = 9 0 0 1 0 0 0 0