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

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

2、發(fā)，必能通過每座橋恰好一次而回到出發(fā)地陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地. .第3頁/共91頁4問題問題2(2(哈密頓環(huán)球旅行哈密頓環(huán)球旅行問題問題):): 十二面體的十二面體的2020個頂點代表世界上個頂點代表世界上2020個城市，個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？城市恰好一次最后回到出發(fā)點？歐拉問題是歐拉問題是“邊遍歷邊遍歷”，哈密爾頓問題是，哈密爾頓問題是“點遍歷點遍歷”第4頁/共91頁5問題問題3(3(四色問題四色問題):): 對任何一張地圖進行著色，兩個共同邊界的國家染不同的顏對任何一張地

3、圖進行著色，兩個共同邊界的國家染不同的顏色，則只需要四種顏色就夠了色，則只需要四種顏色就夠了. .問題4(4(關(guān)鍵路徑問題):): 一項工程任務(wù), ,大到建造一座大壩, ,一座體育中心, ,小至組裝一臺機床, ,一架電視機, , 都要包括許多工序. .這些工序相互約束, ,只有在某些工序完成之后, , 一個工序才能開始. . 即它們之間存在完成的先后次序關(guān)系, ,一般認為這些關(guān)系是預(yù)知的, , 而且也能夠預(yù)計完成每個工序所需要的時間. . 這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項目, , 影響工程進度的要害工序是哪幾個？ 第5頁/共91頁圖的定義 圖論中的“圖”并不是通

4、常意義下的幾何圖形或物體的形狀圖, , 而是以一種抽象的形式來表達一些確定的事物之間的聯(lián)系的一個數(shù)學(xué)系統(tǒng). . 定義定義1 一個有序二元組(V, E ) 稱為一個圖圖, 記為G = (V, E ), 其中 V稱為G的頂點集, V , 其元素稱為頂點頂點或結(jié)點結(jié)點, 簡稱點點; E稱為G的邊集, 其元素稱為邊邊, 它聯(lián)結(jié)V 中的兩個點, 如果這兩個點是無序的, 則稱該邊為無向邊無向邊, 否則, 稱為有向邊有向邊. 如果V = v1, v2, , vn是有限非空點集, 則稱G為有限圖有限圖或n階圖階圖. 第6頁/共91頁7 如果E的每一條邊都是無向邊, 則稱G為無向圖無向圖( (如圖1)1); 如

5、果E的每一條邊都是有向邊, 則稱G為有向圖有向圖( (如圖2)2); 否則, 稱G為混合圖混合圖. 圖1 1 圖2 2并且常記: :V = v1, v2, , vn, |V | = n ;E = e1, e2, , em(ek=vivj ) , |E | = m.稱點vi , vj為邊vivj的端點端點. 在有向圖中, 稱點vi , vj分別為邊vivj的始點始點和終點終點. 該圖稱為(n,m)圖圖第7頁/共91頁8 對于一個圖G = (V, E ), 人們常用圖形來表示它, 稱其為圖解圖解. 凡是有向邊, 在圖解上都用箭頭標(biāo)明其方向. 例如, 設(shè)V = v1 , v2 , v3 , v4,

6、E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 則G = (V, E ) 是一個有4個頂點和6條邊的圖, G的圖解如下圖所示. 第8頁/共91頁9 一個圖會有許多外形不同的圖解, , 下面兩個圖表示同一個圖G = (V, E )的圖解. .這兩個圖互為同構(gòu)圖同構(gòu)圖, ,今后將不計較這種外形上的差別, ,而用一個容易理解的、確定的圖解去表示一個圖. . 第9頁/共91頁10 有邊聯(lián)結(jié)的兩個點稱為相鄰的點相鄰的點, 有一個公共端點的邊稱為相鄰邊相鄰邊. 邊和它的端點稱為互相關(guān)聯(lián)互相關(guān)聯(lián). 常用d(v)表示圖G中與頂點v關(guān)聯(lián)的邊的數(shù)目, d(v)稱為頂點v的

7、度數(shù)度數(shù). 對于有向圖,還有出度出度和入度入度之分. 用N(v)表示圖G中所有與頂點v相鄰的頂點的集合. d(v1)= d(v3)= d(v4)=4, d(v2)=2dout(v1)= dout (v3)= dout (v4)=2, dout(v2)=1din(v1)= din(v3)= din(v4)=2, din(v2)=1第10頁/共91頁11握手定理握手定理：無向圖中，所有結(jié)點的度數(shù)之和等于2m。右圖：推論1：無向圖中必有偶數(shù)個度數(shù)為奇數(shù)的結(jié)點。推論2：有向圖中所有結(jié)點的出度之和等于入度之和。d(v1)= d(v3)= d(v4)=4, d(v2)=2mvdnii2)(1147*2)(

8、1niivd第11頁/共91頁我們今后只討論有限簡單圖： (1) (1) 頂點個數(shù)是有限的; (2) (2) 任意一條邊有且只有兩個不同的點與它相互關(guān)聯(lián); (3) (3) 若是無向圖, , 則任意兩個頂點最多只有一條邊與之相聯(lián)結(jié); (4) (4) 若是有向圖, , 則任意兩個頂點最多只有兩條邊與之相聯(lián)結(jié). . 當(dāng)兩個頂點有兩條邊與之相聯(lián)結(jié)時，這兩條邊的方向相反. . 如果某個有限圖不滿足(2)(3)(4),(2)(3)(4),可在某條邊上增設(shè)頂點使之滿足. .第12頁/共91頁13 定義定義2 若將圖G的每一條邊e都對應(yīng)一個實數(shù)F (e), 則稱F (e)為該邊的權(quán)權(quán), 并稱圖G為賦權(quán)圖賦權(quán)圖

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

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

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

12、否則取0)，共有24 =16 種狀態(tài)。在河?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個狀態(tài)向量作為個狀態(tài)向量作為頂點頂點，將可能互相轉(zhuǎn)移的狀態(tài)用，將可能互相轉(zhuǎn)移的狀態(tài)用邊邊連接起來構(gòu)成一連接起來構(gòu)成一個圖。個圖。 利用圖論的相關(guān)知識即可回答原問題。第19頁/共91頁例 過河問題(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

13、,1,0) (0,1,0,0) (0,1,0,1)(0,1,0,1) (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)|=(人,狼,羊,菜) 將10個頂點分別記為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之間有多少條不同的路徑？ 最快

