數(shù)學(xué)建模圖論模型

1、圖論模型圖論模型圖論基本概念圖論基本概念最短路徑算法最短路徑算法最小生成樹算法最小生成樹算法遍歷性問題遍歷性問題二分圖與匹配二分圖與匹配2網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題關(guān)鍵路徑問題關(guān)鍵路徑問題系統(tǒng)監(jiān)控模型系統(tǒng)監(jiān)控模型著色模型著色模型1 1、圖論的基本概念、圖論的基本概念問題問題1(1(哥尼斯堡七橋哥尼斯堡七橋問題問題):): 能否從任一陸地出發(fā)通過每座橋恰好一次而能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點(diǎn)？回到出發(fā)點(diǎn)？34歐拉指出：歐拉指出： 如果每塊陸地所連接的橋都是偶數(shù)座，則從任一如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地陸地出發(fā)，必能通過每座橋恰好

2、一次而回到出發(fā)地. .5問題問題2(2(哈密頓環(huán)球旅行哈密頓環(huán)球旅行問題問題):): 十二面體的十二面體的2020個(gè)頂點(diǎn)代表世界上個(gè)頂點(diǎn)代表世界上2020個(gè)城市，個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過每個(gè)能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？城市恰好一次最后回到出發(fā)點(diǎn)？歐拉問題是歐拉問題是“邊遍歷邊遍歷”，哈密爾頓問題是，哈密爾頓問題是“點(diǎn)遍歷點(diǎn)遍歷”6問題問題3(3(四色問題四色問題):): 對任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的國家染不同的顏對任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的國家染不同的顏色，則只需要四種顏色就夠了色，則只需要四種顏色就夠了. .

3、問題問題4(4(關(guān)鍵路徑問題關(guān)鍵路徑問題):): 一項(xiàng)工程任務(wù)一項(xiàng)工程任務(wù), ,大到建造一座大壩大到建造一座大壩, ,一座體育中心一座體育中心, ,小至組裝小至組裝一臺機(jī)床一臺機(jī)床, ,一架電視機(jī)一架電視機(jī), , 都要包括許多工序都要包括許多工序. .這些工序相互約束這些工序相互約束, ,只有在某些工序完成之后只有在某些工序完成之后, , 一個(gè)工序才能開始一個(gè)工序才能開始. . 即它們之間存在即它們之間存在完成的先后次序關(guān)系完成的先后次序關(guān)系, ,一般認(rèn)為這些關(guān)系是預(yù)知的一般認(rèn)為這些關(guān)系是預(yù)知的, , 而且也能夠而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間. . 這時(shí)工程

4、領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目成整個(gè)工程項(xiàng)目, , 影響工程進(jìn)度的要害工序是哪幾個(gè)？影響工程進(jìn)度的要害工序是哪幾個(gè)？ 圖的定義 圖論中的圖論中的“圖圖”并不是通常意義下的幾何圖形或物體的形并不是通常意義下的幾何圖形或物體的形狀圖狀圖, , 而是以一種抽象的形式來表達(dá)一些確定的事物之間的聯(lián)而是以一種抽象的形式來表達(dá)一些確定的事物之間的聯(lián)系的一個(gè)數(shù)學(xué)系統(tǒng)系的一個(gè)數(shù)學(xué)系統(tǒng). . 定義定義1 一個(gè)有序二元組一個(gè)有序二元組(V, E ) 稱為一個(gè)稱為一個(gè)圖圖, 記為記為G = (V, E ), 其中其中 V稱為稱為G的頂點(diǎn)集

5、的頂點(diǎn)集, V , 其元素稱為其元素稱為頂點(diǎn)頂點(diǎn)或或結(jié)點(diǎn)結(jié)點(diǎn), 簡稱簡稱點(diǎn)點(diǎn); E稱為稱為G的邊集的邊集, 其元素稱為其元素稱為邊邊, 它聯(lián)結(jié)它聯(lián)結(jié)V 中的兩個(gè)點(diǎn)中的兩個(gè)點(diǎn), 如如果這兩個(gè)點(diǎn)是無序的果這兩個(gè)點(diǎn)是無序的, 則稱該邊為則稱該邊為無向邊無向邊, 否則否則, 稱為稱為有向邊有向邊. 如果如果V = v1, v2, , vn是有限非空點(diǎn)集是有限非空點(diǎn)集, 則稱則稱G為為有限圖有限圖或或n階圖階圖. 8 如果如果E的每一條邊都是無向邊的每一條邊都是無向邊, 則稱則稱G為為無向圖無向圖( (如圖如圖1)1); 如如果果E的每一條邊都是有向邊的每一條邊都是有向邊, 則稱則稱G為為有向圖有向圖(

6、 (如圖如圖2)2); 否則否則, 稱稱G為為混合圖混合圖. 圖圖1 1 圖圖2 2并且常記并且常記: : V = v1, v2, , vn, |V | = n ;E = e1, e2, , em(ek=vivj ) , |E | = m.稱點(diǎn)稱點(diǎn)vi , vj為邊為邊vivj的的端點(diǎn)端點(diǎn). 在有向圖中在有向圖中, 稱點(diǎn)稱點(diǎn)vi , vj分別為邊分別為邊vivj的的始點(diǎn)始點(diǎn)和和終點(diǎn)終點(diǎn). 該圖稱為該圖稱為(n,m)圖圖9 對于一個(gè)圖對于一個(gè)圖G = (V, E ), 人們常用圖形來表示它人們常用圖形來表示它, 稱稱其為其為圖解圖解. 凡是有向邊凡是有向邊, 在圖解上都用箭頭標(biāo)明其方向在圖解上都

7、用箭頭標(biāo)明其方向. 例如例如, 設(shè)設(shè)V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 則則G = (V, E ) 是一個(gè)有是一個(gè)有4個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和6條邊的圖條邊的圖, G的圖解如下圖所示的圖解如下圖所示. 10 一個(gè)圖會有許多外形不同的圖解一個(gè)圖會有許多外形不同的圖解, , 下面兩個(gè)圖表示同一個(gè)圖下面兩個(gè)圖表示同一個(gè)圖G = (V, E )的圖解的圖解. .這兩個(gè)圖互為這兩個(gè)圖互為同構(gòu)圖同構(gòu)圖, ,今后將不計(jì)較這種外形今后將不計(jì)較這種外形上的差別上的差別, ,而用一個(gè)容易理解的、確定的圖解去表示一個(gè)圖而用一

8、個(gè)容易理解的、確定的圖解去表示一個(gè)圖. . 11 有邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為有邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為相鄰的點(diǎn)相鄰的點(diǎn), 有一個(gè)公共端點(diǎn)的邊稱為有一個(gè)公共端點(diǎn)的邊稱為相相鄰邊鄰邊. 邊和它的端點(diǎn)稱為邊和它的端點(diǎn)稱為互相關(guān)聯(lián)互相關(guān)聯(lián). 常用常用d(v)表示圖表示圖G中與頂點(diǎn)中與頂點(diǎn)v關(guān)聯(lián)關(guān)聯(lián)的邊的數(shù)目的邊的數(shù)目, d(v)稱為頂點(diǎn)稱為頂點(diǎn)v的的度數(shù)度數(shù). 對于有向圖對于有向圖,還有還有出度出度和和入度入度之之分分. 用用N(v)表示圖表示圖G中所有與頂點(diǎn)中所有與頂點(diǎn)v相鄰的頂點(diǎn)的集合相鄰的頂點(diǎn)的集合. d(v1)= d(v3)= d(v4)=4, d(v2)=2dout(v1)= dout (v3)= do

