圖論中幾個(gè)典型問題

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

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

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

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

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

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

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

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

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

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

11、無法進(jìn)行為止，結(jié)束。 例：求下圖所示的網(wǎng)絡(luò)最大流 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實(shí)現(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