14、的解決方案是什么？即： A1到A10最短路徑有哪些？第20頁/共91頁圖的矩陣表示圖的矩陣表示 鄰接矩陣：鄰接矩陣表示了點與點之間的鄰接關(guān)系. .一個n階圖G的鄰接矩陣A = (aij )nn , 其中 ., 0;, 1EvEvaijijij0101100101001010A21第21頁/共91頁22無向圖G的鄰接矩陣A是一個對稱矩陣. . 0101101101011110A 權(quán)矩陣 一個n階賦權(quán)圖G = (V, E, F)的權(quán)矩陣A = (aij ) nn , 其中 .,;0),(EvjiEvvvFaijijjiij有限簡單圖基本上可用權(quán)矩陣來表示. .第22頁/共91頁2305420370

15、860A無向圖G的權(quán)矩陣A是一個對稱矩陣. . 02420737064360A第23頁/共91頁24 關(guān)聯(lián)矩陣：一個有m條邊的n階有向圖G的關(guān)聯(lián)矩陣A = (aij )nm , 其中 若若vi是是ej的始點的始點;若若vi是是ej的終點的終點;若若vi與與ej不關(guān)聯(lián)不關(guān)聯(lián). ., 0, 1, 1ija 有向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有一個1,1,有且僅有一個 - - 1. 1. 1101100011011000000111011001A第24頁/共91頁25 一個有m條邊的n階無向圖G的關(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). .

16、, 0, 1ija 無向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個1. 1. 110100101010011001000111A第25頁/共91頁2 2、最短路徑算法 定義定義1 設(shè)P(u, v) 是賦權(quán)圖G = (V, E , F) 中從點u到v的路徑, 用E(P) 表示路徑P(u, v)中全部邊的集合, 記)()()(PEeeFPF則稱F (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的最短路最

17、短路. 第26頁/共91頁重要性質(zhì)：重要性質(zhì)： 若v0 v1 vm 是圖G中從v0到vm的最短路, 則 1km, v0v1 vk 必為G中從v0到vk的最短路. 即：最短路是一條路，且最短路的任一段也是最短路. 求非負賦權(quán)圖G中某一點到其它各點最短路，一般用Dijkstra標(biāo)號算法；求非負賦權(quán)圖上任意兩點間的最短路，一般用Floyd算法. . 這兩種算法均適用于有向非負賦權(quán)圖. . 下面分別介紹兩種算法的基本過程. .第27頁/共91頁Dijkstra算法 指標(biāo)（a為起點） 設(shè)T為V的子集，P=V-T且aT，對所有tT，設(shè) l(t)表示從a到t的所有通路中距離最短的一條的長度，且這條路徑中不包

18、含T中其他的結(jié)點，則稱l(t)為t關(guān)于集合P的指標(biāo)，若不存在這樣的路徑，這記l(t)= 注：l(t)不一定是從a到t的最短路徑，因為最短路徑中可能包含T中其他的節(jié)點。 定理1 若t是T中關(guān)于P由最小指標(biāo)的結(jié)點，則l(t)是a和t之間的最短距離。 定理2 設(shè) T為V的子集，P=V-T，設(shè) (1)對P中的任一點p,存在一條從a到p的最短路徑,這條路徑僅有P中的點構(gòu)成, (2)對于每一點t,它關(guān)于P的指標(biāo)為l(t),令x為最小指標(biāo)所在的點, 即: (3)令P=P Ux,T=T-x,l(t)表示T中結(jié)點t關(guān)于P的指標(biāo),則 28),()(),(min)( txwxltltlTttlxl),(min)(第

19、28頁/共91頁Dijkstra算法（求a點到其他點的最短路徑）1、初始化，、初始化，P=a，T=V-a，對每個結(jié)點，對每個結(jié)點t計算計算指標(biāo)指標(biāo) l(t)=w(a,t) 2、設(shè)、設(shè)x為為T中關(guān)于中關(guān)于P有最小指標(biāo)的點有最小指標(biāo)的點, 即即: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), 計算計算T中每一個結(jié)點中每一個結(jié)點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)矩