9、ut (v4)=2, dout(v2)=1din(v1)= din(v3)= din(v4)=2, din(v2)=112握手定理握手定理：無向圖中，所有結(jié)點(diǎn)的度數(shù)之和等于2m。右圖：推論1：無向圖中必有偶數(shù)個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)。推論2：有向圖中所有結(jié)點(diǎn)的出度之和等于入度之和。d(v1)= d(v3)= d(v4)=4, d(v2)=2mvdnii2)(1147*2)(1niivd我們今后只討論有限簡單圖： (1) (1) 頂點(diǎn)個(gè)數(shù)是有限的頂點(diǎn)個(gè)數(shù)是有限的; (2) (2) 任意一條邊有且只有兩個(gè)不同的點(diǎn)與它相互關(guān)聯(lián)任意一條邊有且只有兩個(gè)不同的點(diǎn)與它相互關(guān)聯(lián); (3) (3) 若是無向圖若是無向

10、圖, , 則任意兩個(gè)頂點(diǎn)最多只有一條邊與之相則任意兩個(gè)頂點(diǎn)最多只有一條邊與之相聯(lián)結(jié)聯(lián)結(jié); (4) (4) 若是有向圖若是有向圖, , 則任意兩個(gè)頂點(diǎn)最多只有兩條邊與之相則任意兩個(gè)頂點(diǎn)最多只有兩條邊與之相聯(lián)結(jié)聯(lián)結(jié). . 當(dāng)兩個(gè)頂點(diǎn)有兩條邊與之相聯(lián)結(jié)時(shí)，這兩條邊的方向當(dāng)兩個(gè)頂點(diǎn)有兩條邊與之相聯(lián)結(jié)時(shí)，這兩條邊的方向相反相反. . 如果某個(gè)有限圖不滿足如果某個(gè)有限圖不滿足(2)(3)(4),(2)(3)(4),可在某條邊上增設(shè)頂點(diǎn)可在某條邊上增設(shè)頂點(diǎn)使之滿足使之滿足. .14 定義定義2 若將圖若將圖G的每一條邊的每一條邊e都對應(yīng)一個(gè)實(shí)數(shù)都對應(yīng)一個(gè)實(shí)數(shù)F (e), 則稱則稱F (e)為該邊的為該邊的權(quán)

11、權(quán), 并稱圖并稱圖G為為賦權(quán)圖賦權(quán)圖(網(wǎng)絡(luò)網(wǎng)絡(luò)), 記為記為G = (V, E , F ). 定義定義3 任意兩點(diǎn)均有通路的圖稱為任意兩點(diǎn)均有通路的圖稱為連通圖連通圖. 定義定義4 連通而無圈的圖稱為連通而無圈的圖稱為樹樹, 常用常用T表示樹表示樹. 常用的圖給定圖G= 和 G = 是兩個(gè)圖，如果有 V V 和 E E,則稱圖G是圖 G 的子圖。若V =V 稱圖G是圖 G 的生成子圖；若將圖G的每一條邊e都對應(yīng)一個(gè)實(shí)數(shù)F(e)，則稱F(e)為該邊的權(quán)，并稱圖G為賦權(quán)圖(網(wǎng)絡(luò)), 記為G = 。任意兩點(diǎn)均有通路的圖稱為連通圖。連通而無圈的圖稱為樹，常用T=表示樹。 若圖G是圖 G 的生成子圖，且

12、G又是一棵樹，則稱G是圖G 的生成樹。例 Ramsey問題問題：任何6個(gè)人的聚會，其中總會有3個(gè)互相認(rèn)識或3人互相不認(rèn)識。圖論模型：用紅、藍(lán)兩種顏色對6個(gè)頂點(diǎn)的完全圖K6的邊進(jìn)行任意著色，則不論如何著色必然都存在一個(gè)紅色的K3或一個(gè)藍(lán)色的K3 。對應(yīng)關(guān)系：每個(gè)人即為一個(gè)結(jié)點(diǎn)；人與人之間的關(guān)系即為一條邊例 Ramsey問題圖論證明：用紅、藍(lán)兩種顏色對K6的邊進(jìn)行著色，K6的任意一個(gè)頂點(diǎn)均有5條邊與之相連接，這5條邊必有3條邊的顏色是相同的，不妨設(shè)為藍(lán)色（如圖）與這3條邊相關(guān)聯(lián)的另外3個(gè)節(jié)點(diǎn)之間的3條邊，若都為紅色，則形成紅色的K3；若另外3個(gè)節(jié)點(diǎn)之間的3條邊有一條為藍(lán)色，則與上面的藍(lán)色邊形成藍(lán)色

13、的K3；因此必然存在一個(gè)紅色的K3或一個(gè)藍(lán)色的K3 。例 Ramsey問題Ramsey數(shù)：R（3,3）=6；R（3,4）=9；。18例 過河問題問題：一擺渡人欲將一只狼、一頭羊、一籃菜從河西渡過河到河?xùn)|。由于船小，一次只能帶一物過河，并且狼與羊，羊與菜不能獨(dú)處，給出渡河方法。這里顯然不能用一個(gè)節(jié)點(diǎn)表示一個(gè)物體。一個(gè)物體可能在河?xùn)|，也可能在河西，也可能在船上，狀態(tài)表示不清楚。另外，問題也可以分成幾個(gè)小問題，如：問題是否能解？有幾種不同的解法？最快的解決方案是什么？例 過河問題解：解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的狀態(tài)(在河西岸則分量取1，否則取0)，共有24 =16 種狀態(tài)。在

14、河?xùn)|岸的狀態(tài)類似記作。由題設(shè)，狀態(tài)(0,1,1,0)，(0,0,1,1)，(0,1,1,1)是不允許的；其對應(yīng)狀態(tài)：(1,0,0,1)， (1,1,0,0)，(1,0,0,0)也是不允許的。以可允許的以可允許的10個(gè)狀態(tài)向量作為個(gè)狀態(tài)向量作為頂點(diǎn)頂點(diǎn)，將可能互相轉(zhuǎn)移的狀，將可能互相轉(zhuǎn)移的狀態(tài)用態(tài)用邊邊連接起來構(gòu)成一個(gè)圖。連接起來構(gòu)成一個(gè)圖。利用圖論的相關(guān)知識即可回答原問題。例 過河問題(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)(0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1)(0,1,0,1

15、) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0)(1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1)河西河西=(人人,狼狼,羊羊,菜菜) 河?xùn)|河?xùn)|=(人人,狼狼,羊羊,菜菜) 將10個(gè)頂點(diǎn)分別記為A1, A2, , A10 , 從圖中易得到兩條路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.問題的轉(zhuǎn)換： 過河問題是否能解？即：圖中A1到A10是否連通？ 有幾種不同的解法？即： A1到A10之間有多少條不同的路徑？ 最快的解決方案是什么？即： A1到A10最短路

