運籌學(xué) 圖與網(wǎng)絡(luò)優(yōu)化

1、運籌學(xué) 圖與網(wǎng)絡(luò)優(yōu)化第1頁，共131頁，2022年，5月20日，18點42分，星期三圖論概述圖論(Graph Theory)是運籌學(xué)中的一個重要分支，主要研究具有某種二元關(guān)系的離散系統(tǒng)的組合結(jié)構(gòu)和性質(zhì)。如，通信系統(tǒng)、交通運輸系統(tǒng)、信息網(wǎng)絡(luò)系統(tǒng)、生產(chǎn)工藝流程以及軍事后勤保障系統(tǒng)等的問題常用圖論模型來描述。第2頁，共131頁，2022年，5月20日，18點42分，星期三網(wǎng)絡(luò)規(guī)劃概述網(wǎng)絡(luò)規(guī)劃(Network Programming )是圖論與線性規(guī)劃的交叉學(xué)科，具有廣泛的應(yīng)用背景，比如，最短路問題、最小樹問題、最大流問題、最優(yōu)匹配問題等。第3頁，共131頁，2022年，5月20日，18點42分，星期

2、三七橋問題七橋問題圖形第4頁，共131頁，2022年，5月20日，18點42分，星期三原 理 及 方 法 七橋問題是圖論中的著名問題。1736年，Euler巧妙地將此問題化為圖的不重復(fù)一筆畫問題，并證明了該問題不存在肯定回答。原因在于該圖形有頂點連接奇數(shù)條邊。第5頁，共131頁，2022年，5月20日，18點42分，星期三10.1 圖的基本概念一個圖(Graph) 定義為三元有序組V(G)是圖的頂點集合E(G)是圖的邊集合記 是關(guān)聯(lián)函數(shù)第6頁，共131頁，2022年，5月20日，18點42分，星期三圖的端點設(shè)G是一個圖(Graph)G=(V(G),E(G)，則稱e連接u和v，稱u和v是e的端點

3、。若稱端點u，v與邊e是關(guān)聯(lián)的，稱兩個頂點u，v是鄰接的。第7頁，共131頁，2022年，5月20日，18點42分，星期三設(shè)G是一個圖， 圖10G的幾何實現(xiàn)第8頁，共131頁，2022年，5月20日，18點42分，星期三圖的幾何實現(xiàn) 一個圖可用一個幾何圖形表示,稱為圖的幾何實現(xiàn)，其中每個頂點用點表示，每條邊用連接端點的線表示。圖的幾何實現(xiàn)有助與我們直觀的了解圖的許多性質(zhì)。第9頁，共131頁，2022年，5月20日，18點42分，星期三說明一個圖的幾何實現(xiàn)并不是唯一的；表示頂點的點和表示邊的線的相對位置并不重要，重要的是圖形描繪出邊與頂點之間保持的相互關(guān)系。我們常常把一個圖的圖形當(dāng)作這個抽象圖自

4、身. 并稱圖形的點為頂點，圖形的線為邊。圖論中大多數(shù)概念是根據(jù)圖的表示形式提出的，例如：頂點、邊、多重邊、環(huán)、路、圈、樹等。第10頁，共131頁，2022年，5月20日，18點42分，星期三幾何實現(xiàn)圖例在一個圖的幾何實現(xiàn)中，兩條邊的交點可能不是圖的頂點。例如下圖 中，它共有4個頂點，6條邊；而e 3 與e 4 的交點不是這個圖的頂點。第11頁，共131頁，2022年，5月20日，18點42分，星期三平面圖一個圖稱為平面圖，如它有一個平面圖形，使得邊與邊僅在頂點相交。下圖就是一個平面圖。第12頁，共131頁，2022年，5月20日，18點42分，星期三基本概念端點重合為一點的邊稱為環(huán)。連接同一對

5、頂點的多條邊稱為多重邊。在右圖中，e5 是一個環(huán)，e1 與e2 是多重邊， v1和e1,e2,e3是關(guān)聯(lián)的，v1與v2,v3是鄰接的。第13頁，共131頁，2022年，5月20日，18點42分，星期三鄰接矩陣設(shè)G是一個圖， G=(V(G),E(G)，定義圖G的鄰接矩陣A(G) =(aij)為mm矩陣, aij是頂點vi與邊vj相鄰接的邊數(shù)。其中第14頁，共131頁，2022年，5月20日，18點42分，星期三關(guān)聯(lián)矩陣設(shè)G是一個圖， G=(V(G),E(G)定義圖G的關(guān)聯(lián)矩陣M=(mij)為mn矩陣；其中mij是頂點vi與邊ej相關(guān)聯(lián)的次數(shù)，取值可能為0、1、2。第15頁，共131頁，2022年

6、，5月20日，18點42分，星期三注圖的鄰接矩陣比它的關(guān)聯(lián)矩陣小的多，因而圖常常以其鄰接矩陣的形式存貯與計算機中。關(guān)聯(lián)矩陣和鄰接矩陣統(tǒng)稱圖的矩陣表示。第16頁，共131頁，2022年，5月20日，18點42分，星期三頂點的度設(shè)G是一個圖， G=(V(G),E(G)，定義圖G的頂點v的度為與頂點v相關(guān)聯(lián)的邊數(shù)，記作d(v) 例稱度為奇數(shù)的頂點為奇點；稱度為偶數(shù)的頂點為偶點。第17頁，共131頁，2022年，5月20日，18點42分，星期三例22222224+3+3+4=14=27第18頁，共131頁，2022年，5月20日，18點42分，星期三關(guān)聯(lián)矩陣性質(zhì)圖G的關(guān)聯(lián)矩陣M=(mij)為mn矩陣；

7、則每行元素之和等于相應(yīng)頂點的度；每列元素之和等于2。因此，圖G的關(guān)聯(lián)矩陣M所有元素之和既等于所有頂點的度之和，又等于邊數(shù)的2倍。定理設(shè)G是一個圖，則第19頁，共131頁，2022年，5月20日，18點42分，星期三推論圖中奇點的數(shù)目為偶數(shù)。證明記第20頁，共131頁，2022年，5月20日，18點42分，星期三簡單圖一個圖稱為簡單圖，如果它既沒有環(huán)也沒有多重邊。下圖是簡單圖。本書只限于討論有限簡單圖，即頂點集與邊集都是有限集的圖。u1u2u3u4f1f2f6f3f5f4只有一個頂點的圖稱為平凡圖；邊集是空集的圖稱為空圖。第21頁，共131頁，2022年，5月20日，18點42分，星期三同構(gòu)稱G

8、和H是同構(gòu)的，記為 ，使得給定兩個圖如果存在兩個一一對應(yīng)第22頁，共131頁，2022年，5月20日，18點42分，星期三同構(gòu)圖例圖G與圖H是同構(gòu)的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4第23頁，共131頁，2022年，5月20日，18點42分，星期三完全圖Kn完全圖是每一對不同頂點都恰有一邊的簡單圖；具有n個頂點的完全圖記為Kn.K5第24頁，共131頁，2022年，5月20日，18點42分，星期三二分圖二分圖是一個簡單圖，其頂點集合可分劃成兩個子集X與Y，使得每條邊的一個端點在X，另一個端點在Y; (X,Y)也稱為圖的二分劃。x1x2x3y1

9、y2y3第25頁，共131頁，2022年，5月20日，18點42分，星期三完全二分圖完全二分圖是具有二分劃(X,Y)的二分圖，并且X的每個頂點與Y的每個頂點都相連；記為Km,n，其中K3,3第26頁，共131頁，2022年，5月20日，18點42分，星期三特殊圖例K5K 3,3都是極小的非平面圖第27頁，共131頁，2022年，5月20日，18點42分，星期三子圖稱圖H是圖G的子圖，圖G及其基本圖稱H是G的支撐子圖，如果稱H是G的真子圖，若如果表示關(guān)聯(lián)函數(shù)記為在H的限制。第28頁，共131頁，2022年，5月20日，18點42分，星期三頂點導(dǎo)出子圖設(shè)W是圖G的一個非空頂點子集,以W為頂點集，以

10、二端點均在W中的邊的全體為邊集的子圖稱為由W導(dǎo)出的G的子圖，簡稱導(dǎo)出子圖，記為GW。導(dǎo)出子圖GV- w記為G-W，即 它是從G中刪除W中頂點以及與這些頂點相關(guān)聯(lián)的邊所得到的子圖。如果W僅含一個頂點v，則把 簡記為。第29頁，共131頁，2022年，5月20日，18點42分，星期三邊導(dǎo)出子圖設(shè)F是圖G的非空邊子集，以F為邊集，以F中邊的端點全體為頂點集所構(gòu)成的子圖稱為由F導(dǎo)出的G的子圖，簡稱G的邊導(dǎo)出子圖。記為GF。記G-F表示以E(G)F為邊集的G的支撐子圖，它是從G中刪除F中的邊所得到的子圖。如F= e ，則記。第30頁，共131頁，2022年，5月20日，18點42分，星期三子圖圖例v1v

11、2v3v4v5e1e3e2Gv1v2v3v4v5G的支撐子圖G- e1 , e 2 , e 3第31頁，共131頁，2022年，5月20日，18點42分，星期三子圖圖例2v2v3v4e2G-v 1,v 5 v1v2v5Gv 1,v 2 ,v 5 v1v2v3v4e1e3e2G e1 , e 2 , e 3v1v2v3v4v5e1e3e2G第32頁，共131頁，2022年，5月20日，18點42分，星期三途徑頂點vk叫W的終點，頂點v0 稱為W的起點，頂點vi 叫W的內(nèi)部頂點，整數(shù)k稱為W的長度。在簡單圖中，徑可由頂點序列表示。圖G的一個有限的點邊交錯序列稱為從v0到vk的途徑。其中vi與vi+

12、1是邊ei的頂點;第33頁，共131頁，2022年，5月20日，18點42分，星期三路、鏈如果徑W的邊不相同，則稱W為一條鏈，如果W頂點互不相同，則稱W是一條路。鏈長是W中邊的個數(shù)k。記路長uvwxyabdefgh路：xcwhyeuav鏈：wcxdyhwbvgyc第34頁，共131頁，2022年，5月20日，18點42分，星期三圈(回路)如果途徑W的起點和終點相同且有正長度，則稱它是一個閉途徑；如果一條閉鏈的頂點互不相同，則稱它是一個圈（或回路）。稱一個圈是偶圈（奇圈），如果它的圈長是偶數(shù)（奇數(shù)）。圈：uavbwhyeuuvwxyabdefghc第35頁，共131頁，2022年，5月20日，1

13、8點42分，星期三定理一個圖是二分圖當(dāng)且僅當(dāng)圖中不存在奇圈。第36頁，共131頁，2022年，5月20日，18點42分，星期三Euler圈Euler圈是指過所有邊一次且恰好一次的閉途徑。Euler鏈是指過所有邊一次且恰好一次的鏈。Euler鏈:ydxcwheuavfygvbwuvwxyabdefghc第37頁，共131頁，2022年，5月20日，18點42分，星期三圖例下例給出了一個圖的徑，鏈和路。徑：uavfyfvgyhwbv鏈：wcxdyhwbvgy路：xcwhyeuav圈：uavbwhyeuEuler鏈:ydxcwheuavfygvbwuvwxyabdefghc第38頁，共131頁，20

14、22年，5月20日，18點42分，星期三Euler型定理定理2設(shè)G是連通圈，則G是Euler型的充要條件是G沒有奇次數(shù)的頂點。推論1設(shè)G是一個連通圖，則G有Euler鏈當(dāng)且僅當(dāng)G最多有兩個奇數(shù)次數(shù)的頂點。第39頁，共131頁，2022年，5月20日，18點42分，星期三連通性圖G稱為連通的，如果在G的任意兩個頂點u和v中存在一條(u,v)路。不連通圖至少有兩個連通分支。兩點頂點u和v等價當(dāng)且僅當(dāng)u和v中存在一條(u,v)路。表示G的連通分支數(shù)。第40頁，共131頁，2022年，5月20日，18點42分，星期三10.2 樹樹（tree）是一個不包含圈的簡單連通圖。具有k個連通分支的不包含圈的圖稱

15、為k-樹，或森林。第41頁，共131頁，2022年，5月20日，18點42分，星期三下圖列出了具有六個頂點的不同構(gòu)的樹。從中可以看出，圖中的每棵樹都只有5條邊，并且至少有2個頂點的次數(shù)是1。第42頁，共131頁，2022年，5月20日，18點42分，星期三性質(zhì)1設(shè)G是一棵樹，則： G中任意兩點均有唯一的路連接。2 G的邊數(shù)等于頂點數(shù)減1，即3 若G不是平凡圖，則G至少有兩個次數(shù)為1的頂點。第43頁，共131頁，2022年，5月20日，18點42分，星期三定理1設(shè)G是一個簡單圖， ，則下列六個命題是等價的。G是一棵樹。無圈且m=n-1。G連通且m=n-1。G連通并且每條邊都是割邊。G中任意兩點都

16、有唯一的路相連。G無圈，但在任意一對不相鄰的頂點之間加連一條邊，則構(gòu)成唯一的一個圈。第44頁，共131頁，2022年，5月20日，18點42分，星期三支撐樹圖G的支撐樹是G的支撐子圖，并且是一棵樹。每個連通圖都有支撐樹支撐樹也稱為連通圖的極小連通支撐子圖。很顯然，一個連通圖只要本身不是一棵樹，它的支撐樹就不止一個。第45頁，共131頁，2022年，5月20日，18點42分，星期三定理定理4設(shè)T1 和T2 是G的兩個支撐樹，令 則T1 經(jīng)過k次迭代后可得到T2。定理2設(shè)G是一個連通圖，T是G的一棵支撐樹，e是G的一條不屬于T的邊，則T+e含有G的唯一圈。定理3設(shè)T是連通圖G的一棵支撐樹，e是T的

17、任意一條邊，則：T（1） 不包含G的割集（2）包含G的唯一的割集。第46頁，共131頁，2022年，5月20日，18點42分，星期三最小樹定理5設(shè)T是G的一個支撐樹，則T是G的最小樹的充分必要條件為對任意邊設(shè)G是一個賦權(quán)圖，T為G的一個支撐樹。定義T的權(quán)為：G中權(quán)最小的支撐樹稱為G的最小樹。第47頁，共131頁，2022年，5月20日，18點42分，星期三定理6設(shè)T是G的支撐樹，則T是G的最小樹的充分必要條件為對任意邊 ，其中 為G的唯一割集。第48頁，共131頁，2022年，5月20日，18點42分，星期三最小樹算法-1-貪心算法Kruskal在1965年提出一種求最小樹的所謂貪心算法。算法

18、步驟如下Step0 把邊按權(quán)的大小從小到大排列得：置Step1 若 ，則停，此時GS即為所求的最小樹； 否則，轉(zhuǎn)向Step2。Step2 如果 GS+e j不構(gòu)成回路，則令轉(zhuǎn)向Step1；否則，令j=j+1轉(zhuǎn)向Step2。第49頁，共131頁，2022年，5月20日，18點42分，星期三算例圖7-18展示了利用Kruskal算法求最小樹的迭代過程。v1v2v4v5v312244342v1v2v4v5v312244342圖7-18第50頁，共131頁，2022年，5月20日，18點42分，星期三v1v2v4v5v312244342v1v2v4v5v312244342圖7-18-1第51頁，共13

19、1頁，2022年，5月20日，18點42分，星期三評注Kruskal算法的總計算量為 ，有效性不太好。求最小樹的一個好的算法是Dijkstra于1959年提出的，算法的實質(zhì)是在圖的 個獨立割集中，取每個割集的一條極小邊來構(gòu)成最小樹。第52頁，共131頁，2022年，5月20日，18點42分，星期三最小樹算法-2 -Dijkstra算法Step0 置Step1 取置Step2 若 ，則停止；否則，置 ，返回Step1第53頁，共131頁，2022年，5月20日，18點42分，星期三算例2圖7-19展示了利用Dijkstra算法求最小樹的迭代過程。v1v2v4v5v312244342v1v2v4v

20、5v312244342圖7-19第54頁，共131頁，2022年，5月20日，18點42分，星期三利用Dijkstra算法求最小樹的迭代過程。v1v2v4v5v312244342v1v2v4v5v312244342圖7-19-1第55頁，共131頁，2022年，5月20日，18點42分，星期三破圈法是Dijkstra算法的對偶算法。最適合于圖上作業(yè)。尤其是當(dāng)圖的頂點數(shù)和邊數(shù)比較大時，可以在各個局部進行。Step1 若G不含圈，則停止；否則在G中找一個圈C，取圈C的一條邊e ，滿足最小樹算法-3 -破圈法Step2：置 G = G - e ，返回Step1。利用破圈法求圖7-19的最小樹的過程如

21、圖7-20所示。第56頁，共131頁，2022年，5月20日，18點42分，星期三算例3圖7-20展示了利用破圈法求最小樹的迭代過程。v1v2v4v5v312244342v1v2v4v5v312244342圖7-20第57頁，共131頁，2022年，5月20日，18點42分，星期三v1v2v4v5v312244342v1v2v4v5v312244342圖7-20-1第58頁，共131頁，2022年，5月20日，18點42分，星期三評注上述算法都可以在圖上進行。為了便于計算機計算，下面介紹Dijkstra的表上算法。給定一個賦權(quán)圖G，可以相應(yīng)地定義一個鄰接矩陣A=(wij)，其中wij是連接頂點

22、vi和vj的權(quán);若vi vj不是G的邊，則令 wij 等于無窮大。第59頁，共131頁，2022年，5月20日，18點42分，星期三Step0：畫掉第一列的所有元素（例如打上 ）， 并在第一行的每個元素下面畫一橫線。Step1：在畫橫線的元素中找一個最小的w ij ，用圓圈起來，把第j列其他元素畫掉，并把第j行沒有畫掉的元素畫上橫線。Step2：如果還有沒有圈起來和沒有畫掉的元素，則返回Step1；否則，結(jié)束。這時圈起來的元素代表最小樹的邊，所有圈起來的元素之和就是最小樹的權(quán)。最小樹算法-4 -表上作業(yè)法第60頁，共131頁，2022年，5月20日，18點42分，星期三算例用表上作業(yè)法求圖7-

23、19的最小樹的過程為：最小對的權(quán)=1+2+3+2=8。v1v2v4v5v312244342第61頁，共131頁，2022年，5月20日，18點42分，星期三第62頁，共131頁，2022年，5月20日，18點42分，星期三最小連接問題作為最小樹的應(yīng)用問題之一是所謂的連接問題：欲建造一個連接若干城鎮(zhèn)（礦區(qū)或工業(yè)區(qū)）的鐵路網(wǎng)，給定城鎮(zhèn)i和j之間直通線路的造價為cij，試設(shè)計一個總造價最小的鐵路運輸圖。把每個城鎮(zhèn)看作是具有權(quán)cij的賦權(quán)圖G的一個頂點。顯然連接問題可以表述成：在賦權(quán)圖G中，求出具有最小權(quán)的支撐樹。第63頁，共131頁，2022年，5月20日，18點42分，星期三10.3 最短路問題D

24、ijkstra算法求任意兩點的最短路算法-Floyd算法求帶負權(quán)網(wǎng)絡(luò)圖的最短路的算法用線性規(guī)劃求最短路第64頁，共131頁，2022年，5月20日，18點42分，星期三賦權(quán)圖給定賦權(quán)圖的一個子圖H，定義H的權(quán)為H的所有邊權(quán)的總和。對圖G的每條邊e，賦予一實數(shù)(e)，稱為邊e的權(quán)，可得一賦權(quán)圖。SDBTCEA712244731555第65頁，共131頁，2022年，5月20日，18點42分，星期三賦權(quán)圖中一條路的權(quán)稱為路長。在一個賦權(quán)圖G上，給定兩個頂點u和 v，所謂u和 v最短 路是指所有連接頂點u和 v 的路中路長最短的路；u和v最短路的路長也稱為u和 v的距離。SDBTCEA7122447

25、31555如何求從u到v的最短路的長？第66頁，共131頁，2022年，5月20日，18點42分，星期三Dijkstra算法的基本思想：(1)u0u1P設(shè)S是V的真子集，如果 是從u0 到的最短路，則 ，并且P的 段是最短的 路，所以第67頁，共131頁，2022年，5月20日，18點42分，星期三算法標(biāo)號令dij表示連接頂點vi與頂點vj邊上的權(quán)，即(1)公式（1）是Dijkstra算法的基礎(chǔ)。第68頁，共131頁，2022年，5月20日，18點42分，星期三定義結(jié)點vj 的標(biāo)號為始點的標(biāo)號為0,-, 表明這個點前面沒有點。結(jié)點vj 的標(biāo)號分為兩種：臨時性標(biāo)號和永久性標(biāo)號。如果找到一條更短的

26、路，臨時性標(biāo)號即被修改，如果找不到一條更短的路，臨時性標(biāo)號即被改為永久性標(biāo)號。第69頁，共131頁，2022年，5月20日，18點42分，星期三Step0 令始點的標(biāo)號為0, -. 令i=1 Step i (a) 對于由結(jié)點i可達的還沒有永久性標(biāo)號的結(jié)點j，計算其臨時性標(biāo)號li+dij, i（dij0）. 如果 j 已經(jīng)通過另一個結(jié)點k標(biāo)號為 lj, k 且 li+dijlj, 則用li+dij, i取代 lj, k 。(b) 如果所有的結(jié)點都是永久性標(biāo)號，停止。否則選擇最小的臨時性標(biāo)號 lr, s 。 令 i=r ， 返回Step i.第70頁，共131頁，2022年，5月20日，18點42

27、分，星期三計算實例求連接S、T的最短路SDBTCEA712244731555第71頁，共131頁，2022年，5月20日，18點42分，星期三SDBTCEA7122447315550第72頁，共131頁，2022年，5月20日，18點42分，星期三SDBTCEA71224473155505，s4，s2，s2，s第73頁，共131頁，2022年，5月20日，18點42分，星期三SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s第74頁，共131頁，2022年，5月20日，18點42分，星期三SDBTCEA71224473155505，s4，s2，s2，s9，A4，

28、A4，s4，A8，C第75頁，共131頁，2022年，5月20日，18點42分，星期三SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B 7，B第76頁，共131頁，2022年，5月20日，18點42分，星期三SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E第77頁，共131頁，2022年，5月20日，18點42分，星期三lST = 13;S-T最短路為SABEDTSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，

29、B8，E14，E8，E13，D第78頁，共131頁，2022年，5月20日，18點42分，星期三實例評述Dijkstra算法不僅找到了所求最短路，而且找到了從S點到其他所有頂點的最短路；這些最短路構(gòu)成了圖的一個連通無圈的支撐子圖，即圖的一個支撐樹。SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D第79頁，共131頁，2022年，5月20日，18點42分，星期三注:Dijkstra算法只適用于所有wij0的情形，當(dāng)賦權(quán)有向圖中存在負權(quán)時，算法失效。如v1v2v3 12-3用Dijkstra算法可以得出從v1到v

30、2的最短路的權(quán)是1，但實際上從v1到v2的最短路是（v1， v3 ，v2），權(quán)是-1。第80頁，共131頁，2022年，5月20日，18點42分，星期三下面介紹具有負權(quán)賦權(quán)有向圖D的最短路的算法。不妨假設(shè)從任一點vi到任一點vj都有一條?。ㄈ绻贒中，（ vi，vj ） A，則添加?。?vi，vj ）令wij=+ ）。顯然，從vs到任一點vj的最短路總是從vs出發(fā)到某個點vi，再沿（vi，vj）到vj的，由前面的結(jié)論可知，從vs到vi的這條路必定是從vs到vi的最短路，所以d（vs，vj）必滿足如下方程：第81頁，共131頁，2022年，5月20日，18點42分，星期三第82頁，共131頁，2

31、022年，5月20日，18點42分，星期三6-1-3-283-52-111-1217-3-5例：求v1到各點的最短路。第83頁，共131頁，2022年，5月20日，18點42分，星期三wijv1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v4023-7-7-7v5-101-3-3v610-17-1-1-1v7-1-305-5-5v8-5066第84頁，共131頁，2022年，5月20日，18點42分，星期三例一個連接11個城鎮(zhèn)的交通圖以及城市u與v之間的一條最短路。（粗線表示）uv第85頁，共131頁，2

32、022年，5月20日，18點42分，星期三uv第86頁，共131頁，2022年，5月20日，18點42分，星期三求任意兩點的最短路算法-Floyd算法這種算法用一個n階方陣來表示一個n-結(jié)點網(wǎng)絡(luò).矩陣中的 (i, j)-元 dij 表示從 i 到 j邊上的權(quán), 即第87頁，共131頁，2022年，5月20日，18點42分，星期三ijkFloyds algorithm 的基本思想：給定結(jié)點 i, j 和 k ，若有如下三角形，且 ，則從i經(jīng)過 k到j(luò) 比直接到j(luò)所經(jīng)過路線短。此時用ikj 代替ij最好.-三角形運算第88頁，共131頁，2022年，5月20日，18點42分，星期三第89頁，共13

33、1頁，2022年，5月20日，18點42分，星期三1245335461510 1 2 3 4 5 1 2 3 4 531035106155644 1 2 3 4 5 1 2 3 4 523451345124512351234第90頁，共131頁，2022年，5月20日，18點42分，星期三 1 2 3 4 5 1 2 3 4 531035106155644 1 2 3 4 5 1 2 3 4 523451345124512351234 1 2 3 4 5 1 2 3 4 5310313510136155644 1 2 3 4 5 1 2 3 4 523451145114512351234第91

34、頁，共131頁，2022年，5月20日，18點42分，星期三 1 2 3 4 5 1 2 3 4 5310313510136155644 1 2 3 4 5 1 2 3 4 523451145114512351234 1 2 3 4 531083135101361585644 1 2 3 4 5 1 2 3 4 5232511451145223512341 2 3 4 5第92頁，共131頁，2022年，5月20日，18點42分，星期三 1 2 3 4 531083135101361585644 1 2 3 4 5 1 2 3 4 523251145114522351234 1 2 3 4 5

35、310825313528101361585644 1 2 3 4 5 1 2 3 4 5232311431145223512341 2 3 4 51 2 3 4 5第93頁，共131頁，2022年，5月20日，18點42分，星期三 1 2 3 4 5310825313528101361585644 1 2 3 4 5 1 2 3 4 5232311431145223512341 2 3 4 5 1 2 3 4 53108123115910116108564129104 1 2 3 4 5 1 2 3 4 5232414441444223544441 2 3 4 5第94頁，共131頁，2022

36、年，5月20日，18點42分，星期三 1 2 3 4 53108123115910116108564129104 1 2 3 4 5 1 2 3 4 5232414441444223544441 2 3 4 512453354615101245第95頁，共131頁，2022年，5月20日，18點42分，星期三用線性規(guī)劃求最短路124531001550106030求從1到2的最短路20第96頁，共131頁，2022年，5月20日，18點42分，星期三10.4 網(wǎng)絡(luò)最大流問題第97頁，共131頁，2022年，5月20日，18點42分，星期三vsv1v3v4v2vt322223111網(wǎng)絡(luò)流圖設(shè)D=

37、(V,A,W) 是一個有向網(wǎng)絡(luò)。vs是網(wǎng)絡(luò)的源點，vt是網(wǎng)絡(luò)的匯點?；∩系臄?shù)字是允許通過的最大流量。第98頁，共131頁，2022年，5月20日，18點42分，星期三可行流設(shè)f是定義在弧集A上的一個函數(shù)，如果對所有弧 a 成立并且對所有中間頂點 v 成立其中，f +(v)是流出v 的流量，f -(v)是流入v的流量。則稱 f 是網(wǎng)絡(luò)D上的一個可行流。2,1vsv1v3v4v2vt3,12,12,22,13,21,01,01,1-容量限制-守恒條件第99頁，共131頁，2022年，5月20日，18點42分，星期三流值對于源點vs和匯點vt ，流出源點vs的流量等于流入?yún)R點vt的流量，稱之為流 f

38、 的值，記為val f 。即vsv1v3v4v2vt3,12,12,22,12,13,21,01,01,1val f = 3第100頁，共131頁，2022年，5月20日，18點42分，星期三最大流網(wǎng)絡(luò)最大流是指給定網(wǎng)絡(luò)上的流值最大的一個可行流。尋找給定網(wǎng)絡(luò)的最大流及其有效算法是網(wǎng)絡(luò)規(guī)劃的一個重要問題。Ford 與 Fulkerson 在1957年提出一個求解網(wǎng)絡(luò)最大流問題的算法，稱為Ford Fulkerson 算法。第101頁，共131頁，2022年，5月20日，18點42分，星期三割集設(shè)S是網(wǎng)絡(luò)的頂點子集，且割集的容量定義為最小割是指容量最小的割。定義D的一個割集，簡稱割為vsv1v3v

39、4v2vt322223111第102頁，共131頁，2022年，5月20日，18點42分，星期三定理1對于網(wǎng)絡(luò)的任意流 f 和割 成立證明 由定義可知第103頁，共131頁，2022年，5月20日，18點42分，星期三推論1 對于網(wǎng)絡(luò)的任意流 f 和割 ，成立vsv1v3v4v2vt322223111第104頁，共131頁，2022年，5月20日，18點42分，星期三注：推論2的逆命題也成立，即推論中的等式永遠成立。稱為最大流最小割定理，是網(wǎng)絡(luò)理論的一個重要定理。則f 是最大流，K是最小割。如果成立推論2 設(shè) f 是網(wǎng)絡(luò)的一個可行流， 是網(wǎng)絡(luò)的一個割，第105頁，共131頁，2022年，5月2

40、0日，18點42分，星期三鏈、正向弧、反向弧 設(shè)P是網(wǎng)絡(luò)D的一條鏈，則P中的弧可分為兩類：正向弧弧的方向與P的走向一致；記為P+。反向弧弧的方向與P的走向相反;記為P-。網(wǎng)絡(luò)D的連接源點vs和匯點vt的路。vsv1v3v4v2vt322223111第106頁，共131頁，2022年，5月20日，18點42分，星期三增廣鏈設(shè)P是網(wǎng)絡(luò)D的一條連接源點vs和匯點vt的鏈， f 是網(wǎng)絡(luò)D上的一個可行流.如果P的每一正向弧都是不飽和弧，而P的每一反向弧的流量都為正；則稱P是網(wǎng)絡(luò)D的關(guān)于可行流f 的一條可增廣鏈。簡稱增廣鏈?？稍鰪V鏈上流量可以增加。vsv1v3v4v2vt3，12,12,22,22,13,

41、21,01,11,0第107頁，共131頁，2022年，5月20日，18點42分，星期三定理2設(shè)f 是網(wǎng)絡(luò)D上的一個可行流，則 f 是一個最大流當(dāng)且僅當(dāng)網(wǎng)絡(luò)D不存在f 的增廣鏈。證明 （必要性） 設(shè)f 是一個最大流，假如D中存在f 的增廣鏈P,則可以得到一個流值更大的流f 1,使得構(gòu)造過程如下：其中第108頁，共131頁，2022年，5月20日，18點42分，星期三證明充分性設(shè)網(wǎng)絡(luò)D不存在f 的增廣鏈。定義S如下：從而 是D的割集，進而可得 中的弧都是飽和弧，而 中的弧都是0流弧， 否則將產(chǎn)生網(wǎng)絡(luò)D 的一條增廣鏈。因此，f 的流值等于割集 的割量，所以， f是一個最大流。第109頁，共131頁

42、，2022年，5月20日，18點42分，星期三定理3在任何網(wǎng)絡(luò)流圖中，最大流的值等于最小割的容量。（最大流最小割定理）第110頁，共131頁，2022年，5月20日，18點42分，星期三Ford Fulkerson 算法Ford Fulkerson 算法的基本思想是從任意一個可行流出發(fā)，尋找流的增廣鏈，并在這條增廣鏈上調(diào)整流值，進而得到一個新可行流，依次進行下去，直到一個最大流為止。定理的證明過程蘊涵著最大流算法第111頁，共131頁，2022年，5月20日，18點42分，星期三算例求下面網(wǎng)絡(luò)的最大流vsv1v3v4v2vt852879665圖4.23第112頁，共131頁，2022年，5月2

43、0日，18點42分，星期三初始0流先給網(wǎng)絡(luò)賦一個初始0流f 0 圖4.2-1vsv1v3v4v2vt8,05 ,02, 08 ,07 ,09 ,06 ,06 ,05, 03 ,0第113頁，共131頁，2022年，5月20日，18點42分，星期三(+vs, 8)(+vs, 2)(-, )尋找增廣鏈1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0第114頁，共131頁，2022年，5月20日，18點42分，星期三vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs, 8)(+vs, 2)(-, )(+v1, 5)(+v

44、3, 2)尋找增廣鏈2第115頁，共131頁，2022年，5月20日，18點42分，星期三vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs, 8)(+vs, 2)(-, )(+v1, 5)(+v3, 2)(+v2, 5)尋找增廣鏈3第116頁，共131頁，2022年，5月20日，18點42分，星期三尋找增廣鏈4找到流f 0 的增廣鏈P0 = vs v1 v2 vt.vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs, 8)(+vs, 2)(-, )(+v1, 5)(+v3, 2)(+v2, 5)增量=5.第1

45、17頁，共131頁，2022年，5月20日，18點42分，星期三調(diào)整流值2調(diào)整流值得流值為5的新可行流f 1 ，vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0第118頁，共131頁，2022年，5月20日，18點42分，星期三vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs, 3)(+vs, 2)(-, )第119頁，共131頁，2022年，5月20日，18點42分，星期三vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs, 3)(+vs, 2)(-, )(+v3, 2)(+v3, 2)第120頁，共131頁，2022年，5月20日