20、陣） 29第29頁/共91頁改進Dijkstra算法（求a點到其他點的最短路徑）1、初始化，、初始化，P=a，T=V-a，對每個結(jié)點，對每個結(jié)點t計算指標(biāo)計算指標(biāo) l(t)=w(a,t) ,pro(t)=a;2、設(shè)、設(shè)x為為T中關(guān)于中關(guān)于P有最小指標(biāo)的點有最小指標(biāo)的點, 即即: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), 計算計算T中每一個結(jié)點中每一個結(jié)點t關(guān)于關(guān)于P的指標(biāo)的指標(biāo). 若若 l(x)+w(x,t) l(t), pro(t)=x;4、P代替代替

21、P,T代替代替T,重復(fù)步驟重復(fù)步驟2,3 （ 其中：其中：w(x,y)為圖的權(quán)矩陣）為圖的權(quán)矩陣） 30第30頁/共91頁例 求下圖中A A點到其他點的最短路. .31第31頁/共91頁Floyd算法（求任意兩點的最短路徑） 設(shè)A = (aij )nn為賦權(quán)圖G = (V, E, F)的權(quán)矩陣, dij表示從vi到vj點的距離, rij表示從vi到vj點的最短路中前一個點的編號. 賦初值. 對所有i, j, dij = aij, rij = j. k = 1. 轉(zhuǎn)向. 更新dij , rij . 對所有i, j, 若dik + dk jdij , 則令dij = dik + dkj , rij

22、 = k, 轉(zhuǎn)向; 終止判斷. 若k = n終止; 否則令k = k + 1, 轉(zhuǎn)向. 最短路線可由rij得到. 第32頁/共91頁例 求下圖中任意兩點間的最短路. .3303030350201502051504510500A028338235803065508525035205540150352053015035452510450D533333143333113111133230142212142220R第33頁/共91頁例 設(shè)備更新問題 某企業(yè)每年年初, ,都要作出決定, ,如果繼續(xù)使用舊設(shè)備, ,要付維修費；若購買一臺新設(shè)備, ,要付購買費. .試制定一個5 5年更新計劃, ,使總支出最

23、少. . 已知設(shè)備在每年年初的購買費分別為11,11, 12,12,13. 11,11, 12,12,13. 使用不同時間設(shè)備所需的維修費分別為5,6,8,11,18.5,6,8,11,18. 解解 設(shè)bi 表示設(shè)備在第i 年年初的購買費, ,ci 表示設(shè)備使用i 年后的維修費, , V= v1, v2, , v6,點vi表示第i 年年初購進一臺新設(shè)備, ,虛設(shè)一個點v6表示第5 5年年底. . E = vivj | 1ij6,每條邊vivj表一臺設(shè)備，從第i年年初購買使用到第j年年初報廢.ijkkijicbvvF1)(第34頁/共91頁35 這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖G = (

24、V, E, F )(圖解如下) )中求v1到v6的最短路問題. 第35頁/共91頁36 由實際問題可知, ,設(shè)備使用三年后應(yīng)當(dāng)更新, ,因此刪除該圖中v1到v5 , ,v1到v6 , ,v2到v6的連線；又設(shè)備使用一年后就更新則不劃算, ,因此再刪除該圖中v1v2 , ,v2v3 , ,v3v4 , ,v4v5 , ,v5v6 五條連線后得到從上圖中容易得到v1到v6只有兩條路：v1v3v6和v1v4v6. . 而這兩條路都是v1到v6的最短路. .第36頁/共91頁3 3、最小生成樹 由樹的定義不難知道, 任意一個連通的(n,m)圖G適當(dāng)去掉m - - n +1條邊后, 都可以變成樹, 這棵

25、樹稱為圖G的生成樹生成樹. 設(shè)T是圖G的一棵生成樹, 用F(T)表示樹T中所有邊的權(quán)數(shù)之和, F(T)稱為樹樹T的權(quán)的權(quán). 一個連通圖G的生成樹一般不止一棵, 圖G的所有生成樹中權(quán)數(shù)最小的生成樹稱為圖G的最小生成樹最小生成樹-Minimum-cost Spanning Tree (MST). 求最小生成樹問題有很廣泛的實際應(yīng)用. 例如, 把n個鄉(xiāng)鎮(zhèn)用高壓電纜連接起來建立一個電網(wǎng), 使所用的電纜長度之和最短, 即費用最小, 就是一個求最小生成樹問題. 第37頁/共91頁Kruskal算法38 從未選入樹中的邊中選取權(quán)重最小的且不構(gòu)成回路的邊加入到樹中. .（判斷回路比較麻煩）算法過程：1.將各邊

26、按權(quán)值從小到大進行排序2.找出權(quán)值最小且不與已加入最小生成樹集合的邊構(gòu)成回路的邊。若符合條件，則加入最小生成樹的集合中。不符合條件則繼續(xù)遍歷圖，尋找下一個最小權(quán)值的邊。3.遞歸重復(fù)步驟1，直到找出n-1條邊為止，得到最小生成樹。時間復(fù)雜度只和邊有關(guān)，可以證明其時間復(fù)雜度為O(mlogm)第38頁/共91頁求最小生成樹39 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 B第39頁/共91頁Prim算法40 把結(jié)點分成兩個集合，已加入樹中的( (P P) )和未加入樹中的( (Q Q) )，然后每次選擇一個點在P P中一