16、徑有哪些？圖的矩陣表示圖的矩陣表示 鄰接矩陣：鄰接矩陣：鄰接矩陣表示了點(diǎn)與點(diǎn)之間的鄰接關(guān)鄰接矩陣表示了點(diǎn)與點(diǎn)之間的鄰接關(guān)系系. .一個(gè)一個(gè)n階圖階圖G的鄰接矩陣的鄰接矩陣A = (aij )nn , 其中其中 ., 0;, 1EvEvaijijij0101100101001010A2223無向圖無向圖G的鄰接矩陣的鄰接矩陣A是一個(gè)對稱矩陣是一個(gè)對稱矩陣. . 0101101101011110A 權(quán)矩陣權(quán)矩陣 一個(gè)一個(gè)n階賦權(quán)圖階賦權(quán)圖G = (V, E, F)的權(quán)矩陣的權(quán)矩陣A = (aij ) nn , 其中其中 .,;0),(EvjiEvvvFaijijjiij有限簡單圖基本有限簡單圖基本

17、上可用權(quán)矩陣來上可用權(quán)矩陣來表示表示. .2405420370860A無向圖無向圖G的權(quán)矩陣的權(quán)矩陣A是一個(gè)對稱矩陣是一個(gè)對稱矩陣. . 02420737064360A25 關(guān)聯(lián)矩陣：關(guān)聯(lián)矩陣：一個(gè)有一個(gè)有m條邊的條邊的n階有向圖階有向圖G的關(guān)聯(lián)的關(guān)聯(lián)矩陣矩陣A = (aij )nm , 其中其中 若若vi是是ej的始點(diǎn)的始點(diǎn);若若vi是是ej的終點(diǎn)的終點(diǎn);若若vi與與ej不關(guān)聯(lián)不關(guān)聯(lián). ., 0, 1, 1ija 有向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有一個(gè)有向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有一個(gè)1,1,有且僅有且僅有一個(gè)有一個(gè) - - 1. 1. 11011000110110000001110

18、11001A26 一個(gè)有一個(gè)有m條邊的條邊的n階無向圖階無向圖G的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣A = (aij )nm , 其中其中 若若vi與與ej關(guān)聯(lián)關(guān)聯(lián);若若vi與與ej不關(guān)聯(lián)不關(guān)聯(lián). ., 0, 1ija 無向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個(gè)無向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個(gè)1. 1. 110100101010011001000111A2 2、最短路徑算法 定義定義1 設(shè)設(shè)P(u, v) 是賦權(quán)圖是賦權(quán)圖G = (V, E , F) 中從點(diǎn)中從點(diǎn)u到到v的路徑的路徑, 用用E(P) 表示路徑表示路徑P(u, v)中全部邊的集合中全部邊的集合, 記記)()()(PEeeFPF則稱則稱F

19、(P)為路徑為路徑P(u, v) 的的權(quán)權(quán)或或長度長度( (距離距離) ). 定義定義2 若若P0 (u, v) 是是G 中連接中連接u, v的路徑的路徑, 且對任意在且對任意在G 中連中連接接u, v的路徑的路徑P (u, v)都有都有F (P0)F(P), 則稱則稱P0 (u, v) 是是G 中連接中連接u, v的的最短路最短路. 重要性質(zhì)：重要性質(zhì)： 若若v0 v1 vm 是是圖圖G中從中從v0到到vm的最短路的最短路, 則則 1km, v0v1 vk 必為必為G中從中從v0到到vk的最短路的最短路. 即：最短路是一條路，且最短路的任一段也是最短路即：最短路是一條路，且最短路的任一段也是

20、最短路. 求非負(fù)賦權(quán)圖求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最短路，一般用中某一點(diǎn)到其它各點(diǎn)最短路，一般用Dijkstra標(biāo)號算法；求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用標(biāo)號算法；求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用Floyd算法算法. . 這兩種算法均適用于有向非負(fù)賦權(quán)圖這兩種算法均適用于有向非負(fù)賦權(quán)圖. . 下面分別介紹兩種算法的基本過程下面分別介紹兩種算法的基本過程. .Dijkstra算法指標(biāo)（a為起點(diǎn)） 設(shè)T為V的子集，P=V-T且aT，對所有tT，設(shè) l(t)表示從a到t的所有通路中距離最短的一條的長度，且這條路徑中不包含T中其他的結(jié)點(diǎn)，則稱l(t)為t關(guān)于集合P的指標(biāo)，若不存在這

21、樣的路徑，這記l(t)= 注：l(t)不一定是從a到t的最短路徑，因?yàn)樽疃搪窂街锌赡馨琓中其他的節(jié)點(diǎn)。定理1 若t是T中關(guān)于P由最小指標(biāo)的結(jié)點(diǎn)，則l(t)是a和t之間的最短距離。定理2 設(shè) T為V的子集，P=V-T，設(shè) (1)對P中的任一點(diǎn)p,存在一條從a到p的最短路徑,這條路徑僅有P中的點(diǎn)構(gòu)成, (2)對于每一點(diǎn)t,它關(guān)于P的指標(biāo)為l(t),令x為最小指標(biāo)所在的點(diǎn), 即: (3)令P=P Ux,T=T-x,l(t)表示T中結(jié)點(diǎn)t關(guān)于P的指標(biāo),則 29),()(),(min)( txwxltltlTttlxl),(min)(Dijkstra算法（求a點(diǎn)到其他點(diǎn)的最短路徑）1、初始化，、初始化

22、，P=a，T=V-a，對每個(gè)結(jié)點(diǎn)，對每個(gè)結(jié)點(diǎn)t計(jì)算指標(biāo)計(jì)算指標(biāo) l(t)=w(a,t) 2、設(shè)、設(shè)x為為T中關(guān)于中關(guān)于P有最小指標(biāo)的點(diǎn)有最小指標(biāo)的點(diǎn), 即即:l(x)=min(l(t) (tT), 3、若、若T=,則算法結(jié)束則算法結(jié)束; 否則否則,令令P=P Ux,T=T-x 按照公式按照公式l(t)=minl(t),l(x)+w(x,t), 計(jì)算計(jì)算T中每一個(gè)結(jié)點(diǎn)中每一個(gè)結(jié)點(diǎn)t關(guān)于關(guān)于P的指標(biāo)的指標(biāo). 4、P代替代替P,T代替代替T,重復(fù)步驟重復(fù)步驟2,3 （ 其中：其中：w(x,y)為圖的權(quán)矩陣）為圖的權(quán)矩陣） 30改進(jìn)Dijkstra算法（求a點(diǎn)到其他點(diǎn)的最短路徑）1、初始化，、初始化，

23、P=a，T=V-a，對每個(gè)結(jié)點(diǎn)，對每個(gè)結(jié)點(diǎn)t計(jì)算指標(biāo)計(jì)算指標(biāo) l(t)=w(a,t) ,pro(t)=a;2、設(shè)、設(shè)x為為T中關(guān)于中關(guān)于P有最小指標(biāo)的點(diǎn)有最小指標(biāo)的點(diǎn), 即即:l(x)=min(l(t) (tT);3、若、若T=,則算法結(jié)束則算法結(jié)束; 否則否則,令令P=P Ux,T=T-x 按照公式按照公式l(t)=minl(t),l(x)+w(x,t), 計(jì)算計(jì)算T中每一個(gè)結(jié)點(diǎn)中每一個(gè)結(jié)點(diǎn)t關(guān)于關(guān)于P的指標(biāo)的指標(biāo). 若若 l(x)+w(x,t) l(t), pro(t)=x;4、P代替代替P,T代替代替T,重復(fù)步驟重復(fù)步驟2,3 （ 其中：其中：w(x,y)為圖的權(quán)矩陣）為圖的權(quán)矩陣） 3

24、1例 求下圖中A A點(diǎn)到其他點(diǎn)的最短路. .32Floyd算法（求任意兩點(diǎn)的最短路徑） 設(shè)設(shè)A = (aij )nn為賦權(quán)圖為賦權(quán)圖G = (V, E, F)的權(quán)矩陣的權(quán)矩陣, dij表表示從示從vi到到vj點(diǎn)的距離點(diǎn)的距離, rij表示從表示從vi到到vj點(diǎn)的最短路中前一個(gè)點(diǎn)的最短路中前一個(gè)點(diǎn)的編號點(diǎn)的編號. 賦初值賦初值. 對所有對所有i, j, dij = aij, rij = j. k = 1. 轉(zhuǎn)向轉(zhuǎn)向. 更新更新dij , rij . 對所有對所有i, j, 若若dik + dk jdij , 則令則令dij = dik + dkj , rij = k, 轉(zhuǎn)向轉(zhuǎn)向; 終止判斷終止判

25、斷. 若若k = n終止終止; 否則令否則令k = k + 1, 轉(zhuǎn)向轉(zhuǎn)向. 最短路線可由最短路線可由rij得到得到. 例 求下圖中任意兩點(diǎn)間的最短路. .3403030350201502051504510500A028338235803065508525035205540150352053015035452510450D533333143333113111133230142212142220R例 設(shè)備更新問題 某企業(yè)每年年初某企業(yè)每年年初, ,都要作出決定都要作出決定, ,如果繼續(xù)使用舊設(shè)備如果繼續(xù)使用舊設(shè)備, ,要付要付維修費(fèi)；若購買一臺新設(shè)備維修費(fèi)；若購買一臺新設(shè)備, ,要付購買費(fèi)要付購

26、買費(fèi). .試制定一個(gè)試制定一個(gè)5 5年更新計(jì)年更新計(jì)劃劃, ,使總支出最少使總支出最少. . 已知設(shè)備在每年年初的購買費(fèi)分別為已知設(shè)備在每年年初的購買費(fèi)分別為11,11, 12,12,13. 11,11, 12,12,13. 使使用不同時(shí)間設(shè)備所需的維修費(fèi)分別為用不同時(shí)間設(shè)備所需的維修費(fèi)分別為5,6,8,11,18.5,6,8,11,18. 解解 設(shè)設(shè)bi 表示設(shè)備在第表示設(shè)備在第i 年年初的購買費(fèi)年年初的購買費(fèi), ,ci 表示設(shè)備使用表示設(shè)備使用i 年年后的維修費(fèi)后的維修費(fèi), , V= v1, v2, , v6,點(diǎn)點(diǎn)vi表示第表示第i 年年初購進(jìn)一臺新設(shè)備年年初購進(jìn)一臺新設(shè)備, ,虛設(shè)一個(gè)虛

27、設(shè)一個(gè)點(diǎn)點(diǎn)v6表示第表示第5 5年年底年年底. . E = vivj | 1ij6,每條每條邊邊vivj表一臺設(shè)備，從第表一臺設(shè)備，從第i年年初購買使年年初購買使用到第用到第j年年初報(bào)廢年年初報(bào)廢.ijkkijicbvvF1)(36 這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖G = (V, E, F )(圖解如下圖解如下) )中求中求v1到到v6的最短路問題的最短路問題. 37 由實(shí)際問題可知由實(shí)際問題可知, ,設(shè)備使用三年后應(yīng)當(dāng)更新設(shè)備使用三年后應(yīng)當(dāng)更新, ,因此刪因此刪除該圖中除該圖中v1到到v5 , ,v1到到v6 , ,v2到到v6的連線；又設(shè)備使

28、用一年的連線；又設(shè)備使用一年后就更新則不劃算后就更新則不劃算, ,因此再刪除該圖中因此再刪除該圖中v1v2 , ,v2v3 , ,v3v4 , ,v4v5 , ,v5v6 五條連線后得到五條連線后得到從上圖中容易得到從上圖中容易得到v1到到v6只有兩條路：只有兩條路：v1v3v6和和v1v4v6. . 而這兩條路都是而這兩條路都是v1到到v6的最短路的最短路. .3 3、最小生成樹 由樹的定義不難知道由樹的定義不難知道, 任意一個(gè)連通的任意一個(gè)連通的(n,m)圖圖G適當(dāng)去掉適當(dāng)去掉m - - n +1條邊后條邊后, 都可以變成樹都可以變成樹, 這棵樹稱為圖這棵樹稱為圖G的的生成樹生成樹. 設(shè)設(shè)

29、T是圖是圖G的一棵生成樹的一棵生成樹, 用用F(T)表示樹表示樹T中所有邊的權(quán)數(shù)之和中所有邊的權(quán)數(shù)之和, F(T)稱為稱為樹樹T的權(quán)的權(quán). 一個(gè)連通圖一個(gè)連通圖G的生成樹一般不止一棵的生成樹一般不止一棵, 圖圖G的所有生成樹中權(quán)的所有生成樹中權(quán)數(shù)最小的生成樹稱為圖數(shù)最小的生成樹稱為圖G的的最小生成樹最小生成樹-Minimum-cost Spanning Tree (MST). 求最小生成樹問題有很廣泛的實(shí)際應(yīng)用求最小生成樹問題有很廣泛的實(shí)際應(yīng)用. 例如例如, 把把n個(gè)鄉(xiāng)鎮(zhèn)用個(gè)鄉(xiāng)鎮(zhèn)用高壓電纜連接起來建立一個(gè)電網(wǎng)高壓電纜連接起來建立一個(gè)電網(wǎng), 使所用的電纜長度之和最短使所用的電纜長度之和最短, 即

30、即費(fèi)用最小費(fèi)用最小, 就是一個(gè)求最小生成樹問題就是一個(gè)求最小生成樹問題. KruskalKruskal算法39 從未選入樹中的邊中選取權(quán)重最小的且不構(gòu)成回路從未選入樹中的邊中選取權(quán)重最小的且不構(gòu)成回路的邊加入到樹中的邊加入到樹中. .（判斷回路比較麻煩）（判斷回路比較麻煩）算法過程：算法過程：1.將各邊按權(quán)值從小到大進(jìn)行排序?qū)⒏鬟叞礄?quán)值從小到大進(jìn)行排序2.找出權(quán)值最小且找出權(quán)值最小且不與已加入最小生成樹集合的邊構(gòu)成回路不與已加入最小生成樹集合的邊構(gòu)成回路的的邊。若符合條件，則加入最小生成樹的集合中。不符合條件則邊。若符合條件，則加入最小生成樹的集合中。不符合條件則繼續(xù)遍歷圖，尋找下一個(gè)最小權(quán)值

31、的邊。繼續(xù)遍歷圖，尋找下一個(gè)最小權(quán)值的邊。3.遞歸重復(fù)步驟遞歸重復(fù)步驟1，直到找出，直到找出n-1條邊為止，得到最小生成樹。條邊為止，得到最小生成樹。時(shí)間復(fù)雜度時(shí)間復(fù)雜度只和邊有關(guān)，可以證明其時(shí)間復(fù)雜度為只和邊有關(guān)，可以證明其時(shí)間復(fù)雜度為O(mlogm)求最小生成樹40?2?4?4?2?1?3?7?2?8?6?7?3?B?C?A?F?D?G?E?2?2?1?3?6?3?E?G?D?F?A?C?BPrimPrim算法41 把結(jié)點(diǎn)分成兩個(gè)集合，已加入樹中的把結(jié)點(diǎn)分成兩個(gè)集合，已加入樹中的( (P P) )和未加入樹中的和未加入樹中的( (Q Q) )，然后每次選擇一個(gè)點(diǎn)在然后每次選擇一個(gè)點(diǎn)在P P

32、中一個(gè)點(diǎn)在中一個(gè)點(diǎn)在Q Q中的權(quán)重最小的邊，加入樹中的權(quán)重最小的邊，加入樹中，并把相應(yīng)點(diǎn)加入中，并把相應(yīng)點(diǎn)加入P P中。中。類似地類似地, ,可定義連通圖可定義連通圖G 的最大生成樹的最大生成樹. .算法過程：算法過程：1：初始化：任取一個(gè)節(jié)點(diǎn)：初始化：任取一個(gè)節(jié)點(diǎn)u加入生成樹加入生成樹,P=u0, Q=V-u0, 生成樹的邊集生成樹的邊集TE=。2：在所有：在所有uP,vQ的邊的邊(u,v) （稱為可選邊集稱為可選邊集）中，找一條權(quán)重最小的）中，找一條權(quán)重最小的邊邊(u1,v1)，將此邊加進(jìn)集合，將此邊加進(jìn)集合TE中，并將中，并將v加入加入P中。同時(shí)對與中。同時(shí)對與v關(guān)聯(lián)的邊，若關(guān)聯(lián)的邊，若