27、個點在Q Q中的權(quán)重最小的邊，加入樹中，并把相應(yīng)點加入P P中。類似地, ,可定義連通圖G 的最大生成樹. .算法過程：1：初始化：任取一個節(jié)點u加入生成樹,P=u0, Q=V-u0, 生成樹的邊集TE=。2：在所有uP,vQ的邊(u,v) （稱為可選邊集）中，找一條權(quán)重最小的邊(u1,v1)，將此邊加進集合TE中，并將v加入P中。同時對與v關(guān)聯(lián)的邊，若另一個端點已經(jīng)在P中，則從可選邊集中刪除，否則加入可選邊集。3：如果P=V，則算法結(jié)束；否則重復(fù)步驟2。 我們可以算出當(dāng)U=V時，步驟2共執(zhí)行了n1次，TE中也增加了n1條邊，這n1條邊就是需要求出的最小生成樹的邊。第40頁/共91頁例 選址問

28、題 現(xiàn)準備在 n 個居民點v1, v2, , vn中設(shè)置一銀行. .問設(shè)在哪個點, ,可使最大服務(wù)距離最小? ? 若設(shè)置兩個銀行, ,問設(shè)在哪兩個點? ? 模型假設(shè) 假設(shè)各個居民點都有條件設(shè)置銀行, ,并有路相連, ,且路長已知. . 模型建立與求解 用Floyd算法求出任意兩個居民點vi , vj 之間的最短距離, ,并用dij 表示. . 設(shè)置一個銀行, ,銀行設(shè)在 vi 點的最大服務(wù)距離為.,.,2 , 1,max1niddijnji第41頁/共91頁42求k, ,使.min1inikdd 即若設(shè)置一個銀行, ,則銀行設(shè)在 vk 點, ,可使最大服務(wù)距離最小. . 設(shè)置兩個銀行, ,假設(shè)