33、另一個(gè)端點(diǎn)已經(jīng)在另一個(gè)端點(diǎn)已經(jīng)在P中，則從可選邊集中刪除，否則加入可選邊集。中，則從可選邊集中刪除，否則加入可選邊集。3：如果：如果P=V，則算法結(jié)束；否則重復(fù)步驟，則算法結(jié)束；否則重復(fù)步驟2。 我們可以算出當(dāng)我們可以算出當(dāng)U=V時(shí)，步驟時(shí)，步驟2共執(zhí)行了共執(zhí)行了n1次，次，TE中也增加了中也增加了n1條條邊，這邊，這n1條邊就是需要求出的最小生成樹的邊。條邊就是需要求出的最小生成樹的邊。例 選址問題 現(xiàn)準(zhǔn)備現(xiàn)準(zhǔn)備在在 n 個(gè)個(gè)居民點(diǎn)居民點(diǎn)v1, v2, , vn中設(shè)置一銀行中設(shè)置一銀行. .問問設(shè)在哪個(gè)點(diǎn)設(shè)在哪個(gè)點(diǎn), ,可使最大服務(wù)距離最小可使最大服務(wù)距離最小? ? 若設(shè)置兩個(gè)銀行若設(shè)置兩個(gè)

34、銀行, ,問設(shè)在哪兩個(gè)點(diǎn)問設(shè)在哪兩個(gè)點(diǎn)? ? 模型假設(shè)模型假設(shè) 假設(shè)各假設(shè)各個(gè)個(gè)居民點(diǎn)都有條件設(shè)置銀行居民點(diǎn)都有條件設(shè)置銀行, ,并并有路相連有路相連, ,且路長已知且路長已知. . 模型建立與求解模型建立與求解 用用Floyd算法求出任意兩算法求出任意兩個(gè)個(gè)居民居民點(diǎn)點(diǎn)vi , vj 之間的最短距離之間的最短距離, ,并用并用dij 表示表示. . 設(shè)置一個(gè)銀行設(shè)置一個(gè)銀行, ,銀行設(shè)銀行設(shè)在在 vi 點(diǎn)點(diǎn)的最大服務(wù)距離為的最大服務(wù)距離為.,.,2 , 1,max1niddijnji43求求k, ,使使.min1inikdd 即若設(shè)置一個(gè)銀行即若設(shè)置一個(gè)銀行, ,則銀行設(shè)在則銀行設(shè)在 vk

35、點(diǎn)點(diǎn), ,可使最大服務(wù)距離最小可使最大服務(wù)距離最小. . 設(shè)置兩個(gè)銀行設(shè)置兩個(gè)銀行, ,假設(shè)銀行設(shè)假設(shè)銀行設(shè)在在vs , vt 點(diǎn)點(diǎn)使最大服務(wù)距離最小使最大服務(wù)距離最小. .記記.,minmax),(1jkiknkddjid則則s, ,t 滿足：滿足：).,(min),(1jidtsdnji進(jìn)一步進(jìn)一步, ,若設(shè)置多個(gè)銀行呢？若設(shè)置多個(gè)銀行呢？4 4、遍歷性問題一、歐拉圖G=(V,E)為一連通無向圖經(jīng)過G中每條邊至少一次的回路稱為巡回；經(jīng)過G中每條邊正好一次的巡回稱為歐拉巡回；存在歐拉巡回的圖稱為歐拉圖。二、中國郵遞員問題（CPPchinese?postman?problem）?一名郵遞員負(fù)責(zé)

36、投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？這一問題是我國管梅谷教授1962年首先提出，國際上稱之為中國郵遞員問題。?44解法： 若本身就是歐拉圖，則直接可以找到一條歐拉巡回就是若本身就是歐拉圖，則直接可以找到一條歐拉巡回就是本問題的解。本問題的解。 若不是歐拉圖，必定有偶數(shù)個(gè)奇度數(shù)結(jié)點(diǎn)，在這些奇度若不是歐拉圖，必定有偶數(shù)個(gè)奇度數(shù)結(jié)點(diǎn)，在這些奇度數(shù)點(diǎn)之間添加一些邊，使之變成歐拉圖，再找出一個(gè)歐數(shù)點(diǎn)之間添加一些邊，使之變成歐拉圖，再找出一個(gè)歐拉巡回。拉巡回。具體解法：Fleury算法+Edmonds最小對集算法45三、哈密爾

37、頓圖G=(V,E)為一連通無向圖經(jīng)過G中每點(diǎn)一次且正好一次的路徑稱為哈密爾頓路徑；經(jīng)過G中每點(diǎn)一次且正好一次的回路稱為哈密爾頓回路；存在哈密爾頓回路的圖稱為哈密爾頓圖。四、旅行商問題（TSPTraveling?Salesman?Problem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線？ 即：從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地（最小哈密爾頓回路）對于n個(gè)節(jié)點(diǎn)的旅行商問題，n個(gè)節(jié)點(diǎn)的任意一個(gè)全排列都是問題的一個(gè)可能解（假設(shè)任意兩個(gè)點(diǎn)之間都有邊）。G個(gè)節(jié)點(diǎn)的全排列有(n-1)!個(gè)，因此間題歸結(jié)為在(n-1)!個(gè)回路中選取最小回路。 TSP問題的解法屬于NP

38、NP完全問題，一般只研究其近似解法46最鄰近算法(1) 選取任意一個(gè)點(diǎn)作為起始點(diǎn),找出與該點(diǎn)相關(guān)聯(lián)的權(quán)重最小的邊,形成一條初始路徑.(2) 找出與最新加入到路徑中的點(diǎn)相關(guān)聯(lián)的權(quán)重最小的邊加入到路徑中,且要求不再路徑中產(chǎn)生回路.(3) 重復(fù)(2)直到所有的結(jié)點(diǎn)都加入到路徑中.(4) 將起點(diǎn)和最后加入的結(jié)點(diǎn)之間的邊加入到路徑中,形成Hamilton回路.其他數(shù)值算法： 人工神經(jīng)元方法， 遺傳算法等等475 5、二分圖與匹配 定義定義1 1 設(shè)設(shè)X, ,Y 都是非空有限集都是非空有限集, ,且且XY = , , E xy| |xX, ,yY, , 稱稱G =(X, Y, E)為為二部圖二部圖. .

39、二部圖可認(rèn)為是有限簡單無向圖二部圖可認(rèn)為是有限簡單無向圖. . 如果如果X中的每個(gè)點(diǎn)都與中的每個(gè)點(diǎn)都與Y中的每個(gè)點(diǎn)鄰接中的每個(gè)點(diǎn)鄰接, ,則稱則稱G =(X, Y, E)為為完備二部圖完備二部圖. . 若若F：ER + +, ,則稱則稱G =(X, Y, E, F )為為二部賦權(quán)圖二部賦權(quán)圖. . 二部賦權(quán)圖的權(quán)矩陣一般記作二部賦權(quán)圖的權(quán)矩陣一般記作A=(aij )|X|Y | , ,其中其中aij = F (xi yj ). .49 定義定義2 2 設(shè)設(shè)G =(X, Y, E)為二部圖為二部圖, ,且且M E. .若若M中任意兩條邊中任意兩條邊在在G中均不鄰接中均不鄰接, ,則稱則稱M是是二

40、部圖二部圖G的一個(gè)的一個(gè)匹配匹配. . 定義定義3 3 設(shè)設(shè)M是二部圖是二部圖G的一個(gè)匹配的一個(gè)匹配, ,如果如果G的每一個(gè)點(diǎn)都是的每一個(gè)點(diǎn)都是M中邊的頂中邊的頂點(diǎn)點(diǎn), ,則稱則稱M是二部圖是二部圖G的的完美匹配完美匹配； 如果如果G中沒有另外的匹配中沒有另外的匹配M0 , ,使使| |M0| | |M|,|,則稱則稱M是二部圖是二部圖G的的最大匹配最大匹配. . 在二部賦權(quán)圖在二部賦權(quán)圖G =(X, Y, E, F )中中, ,權(quán)數(shù)最大的最大匹配權(quán)數(shù)最大的最大匹配M稱為稱為二部賦權(quán)圖二部賦權(quán)圖G的的最佳匹配最佳匹配. . 顯然顯然, ,每個(gè)完美匹配都是最大匹配每個(gè)完美匹配都是最大匹配, ,反

41、之不一定成立反之不一定成立. .工作安排問題之一 50 給給n個(gè)工作人員個(gè)工作人員x1, x2, , xn安排安排n項(xiàng)工作項(xiàng)工作y1, y2, , yn. . n個(gè)工作人員中每個(gè)人能勝任一項(xiàng)或幾項(xiàng)工作個(gè)工作人員中每個(gè)人能勝任一項(xiàng)或幾項(xiàng)工作, 但并但并不是所有不是所有工作人員都能從事任何一項(xiàng)工作工作人員都能從事任何一項(xiàng)工作. 比如比如x1能做能做y1, y2工作工作, x2能能做做y2, y3, y4工作等工作等. 這樣便提出一個(gè)問題這樣便提出一個(gè)問題, 對所有的工作人員能不能都分配對所有的工作人員能不能都分配一件他所能勝任的工作？一件他所能勝任的工作？ 我們構(gòu)造一個(gè)二部圖我們構(gòu)造一個(gè)二部圖G

42、= ( X, Y, E ), 這里這里X = x1, x2, , xn,Y = y1, y2, , yn, 并且當(dāng)且僅當(dāng)工作人員并且當(dāng)且僅當(dāng)工作人員xi勝任工作勝任工作yj時(shí)時(shí), xi與與yj才相鄰才相鄰. 于是于是, 問題轉(zhuǎn)化為求二部圖的一個(gè)完美匹配問題轉(zhuǎn)化為求二部圖的一個(gè)完美匹配. 因?yàn)橐驗(yàn)?|X|=|Y|, 所以完美匹配即為最大匹配所以完美匹配即為最大匹配. 51 求二部圖G = ( X, Y, E )的最大匹配算法( (匈牙利算法, ,交替鏈算法) )迭代步驟: 從從G的任意匹配的任意匹配M開始開始. . 將將X中中M的所有的所有非飽和點(diǎn)非飽和點(diǎn)都給以標(biāo)號都給以標(biāo)號0 0和標(biāo)記和標(biāo)記*

43、 *, , 轉(zhuǎn)向轉(zhuǎn)向. . M的非飽和點(diǎn)即非的非飽和點(diǎn)即非M的某條邊的頂點(diǎn)的某條邊的頂點(diǎn). . 若若X中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記* *, , 則則M是是G的最大的最大匹配匹配. . 否則任取否則任取X中一個(gè)既有標(biāo)號又有標(biāo)記中一個(gè)既有標(biāo)號又有標(biāo)記* *的點(diǎn)的點(diǎn)xi , , 去掉去掉xi的標(biāo)的標(biāo)記記* *, , 轉(zhuǎn)向轉(zhuǎn)向. . 找出在找出在G中所有與中所有與xi鄰接的點(diǎn)鄰接的點(diǎn)yj , , 若所有這樣的若所有這樣的yj都已有標(biāo)都已有標(biāo)號號, , 則轉(zhuǎn)向則轉(zhuǎn)向, , 否則轉(zhuǎn)向否則轉(zhuǎn)向. .52 對與對與xi鄰接且尚未給標(biāo)號的鄰接且尚未給標(biāo)號的yj都給定標(biāo)號都給定標(biāo)號

44、i. . 若所有的若所有的 yj 都是都是M的的飽和點(diǎn)飽和點(diǎn), ,則轉(zhuǎn)向則轉(zhuǎn)向, ,否則逆向返回否則逆向返回. . 即由即由其中其中M的任一個(gè)非飽和點(diǎn)的任一個(gè)非飽和點(diǎn) yj 的標(biāo)號的標(biāo)號i 找到找到xi , ,再由再由 xi 的標(biāo)號的標(biāo)號k 找到找到 yk , , ,最后由最后由 yt 的標(biāo)號的標(biāo)號s找到標(biāo)號為找到標(biāo)號為0 0的的xs時(shí)結(jié)束時(shí)結(jié)束, ,獲得獲得M- -增廣路增廣路xs yt xi yj , , 記記P = xs yt , , xi yj ,重新記重新記M為為M P, ,轉(zhuǎn)向轉(zhuǎn)向. . 不必理會不必理會M- -增廣路增廣路的定義的定義. . M P = MP MP, , 是對稱差

45、是對稱差. . 將將yj在在M中與之鄰接的點(diǎn)中與之鄰接的點(diǎn)xk , ,給以標(biāo)號給以標(biāo)號 j 和標(biāo)記和標(biāo)記* *, , 轉(zhuǎn)向轉(zhuǎn)向. .例 求下圖所示二部圖G的最大匹配53解解 取初始匹配取初始匹配M0 = x2 y2 , x3 y3 , x5 y5 ( (上圖粗線所示上圖粗線所示). ). 給給X中中M0的兩個(gè)非飽和點(diǎn)的兩個(gè)非飽和點(diǎn)x1, ,x4都給以標(biāo)號都給以標(biāo)號0 0和標(biāo)記和標(biāo)記* * ( (如如下圖所示下圖所示). ). 去掉去掉x1的標(biāo)記的標(biāo)記*, 將與將與x1鄰接的兩個(gè)點(diǎn)鄰接的兩個(gè)點(diǎn)y2, y3都給以標(biāo)號都給以標(biāo)號1.1. 因因?yàn)闉閥2, y3都是都是M0的兩個(gè)飽和點(diǎn)的兩個(gè)飽和點(diǎn), ,

46、所以將它們在所以將它們在M0中鄰接的兩個(gè)點(diǎn)中鄰接的兩個(gè)點(diǎn)x2, x3都給以相應(yīng)的標(biāo)號和標(biāo)記都給以相應(yīng)的標(biāo)號和標(biāo)記* (如下圖所示如下圖所示). 54 去掉去掉x2的標(biāo)記的標(biāo)記*, 將與將與x2鄰接且尚未給標(biāo)號的三個(gè)點(diǎn)鄰接且尚未給標(biāo)號的三個(gè)點(diǎn)y1, y4, y5都給以標(biāo)號都給以標(biāo)號2 (如下圖所示如下圖所示). 因?yàn)橐驗(yàn)閥1是是M0的非飽和點(diǎn)的非飽和點(diǎn), 所以順著標(biāo)號逆向返回依次得到所以順著標(biāo)號逆向返回依次得到x2, y2, 直到直到x1為為0為止為止. .于是得到于是得到M0的增廣路的增廣路x1 y2x2 y1, 記記P = x1 y2 , y2x2 , x2 y1. 取取M1 = M0P =