29、銀行設(shè)在vs , vt 點使最大服務(wù)距離最小. .記.,minmax),(1jkiknkddjid則s, ,t 滿足：).,(min),(1jidtsdnji進一步, ,若設(shè)置多個銀行呢？第42頁/共91頁4、遍歷性問題一、歐拉圖G=(V,E)為一連通無向圖經(jīng)過G中每條邊至少一次的回路稱為巡回；經(jīng)過G中每條邊正好一次的巡回稱為歐拉巡回；存在歐拉巡回的圖稱為歐拉圖。二、中國郵遞員問題（CPPchinese postman problem） 一名郵遞員負責(zé)投遞某個街區(qū)的郵件。如何為他（她）設(shè)計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？這一問題是我國管梅谷教授19

30、62年首先提出，國際上稱之為中國郵遞員問題。 43第43頁/共91頁 解法： 若本身就是歐拉圖，則直接可以找到一條歐拉巡回就是本問題的解。 若不是歐拉圖，必定有偶數(shù)個奇度數(shù)結(jié)點，在這些奇度數(shù)點之間添加一些邊，使之變成歐拉圖，再找出一個歐拉巡回。 具體解法：Fleury算法+Edmonds最小對集算法44第44頁/共91頁三、哈密爾頓圖 G=(V,E)為一連通無向圖 經(jīng)過G中每點一次且正好一次的路徑稱為哈密爾頓路徑； 經(jīng)過G中每點一次且正好一次的回路稱為哈密爾頓回路； 存在哈密爾頓回路的圖稱為哈密爾頓圖。四、旅行商問題（TSPTraveling Salesman Problem） 一名推銷員準備

31、前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計一條最短的旅行路線？ 即：從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地（最小哈密爾頓回路） 對于n個節(jié)點的旅行商問題，n個節(jié)點的任意一個全排列都是問題的一個可能解（假設(shè)任意兩個點之間都有邊）。G個節(jié)點的全排列有(n-1)!個，因此間題歸結(jié)為在(n-1)!個回路中選取最小回路。 TSP問題的解法屬于NPNP完全問題，一般只研究其近似解法45第45頁/共91頁最鄰近算法(1) 選取任意一個點作為起始點,找出與該點相關(guān)聯(lián)的權(quán)重最小的邊,形成一條初始路徑.(2) 找出與最新加入到路徑中的點相關(guān)聯(lián)的權(quán)重最小的邊加入到路徑中,且要求不再路徑中產(chǎn)生回路.(3) 重復(fù)

32、(2)直到所有的結(jié)點都加入到路徑中.(4) 將起點和最后加入的結(jié)點之間的邊加入到路徑中,形成Hamilton回路.其他數(shù)值算法： 人工神經(jīng)元方法， 遺傳算法等等46第46頁/共91頁5 5、二分圖與匹配 定義定義1 1 設(shè)X, ,Y 都是非空有限集, ,且XY = , , E xy| |xX, ,yY, , 稱G =(X, Y, E)為二部圖二部圖. . 二部圖可認為是有限簡單無向圖. . 如果X中的每個點都與Y中的每個點鄰接, ,則稱G =(X, Y, E)為完備二部圖完備二部圖. . 若F：ER + +, ,則稱G =(X, Y, E, F )為二部賦權(quán)圖二部賦權(quán)圖. . 二部賦權(quán)圖的權(quán)矩

33、陣一般記作A=(aij )|X|Y | , ,其中aij = F (xi yj ). .第47頁/共91頁48 定義定義2 2 設(shè)G =(X, Y, E)為二部圖, ,且M E. .若M中任意兩條邊在G中均不鄰接, ,則稱M是二部圖G的一個匹配匹配. . 定義定義3 3 設(shè)M是二部圖G的一個匹配, ,如果G的每一個點都是M中邊的頂點, ,則稱M是二部圖G的完美匹配完美匹配； 如果G中沒有另外的匹配M0 , ,使| |M0| | |M|,|,則稱M是二部圖G的最大匹配最大匹配. . 在二部賦權(quán)圖G =(X, Y, E, F )中, ,權(quán)數(shù)最大的最大匹配M稱為二部賦權(quán)圖G的最佳匹最佳匹配配. .

34、顯然, ,每個完美匹配都是最大匹配, ,反之不一定成立. .第48頁/共91頁工作安排問題之一 49 給n個工作人員x1, x2, , xn安排n項工作y1, y2, , yn. . n個工作人員中每個人能勝任一項或幾項工作, 但并不是所有工作人員都能從事任何一項工作. 比如x1能做y1, y2工作, x2能做y2, y3, y4工作等. 這樣便提出一個問題, 對所有的工作人員能不能都分配一件他所能勝任的工作？ 我們構(gòu)造一個二部圖G = ( X, Y, E ), 這里X = x1, x2, , xn,Y = y1, y2, , yn, 并且當(dāng)且僅當(dāng)工作人員xi勝任工作yj時, xi與yj才相鄰

35、. 于是, 問題轉(zhuǎn)化為求二部圖的一個完美匹配. 因為 |X|=|Y|, 所以完美匹配即為最大匹配. 第49頁/共91頁50 求二部圖G = ( X, Y, E )的最大匹配算法( (匈牙利算法, ,交替鏈算法) )迭代步驟: 從G的任意匹配M開始. . 將X中M的所有非飽和點都給以標(biāo)號0 0和標(biāo)記* *, , 轉(zhuǎn)向. . M的非飽和點即非M的某條邊的頂點. . 若X中所有有標(biāo)號的點都已去掉了標(biāo)記* *, , 則M是G的最大匹配. . 否則任取X中一個既有標(biāo)號又有標(biāo)記* *的點xi , , 去掉xi的標(biāo)記* *, , 轉(zhuǎn)向. . 找出在G中所有與xi鄰接的點yj , , 若所有這樣的yj都已有標(biāo)

36、號, , 則轉(zhuǎn)向, , 否則轉(zhuǎn)向. .第50頁/共91頁51 對與xi鄰接且尚未給標(biāo)號的yj都給定標(biāo)號i. . 若所有的 yj 都是M的飽和點, ,則轉(zhuǎn)向, ,否則逆向返回. . 即由其中M的任一個非飽和點 yj 的標(biāo)號i 找到xi , ,再由 xi 的標(biāo)號k 找到 yk , , ,最后由 yt 的標(biāo)號s找到標(biāo)號為0 0的xs時結(jié)束, ,獲得M- -增廣路xs yt xi yj , , 記P = xs yt , , xi yj ,重新記M為M P, ,轉(zhuǎn)向. . 不必理會M- -增廣路的定義. . M P = MP MP, , 是對稱差. . 將yj在M中與之鄰接的點xk , ,給以標(biāo)號 j

37、和標(biāo)記* *, , 轉(zhuǎn)向. .第51頁/共91頁例 求下圖所示二部圖G的最大匹配52解 取初始匹配M0 = x2 y2 , x3 y3 , x5 y5 ( (上圖粗線所示). ). 給X中M0的兩個非飽和點x1, ,x4都給以標(biāo)號0 0和標(biāo)記* * ( (如下圖所示). ). 去掉x1的標(biāo)記*, 將與x1鄰接的兩個點y2, y3都給以標(biāo)號1.1. 因為y2, y3都是M0的兩個飽和點, ,所以將它們在M0中鄰接的兩個點x2, x3都給以相應(yīng)的標(biāo)號和標(biāo)記* (如下圖所示). 第52頁/共91頁53 去掉x2的標(biāo)記*, 將與x2鄰接且尚未給標(biāo)號的三個點y1, y4, y5都給以標(biāo)號2 (如下圖所示

38、). 因為y1是M0的非飽和點, 所以順著標(biāo)號逆向返回依次得到x2, y2, 直到x1為0為止. .于是得到M0的增廣路x1 y2x2 y1, 記P = x1 y2 , y2x2 , x2 y1. 取M1 = M0P = x1 y2 , x2 y1 , x3 y3 , x5 y5, 則M1是比M多一邊的匹配(如下圖所示). 第53頁/共91頁 再給X中M1的非飽和點x4給以標(biāo)號0和標(biāo)記*, 然后去掉x4的標(biāo)記*, 將與x4鄰接的兩個點y2, y3都給以標(biāo)號4. 因為y2, y3都是M1的兩個飽和點, , 所以將它們在M1中鄰接的兩個點x1, x3都給以相應(yīng)的標(biāo)號和標(biāo)記* (如下圖所示). 去掉

39、x1的標(biāo)記*, 因為與x1鄰接的兩個點y2, y3都有標(biāo)號4, 所以去掉x3的標(biāo)記*. 而與x3鄰接的兩個點y2, y3也都有標(biāo)號4, 此時X中所有有標(biāo)號的點都已去掉了標(biāo)記*(如下圖所示), 因此M1是G的最大匹配. G不存在飽和X的每個點的匹配, 當(dāng)然也不存在完美匹配.第54頁/共91頁工作安排問題之二 55 給n個工作人員x1, x2, , xn安排n項工作y1, y2, , yn. . 如果每個工作人員工作效率不同, 要求工作分配的同時考慮總效率最高. 我們構(gòu)造一個二部賦權(quán)圖G = ( X, Y, E , F ), 這里X = x1, x2, , xn,Y = y1, y2, , yn,

40、 F(xi yj )為工作人員xi勝任工作yj時的工作效率. 則問題轉(zhuǎn)化為：求二部賦權(quán)圖G的最佳匹配. 在求G 的最佳匹配時, 總可以假設(shè)G為完備二部賦權(quán)圖. .若xi與yj不相鄰, 可令F(xi yj )=0. 同樣地, 還可虛設(shè)點x或y, ,使|X|=|Y|. .如此就將G 轉(zhuǎn)化為完備二部賦權(quán)圖, ,而且不會影響結(jié)果. 第55頁/共91頁 定義定義 設(shè)G =( (X, Y, E, F) )為完備的二部賦權(quán)圖, , 若L：X Y R + + 滿足： xX, yY, L(x) + L(y)F(xy), ,則稱L為G的一個可行點標(biāo)記可行點標(biāo)記, ,記相應(yīng)的生成子圖為GL =( (X, Y, EL

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

42、 調(diào)整標(biāo)記, 計算aL=minL(x) + L (y) - - F (xy)|xS, yYT. 由此得新的可行點標(biāo)記.),(,)(,)()(ccLLTSvvLTvavLSvavLvH 令L = H, GL = GH , 重新給出GL的一個匹配M, 轉(zhuǎn)向. 取yNL (S) T , 若y是M的飽和點, 轉(zhuǎn)向. 否則, 轉(zhuǎn)向. 設(shè)x yM, 則令S = S x , T = T y , 轉(zhuǎn)向. 在GL中的u - - y路是M- - 增廣路, 設(shè)為P, 并令 M = M P, 轉(zhuǎn)向. 第57頁/共91頁6 6、網(wǎng)絡(luò)流問題 58 定義定義1 1 設(shè)G =(V, E )為有向圖, ,在V中指定一點稱為發(fā)點

43、發(fā)點( (記為vs ),),和另一點稱為收點收點( (記為vt ), ), 其余點叫做中間點. . 對每一條邊vivjE, ,對應(yīng)一個非負實數(shù)Cij , ,稱為它的容量容量. . 這樣的G稱為容量網(wǎng)絡(luò)容量網(wǎng)絡(luò), ,簡稱網(wǎng)絡(luò)網(wǎng)絡(luò), ,記作G = (V, E, C ). . 定義定義2 2 網(wǎng)絡(luò)G = (V, E, C )中任一條邊vivj有流量 fij , ,稱集合 f = fij 為網(wǎng)絡(luò)G上的一個流流. . 滿足下述條件的流 f 稱為可行流可行流： ( (限制條件) )對每一邊vivj , ,有0 fij Cij ; ( (平衡條件) )對于中間點vk有fik =fkj , , 即中間點vk的

44、輸入量 = 輸出量. . 第58頁/共91頁 如果 f 是可行流, ,則對收、發(fā)點vt、vs有fsi =fjt =Wf , ,即從vs點發(fā)出的物質(zhì)總量 = vt點輸入的量. .Wf 稱為網(wǎng)絡(luò)流 f 的總流量. . 上述概念可以這樣來理解, ,如G是一個運輸網(wǎng)絡(luò), ,則發(fā)點vs表示發(fā)送站, ,收點vt表示接收站, ,中間點vk表示中間轉(zhuǎn)運站, ,可行流 fij 表示某條運輸線上通過的運輸量, ,容量Cij表示某條運輸線能承擔(dān)的最大運輸量, ,Wf 表示運輸總量. . 可行流總是存在的. .比如所有邊的流量 fij = 0就是一個可行流( (稱為零流).).第59頁/共91頁 所謂最大流問題就是在

45、容量網(wǎng)絡(luò)中, ,尋找流量最大的可行流. . 實際問題中, ,一個網(wǎng)絡(luò)會出現(xiàn)下面兩種情況： 發(fā)點和收點都不止一個. . 解決的方法是再虛設(shè)一個發(fā)點vs和一個收點vt , ,發(fā)點vs到所有原發(fā)點邊的容量都設(shè)為無窮大, , 所有原收點到收點vt 邊的容量都設(shè)為無窮大. . 網(wǎng)絡(luò)中除了邊有容量外, ,點也有容量. . 解決的方法是將所有有容量的點分成兩個點, ,如點v有容量Cv , ,將點v分成兩個點v和v, ,令C(vv ) = Cv . . 第60頁/共91頁最小費用流問題 61 這里我們要進一步探討不僅要使網(wǎng)上的流達到最大, ,或者達到要求的預(yù)定值, ,而且還要使運輸流的費用是最小的, ,這就是

46、最小費用流問題. . 最小費用流問題的一般提法： 已知網(wǎng)絡(luò)G = (V, E, C ), ,每條邊vivjE 除了已給容量Cij外, ,還給出了單位流量的費用bij(0).). 所謂最小費用流問題就是求一個總流量已知的可行流 f = f ij 使得總費用ijEvvijfbfbji)(最小. .第61頁/共91頁62 特別地, ,當(dāng)要求 f 為最大流時, , 即為最小費用最大流問題. . 設(shè)網(wǎng)絡(luò)G = (V, E, C), 取初始可行流 f 為零流, 求解最小費用流問題的迭代步驟： 構(gòu)造有向賦權(quán)圖Gf =( (V, Ef , F),),對于任意的vivjE, ,Ef , ,F 的定義如下： 當(dāng)

47、f ij = 0時, ,vivjEf , ,F(vivj )= bij ; 當(dāng) f ij = Cij時, ,vjviEf , ,F(vjvi )= - - bij ; 當(dāng)0 f ijCij時, ,vivjEf , ,F(vivj )= bij , ,vjviEf , , F(vjvi ) = - - bij . . 然后轉(zhuǎn)向. .第62頁/共91頁63 求出含有負權(quán)的有向賦權(quán)圖Gf =( (V, Ef , F) )中發(fā)點vs到收點vt的最短路 , ,若最短路 存在轉(zhuǎn)向; 否則f是所求的最小費用最大流, ,停止. . 增流. .,jiijjiijijijvvfvvfCvivj與 相同, ,viv

48、j與 相反. .令 = min ij| |vivj , 重新定義流 f = f ij 為.,jiijjiijijvvfvvff其它情況不變. . 如果Wf 大于或等于預(yù)定的流量值, ,則適當(dāng)減少 值, ,使Wf 等于預(yù)定的流量值, ,那么 f 是所求的最小費用流, , 停止; 否則轉(zhuǎn)向. .第63頁/共91頁64 下面介紹求解有向賦權(quán)圖G = (V, E, F )中含有負權(quán)的最短路的Ford算法. 設(shè)邊的權(quán)vivj為wij , v1到vi的路長記為 (i ). Ford算法的迭代步驟： 賦初值 (1)=0, , (i )=,i = 2, 3, , n . . 更新 (i ), ,i = 2,

49、3, , n . . (i )= min (i ), ,min ( j ) + + wji | | ji . . 若所有的 (i )都無變化, ,停止;否則轉(zhuǎn)向. . 在算法的每一步, , (i )都是從v1到vi的最短路長度的上界. . 若不存在負長回路, ,則從v1到vi的最短路長度是 (i )的下界, ,經(jīng)過n - - 1次迭代后 (i )將保持不變. . 若在第n次迭代后 (i )仍在變化時, , 說明存在負長回路. . 第64頁/共91頁7 7、關(guān)鍵路徑問題（拓撲排序）65 一項工程任務(wù), ,大到建造一座大壩, ,一座體育中心, ,小至組裝一臺機床, ,一架電視機, , 都要包括許多

50、工序. .這些工序相互約束, ,只有在某些工序完成之后, , 一個工序才能開始. . 即它們之間存在完成的先后次序關(guān)系, ,一般認為這些關(guān)系是預(yù)知的, , 而且也能夠預(yù)計完成每個工序所需要的時間. . 這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項目, , 影響工程進度的要害工序是哪幾個？ 第65頁/共91頁PT(Potentialtask graph)圖 66 在PT(Potentialtask graph)圖中, ,用結(jié)點表示工序, ,如果工序 i 完成之后工序 j 才能啟動, ,則圖中有一條有向邊( (i , j ),),其長度wi 表示工序 i 所需的時間. . 這種

51、圖必定不存在有向回路, ,否則某些工序?qū)⒃谧陨硗瓿芍蟛拍荛_始, ,這顯然不符合實際情況. . 在PT圖中增加兩個虛擬結(jié)點v0和vn , ,使所有僅為始點的結(jié)點都直接與v0聯(lián)結(jié), ,v0為新增邊的始點, ,這些新增邊的權(quán)都設(shè)為0; 使所有僅為終點的結(jié)點都直接與vn聯(lián)結(jié), ,vn為新增邊的終點. . 這樣得到的圖G仍然不存在有向回路. .第66頁/共91頁 例 一項工程由1313道工序組成, , 所需時間( (單位：天) )及先行工序如下表所示(P172).(P172).工序序號 A B C D E F G H IA B C D E F G H I所需時間 2 6 3 2 4 3 8 4 22

52、6 3 2 4 3 8 4 2先行工序 A A B C,D D D D G,H A A B C,D D D D G,H工序序號 J K L MJ K L M所需時間 3 8 5 63 8 5 6先行工序 G H,E J K G H,E J K 試問這項工程至少需要多少天才能完成? ? 那些工程不能延誤? ? 那些工程可以延誤? ? 最多可延誤多少天? ?第67頁/共91頁 先作出該工程的先作出該工程的PT圖圖. .由于除了工序由于除了工序A A外，均有先行工序外，均有先行工序, ,因因此不必虛設(shè)虛擬結(jié)點此不必虛設(shè)虛擬結(jié)點v0. .A AB B2 22 2C C6 6D D3 3E E2 2F

53、F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8 85 56 6 在在PT圖中圖中,容易看出各工序先后完成的順序及時間容易看出各工序先后完成的順序及時間.虛擬結(jié)點第68頁/共91頁69A AB B2 22 2C C6 6D D3 3E E2 2F F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8 85 56 6 這項工程至少需要多少天才能完成? ?就是要求就是要求A A到到N N的最長路的最長路, ,此路徑稱為此路徑稱為關(guān)鍵路徑關(guān)鍵路徑. . 那些工程不能

54、延誤? ? 那些工程可以延誤? ? 最多可延誤多少天? ? 關(guān)鍵路徑上的那些工程不能延誤. .第69頁/共91頁關(guān)鍵路徑( (最長路徑) )算法 70 定理定理 若有向圖G中不存在有向回路, ,則可以將G 的結(jié)點重新編號為u1, u2, , un, ,使得對任意的邊ui ujE( (G),),都有i j . . 各工序最早啟動時間算法步驟： 根據(jù)定理對結(jié)點重新編號為u1, u2, , un . . 賦初值 ( (u1) )= 0. . 依次更新 ( (uj ),),j = 2, 3, , n . . ( (uj ) )= max ( (ui )+)+ ( (ui , ,uj )|)|uiujE

55、( (G).). 結(jié)束. .其中 ( (uj ) )表示工序 uj 最早啟動時間, ,而 ( (un) )即 ( (vn) )是整個工程完工所需的最短時間. .第70頁/共91頁71A AB B2 22 2C C6 6D D3 3E E2 2F F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8 85 56 6此例不必重此例不必重新編號，只新編號，只要按字母順要按字母順序即可序即可. (A)=0,(A)=0, (B)=(B)= (C)=2,(C)=2, (D)=8,(D)=8, (E)=(E)=max2+3,8+2=10,2+

56、3,8+2=10, (F)=(F)= (G)=(G)= (H)=(H)= (D)+2=10,(D)+2=10, (I)=(I)=max (G)+8,(G)+8, (H)+4=18,(H)+4=18, (J)=(J)= (G)+8=18,(G)+8=18, (K)=(K)=max (E)+4,(E)+4, (H)+4=14,(H)+4=14, (L)=(L)= (J)+3=21,(J)+3=21, (M)=(M)= (K)+8=22,(K)+8=22, (N)=(N)=max (F)+3,(F)+3, (I)+2,(I)+2, (L)+5,(L)+5, (M)+6=28.(M)+6=28.關(guān)鍵路

57、徑? ?第71頁/共91頁通過以上計算表明：這項工程至少需要2828天才能完成. .關(guān)鍵路徑( (最長路徑):):ABDEKMNABDEKMNABDHKMNABDHKMN 工序A,B,D,E,H,K,MA,B,D,E,H,K,M不能延誤, ,否則將影響工程的完成. . 但是對于不在關(guān)鍵路徑上的工序, , 是否允許延誤？如果允許, , 最多能夠延誤多長時間呢？ 各工序允許延誤時間t( (uj ) )等于各工序最晚啟動時間 ( (uj ) )減去各工序最早啟動時間 ( (uj ).).即 t( (uj )=)= ( (uj )-)- ( (uj ).).第72頁/共91頁73最晚啟動時間算法步驟(

58、 (已知結(jié)點重新編號) )： 賦初值 ( (un )=)= ( (un).). 更新 ( (uj ),),j = n - - 1, n - - 2, , 1. . ( (uj ) )= min ( (ui )-)- ( (ui , ,uj )|)|uiujE( (G).). 結(jié)束. . 順便提一句, ,根據(jù)工序uj允許延誤時間t( (uj ) )是否為0,0,可判斷該工序是否在關(guān)鍵路徑上. .第73頁/共91頁74A AB B2 22 2C C6 6D D3 3E E2 2F F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8

59、 85 56 6 (N)=28,(N)=28, (M)=28-6=22,(M)=28-6=22, (L)=28-5=23,(L)=28-5=23, (K)=(K)= (M)-8=14,(M)-8=14, (J)=(J)= (L)-3=20,(L)-3=20, (I)=28-2=26,(I)=28-2=26, (H)=(H)=min (K)-4,(K)-4, (I)-4=10,(I)-4=10, (G)=(G)=min (J)-8,(J)-8, (I)-8=12,(I)-8=12, (F)=(F)=2828-3=25,-3=25, (E)=(E)= (K)-4=10,(K)-4=10, (D)=

60、(D)=min (E)-2,(E)-2, (F)-2,(F)-2, (G)-2,(G)-2, (H)-2=8,(H)-2=8, (C)=(C)= (E)-3=7,(E)-3=7, (B)=(B)= (D)-6=2,(D)-6=2, (A)=0.(A)=0.第74頁/共91頁75各工序允許延誤時間如下：t t(A)=(A)=t t(B)=(B)=t t(D)=(D)=t t(E)=(E)=t t(H)=(H)=t t(K)=(K)=t t(M)=0,(M)=0,t t(C)=5,(C)=5,t t(F)=15,(F)=15,t t(G)=2,(G)=2,t t(I)=8,(I)=8,t t(J)