47、 x1 y2 , x2 y1 , x3 y3 , x5 y5, 則則M1是比是比M多一邊的匹配多一邊的匹配(如下圖所示如下圖所示). 再給再給X中中M1的非飽和點(diǎn)的非飽和點(diǎn)x4給以標(biāo)號給以標(biāo)號0和標(biāo)記和標(biāo)記*, 然后去掉然后去掉x4的的標(biāo)記標(biāo)記*, 將與將與x4鄰接的兩個(gè)點(diǎn)鄰接的兩個(gè)點(diǎn)y2, y3都給以標(biāo)號都給以標(biāo)號4. 因?yàn)橐驗(yàn)閥2, y3都是都是M1的兩個(gè)飽和點(diǎn)的兩個(gè)飽和點(diǎn), , 所以將它們在所以將它們在M1中鄰接的兩中鄰接的兩個(gè)點(diǎn)個(gè)點(diǎn)x1, x3都給以相應(yīng)的標(biāo)號和標(biāo)記都給以相應(yīng)的標(biāo)號和標(biāo)記* (如下圖所示如下圖所示). 去掉去掉x1的標(biāo)記的標(biāo)記*, 因?yàn)榕c因?yàn)榕cx1鄰接的兩個(gè)點(diǎn)鄰接的兩個(gè)

48、點(diǎn)y2, y3都有標(biāo)號都有標(biāo)號4, 所所以去掉以去掉x3的標(biāo)記的標(biāo)記*. 而與而與x3鄰接的兩個(gè)點(diǎn)鄰接的兩個(gè)點(diǎn)y2, y3也都有標(biāo)號也都有標(biāo)號4, 此時(shí)此時(shí)X中所有有標(biāo)號中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記的點(diǎn)都已去掉了標(biāo)記*(如下圖所示如下圖所示), 因此因此M1是是G的最大匹配的最大匹配. G不存在飽和不存在飽和X的每個(gè)點(diǎn)的匹配的每個(gè)點(diǎn)的匹配, 當(dāng)然也不存在完美匹配當(dāng)然也不存在完美匹配.工作安排問題之二 56 給給n個(gè)工作人員個(gè)工作人員x1, x2, , xn安排安排n項(xiàng)工作項(xiàng)工作y1, y2, , yn. . 如如果每個(gè)工作人員工作效率不同果每個(gè)工作人員工作效率不同, 要求工作分配的同時(shí)考慮總

49、效要求工作分配的同時(shí)考慮總效率最高率最高. 我們構(gòu)造一個(gè)二部賦權(quán)圖我們構(gòu)造一個(gè)二部賦權(quán)圖G = ( X, Y, E , F ), 這里這里X = x1, x2, , xn,Y = y1, y2, , yn, F(xi yj )為工作人員為工作人員xi勝任工作勝任工作yj時(shí)的工作效率時(shí)的工作效率. 則問題轉(zhuǎn)化為：求二部賦權(quán)圖則問題轉(zhuǎn)化為：求二部賦權(quán)圖G的最佳匹配的最佳匹配. 在求在求G 的最佳匹配時(shí)的最佳匹配時(shí), 總可以假設(shè)總可以假設(shè)G為完備二部賦權(quán)圖為完備二部賦權(quán)圖. .若若xi與與yj不相鄰不相鄰, 可令可令F(xi yj )=0. 同樣地同樣地, 還可虛設(shè)點(diǎn)還可虛設(shè)點(diǎn)x或或y, ,使使|X

50、|=|Y|. .如此就將如此就將G 轉(zhuǎn)化為完備二部賦權(quán)圖轉(zhuǎn)化為完備二部賦權(quán)圖, ,而且不會影響結(jié)果而且不會影響結(jié)果. 定義定義 設(shè)設(shè)G =( (X, Y, E, F) )為完備的二部賦權(quán)圖為完備的二部賦權(quán)圖, , 若若L：X Y R + + 滿足：滿足： xX, yY, L(x) + L(y)F(xy), ,則稱則稱L為為G的一個(gè)的一個(gè)可行點(diǎn)標(biāo)記可行點(diǎn)標(biāo)記, ,記相應(yīng)的生成子圖為記相應(yīng)的生成子圖為GL =( (X, Y, EL , F),),這里這里EL = xyE| |L(x) + L (y) = F (xy). 求完備二部賦權(quán)圖求完備二部賦權(quán)圖G = (X, Y, E, F )的最佳匹配算

51、法迭代步驟：的最佳匹配算法迭代步驟： 設(shè)設(shè)G =( (X, Y, E, F) )為完備的二部賦權(quán)圖為完備的二部賦權(quán)圖, ,L是其一個(gè)初始可是其一個(gè)初始可行點(diǎn)標(biāo)記行點(diǎn)標(biāo)記, ,通常取通常取 L(x) = max F (x y) | yY , xX, L(y) = 0, , yY. 58M是是GL的一個(gè)匹配的一個(gè)匹配. . 若若X的每個(gè)點(diǎn)都是飽和的的每個(gè)點(diǎn)都是飽和的,則則M是最佳匹配是最佳匹配.否則取否則取M的非飽和點(diǎn)的非飽和點(diǎn)uX,令令S =u, T = ,轉(zhuǎn)向轉(zhuǎn)向. 記記NL(S)=v|uS,uvGL. 若若NL(S)= T, 則則GL沒有完美匹配沒有完美匹配, 轉(zhuǎn)向轉(zhuǎn)向. 否則轉(zhuǎn)向否則轉(zhuǎn)向.

52、 調(diào)整標(biāo)記調(diào)整標(biāo)記, 計(jì)算計(jì)算aL=minL(x) + L (y) - - F (xy)|xS, yYT. 由此得新的可行點(diǎn)標(biāo)記由此得新的可行點(diǎn)標(biāo)記.),(,)(,)()(ccLLTSvvLTvavLSvavLvH 令令L = H, GL = GH , 重新給出重新給出GL的一個(gè)匹配的一個(gè)匹配M, 轉(zhuǎn)向轉(zhuǎn)向. 取取yNL (S) T , 若若y是是M的飽和點(diǎn)的飽和點(diǎn), 轉(zhuǎn)向轉(zhuǎn)向. 否則否則, 轉(zhuǎn)向轉(zhuǎn)向. 設(shè)設(shè)x yM, 則令則令S = S x , T = T y , 轉(zhuǎn)向轉(zhuǎn)向. 在在GL中的中的u - - y路是路是M- - 增廣路增廣路, 設(shè)為設(shè)為P, 并令并令 M = M P, 轉(zhuǎn)向轉(zhuǎn)向.

53、 6 6、網(wǎng)絡(luò)流問題 59 定義定義1 1 設(shè)設(shè)G =(V, E )為有向圖為有向圖, ,在在V中指定一點(diǎn)稱為中指定一點(diǎn)稱為發(fā)點(diǎn)發(fā)點(diǎn)( (記為記為vs ),),和另一點(diǎn)稱為和另一點(diǎn)稱為收點(diǎn)收點(diǎn)( (記為記為vt ), ), 其余點(diǎn)叫做中間點(diǎn)其余點(diǎn)叫做中間點(diǎn). . 對每一條邊對每一條邊vivjE, ,對應(yīng)一個(gè)非負(fù)實(shí)數(shù)對應(yīng)一個(gè)非負(fù)實(shí)數(shù)Cij , ,稱為它的稱為它的容量容量. . 這樣的這樣的G稱為稱為容量容量網(wǎng)絡(luò)網(wǎng)絡(luò), ,簡稱簡稱網(wǎng)絡(luò)網(wǎng)絡(luò), ,記作記作G = (V, E, C ). . 定義定義2 2 網(wǎng)絡(luò)網(wǎng)絡(luò)G = (V, E, C )中任一條邊中任一條邊vivj有流量有流量 fij , ,稱集

54、合稱集合 f = fij 為網(wǎng)絡(luò)為網(wǎng)絡(luò)G上的一個(gè)上的一個(gè)流流. . 滿足下述條件的流滿足下述條件的流 f 稱為稱為可行流可行流： ( (限制條件限制條件) )對每一邊對每一邊vivj , ,有有0 fij Cij ; ( (平衡條件平衡條件) )對于中間點(diǎn)對于中間點(diǎn)vk有有fik =fkj , , 即中間點(diǎn)即中間點(diǎn)vk的輸入的輸入量量 = 輸出輸出量量. . 如果如果 f 是可行流是可行流, ,則對收、發(fā)點(diǎn)則對收、發(fā)點(diǎn)vt、vs有有fsi =fjt =Wf , ,即從即從vs點(diǎn)發(fā)出的物質(zhì)總量點(diǎn)發(fā)出的物質(zhì)總量 = vt點(diǎn)輸入的量點(diǎn)輸入的量. .Wf 稱為網(wǎng)絡(luò)流稱為網(wǎng)絡(luò)流 f 的總流量的總流量.

55、. 上述概念可以這樣來理解上述概念可以這樣來理解, ,如如G是一個(gè)運(yùn)輸網(wǎng)絡(luò)是一個(gè)運(yùn)輸網(wǎng)絡(luò), ,則發(fā)點(diǎn)則發(fā)點(diǎn)vs表示表示發(fā)送站發(fā)送站, ,收點(diǎn)收點(diǎn)vt表示接收站表示接收站, ,中間點(diǎn)中間點(diǎn)vk表示中間轉(zhuǎn)運(yùn)站表示中間轉(zhuǎn)運(yùn)站, ,可行流可行流 fij 表表示某條運(yùn)輸線上通過的運(yùn)輸量示某條運(yùn)輸線上通過的運(yùn)輸量, ,容量容量Cij表示某條運(yùn)輸線能承擔(dān)的最表示某條運(yùn)輸線能承擔(dān)的最大運(yùn)輸量大運(yùn)輸量, ,Wf 表示運(yùn)輸總量表示運(yùn)輸總量. . 可行流總是存在的可行流總是存在的. .比如所有邊的流量比如所有邊的流量 fij = 0就是一個(gè)可行流就是一個(gè)可行流( (稱為零流稱為零流).). 所謂所謂最大流問題最大流

56、問題就是在容量網(wǎng)絡(luò)中就是在容量網(wǎng)絡(luò)中, ,尋找流量最大的可行流尋找流量最大的可行流. . 實(shí)際問題中實(shí)際問題中, ,一個(gè)網(wǎng)絡(luò)會出現(xiàn)下面兩種情況：一個(gè)網(wǎng)絡(luò)會出現(xiàn)下面兩種情況： 發(fā)點(diǎn)和收點(diǎn)都不止一個(gè)發(fā)點(diǎn)和收點(diǎn)都不止一個(gè). . 解決的方法是再虛設(shè)一個(gè)發(fā)點(diǎn)解決的方法是再虛設(shè)一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)和一個(gè)收點(diǎn)vt , ,發(fā)點(diǎn)發(fā)點(diǎn)vs到所有到所有原發(fā)點(diǎn)邊的容量都設(shè)為無窮大原發(fā)點(diǎn)邊的容量都設(shè)為無窮大, , 所有原收點(diǎn)到收點(diǎn)所有原收點(diǎn)到收點(diǎn)vt 邊的容量都邊的容量都設(shè)為無窮大設(shè)為無窮大. . 網(wǎng)絡(luò)中除了邊有容量外網(wǎng)絡(luò)中除了邊有容量外, ,點(diǎn)也有容量點(diǎn)也有容量. . 解決的方法是將所有有容量的點(diǎn)分成兩個(gè)點(diǎn)解決的方

57、法是將所有有容量的點(diǎn)分成兩個(gè)點(diǎn), ,如點(diǎn)如點(diǎn)v有容量有容量Cv , ,將點(diǎn)將點(diǎn)v分成兩個(gè)點(diǎn)分成兩個(gè)點(diǎn)v和和v, ,令令C(vv ) = Cv . . 最小費(fèi)用流問題 62 這里我們要進(jìn)一步探討不僅要使網(wǎng)上的流達(dá)到最大這里我們要進(jìn)一步探討不僅要使網(wǎng)上的流達(dá)到最大, ,或者達(dá)或者達(dá)到要求的預(yù)定值到要求的預(yù)定值, ,而且還要使運(yùn)輸流的費(fèi)用是最小的而且還要使運(yùn)輸流的費(fèi)用是最小的, ,這就是最小這就是最小費(fèi)用流問題費(fèi)用流問題. . 最小費(fèi)用流問題的一般提法：最小費(fèi)用流問題的一般提法： 已知網(wǎng)絡(luò)已知網(wǎng)絡(luò)G = (V, E, C ), ,每條邊每條邊vivjE 除了已給容量除了已給容量Cij外外, ,還還給

58、出了單位流量的費(fèi)用給出了單位流量的費(fèi)用bij(0).). 所謂最小費(fèi)用流問題就是求一個(gè)總流量已知的可行流所謂最小費(fèi)用流問題就是求一個(gè)總流量已知的可行流 f = f ij 使得總費(fèi)用使得總費(fèi)用ijEvvijfbfbji)(最小最小. .63 特別地特別地, ,當(dāng)要求當(dāng)要求 f 為最大流時(shí)為最大流時(shí), , 即為即為最小費(fèi)用最大流問題最小費(fèi)用最大流問題. . 設(shè)網(wǎng)絡(luò)設(shè)網(wǎng)絡(luò)G = (V, E, C), 取初始可行流取初始可行流 f 為零流為零流, 求解最小費(fèi)用流求解最小費(fèi)用流問題的迭代步驟：問題的迭代步驟： 構(gòu)造有向賦權(quán)圖構(gòu)造有向賦權(quán)圖Gf =( (V, Ef , F),),對于任意的對于任意的viv

59、jE, ,Ef , ,F 的定義如下：的定義如下： 當(dāng)當(dāng) f ij = 0時(shí)時(shí), ,vivjEf , ,F(vivj )= bij ; 當(dāng)當(dāng) f ij = Cij時(shí)時(shí), ,vjviEf , ,F(vjvi )= - - bij ; 當(dāng)當(dāng)0 f ijCij時(shí)時(shí), ,vivjEf , ,F(vivj )= bij , ,vjviEf , , F(vjvi ) = - - bij . . 然后然后轉(zhuǎn)向轉(zhuǎn)向. .64 求出含有負(fù)權(quán)的有向賦權(quán)圖求出含有負(fù)權(quán)的有向賦權(quán)圖Gf =( (V, Ef , F) )中發(fā)點(diǎn)中發(fā)點(diǎn)vs到收點(diǎn)到收點(diǎn)vt的最短路的最短路 , ,若最若最短路短路 存在轉(zhuǎn)向存在轉(zhuǎn)向; 否則否

60、則f是所求的最小費(fèi)用最是所求的最小費(fèi)用最大流大流, ,停止停止. . 增流增流. .,jiijjiijijijvvfvvfCvivj與與 相同相同, ,vivj與與 相反相反. .令令 = min ij| |vivj , 重新定義流重新定義流 f = f ij 為為.,jiijjiijijvvfvvff其它情況不變其它情況不變. . 如果如果Wf 大于或等于預(yù)定的流量值大于或等于預(yù)定的流量值, ,則適當(dāng)減少則適當(dāng)減少 值值, ,使使Wf 等等于預(yù)定的流量值于預(yù)定的流量值, ,那么那么 f 是是所求的最小費(fèi)用流所求的最小費(fèi)用流, , 停止停止; 否則轉(zhuǎn)向否則轉(zhuǎn)向. .65 下面介紹求解有向賦權(quán)圖