運(yùn)籌學(xué)11圖與網(wǎng)絡(luò)1

1、第十一章 圖與網(wǎng)絡(luò)規(guī)劃11.1 圖與網(wǎng)絡(luò)的基本概念11.2 樹(shù)及最小樹(shù)問(wèn)題11.3 最短路問(wèn)題11.4 網(wǎng)絡(luò)最大流問(wèn)題11.5 最小費(fèi)用最大流問(wèn)題10/5/2022111.1 圖與網(wǎng)絡(luò)的基本概念圖的概念 所謂圖，就是頂點(diǎn)和邊的集合，點(diǎn)的集合記為V，邊的集合記為E，則圖可以表示為：G（V，E），點(diǎn)代表被研究的事物，邊代表事物之間的聯(lián)系，因此，邊不能離開(kāi)點(diǎn)而獨(dú)立存在，每條邊都有兩個(gè)端點(diǎn)。在畫(huà)圖時(shí)，頂點(diǎn)的位置、邊和長(zhǎng)短形狀都是無(wú)關(guān)緊要的，只要兩個(gè)圖的頂點(diǎn)及邊是對(duì)應(yīng)相同的，則兩個(gè)圖相同。 10/5/20222圖的表示 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/20

2、223點(diǎn)與邊 頂點(diǎn)數(shù) 集合V中元素的個(gè)數(shù)，記作p(G)。邊數(shù) 集合E中元素的個(gè)數(shù)，記作q(G)。若e=u,vE，則稱u和v為e的端點(diǎn)，而稱e為u和v的關(guān)聯(lián)邊，也稱u，v與邊e相關(guān)聯(lián)。例如圖中的圖G，p(G)=6，q(G)=9，v1，v2是e1和e2的端點(diǎn)，e1和e2都是v1和v2的關(guān)聯(lián)邊。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/20224點(diǎn)邊關(guān)系若點(diǎn)u和v與同一條邊相關(guān)聯(lián)，則u和v為相鄰點(diǎn)；若兩條邊ei和ej有同一個(gè)端點(diǎn)，則稱ei與ej為相鄰邊。例如在圖中v1和v2為相鄰點(diǎn)， v1和v5不相鄰；e1與e5為相鄰邊，e1和e7不相鄰。 e1 e2 e3 e

3、4 e5v2 v3v1v4v5v6e6e7e8e910/5/20225簡(jiǎn)單圖若一條邊的兩個(gè)端點(diǎn)是同一個(gè)頂點(diǎn)，則稱該邊為環(huán)；又若兩上端點(diǎn)之間有多于一條邊，則稱為多重邊或平行邊。例如圖的e8為環(huán)，e1，e2為兩重邊，e4，e5也是兩重邊。含有多重邊的圖稱作多重圖。無(wú)環(huán)也無(wú)多重邊的圖稱作簡(jiǎn)單圖。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/20226圖的次次 點(diǎn)v作為邊的端點(diǎn)的次數(shù)，記作d(v)，如圖中，d(v1)=5, d(v4)=6等端點(diǎn)次為奇數(shù)的點(diǎn)稱作奇點(diǎn)；次為偶數(shù)的點(diǎn)稱作偶點(diǎn)。次為1的點(diǎn)稱為懸掛點(diǎn)，與懸掛點(diǎn)連接的邊稱作懸掛邊；次為0的點(diǎn)稱為孤立點(diǎn)。圖中的點(diǎn)v

4、5即為懸掛點(diǎn)，邊e9即為懸掛邊，而點(diǎn)v6則是弧立點(diǎn)。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/20227定理 若圖G中所有點(diǎn)都是孤立點(diǎn)，則稱圖G為空?qǐng)D。定理1 所有頂點(diǎn)的次的和，等于所有邊數(shù)的2倍。即 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/20228定理2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 設(shè)V1和V2分別是圖G中次數(shù)為奇數(shù)和偶數(shù)的頂點(diǎn)集合。由定理1有 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/20229鏈 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。v0稱為鏈的起點(diǎn)，

5、 vn稱為鏈的終點(diǎn)。若v0 vn則稱該鏈為開(kāi)鏈，反之稱為閉鏈或回路。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/202210簡(jiǎn)單鏈 若鏈中所含的邊均不相同，則稱為簡(jiǎn)單鏈；若點(diǎn)均不相同，則稱為初等鏈或通路。除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的閉鏈，稱為初等回路或稱為圈。例如圖中e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9是一條鏈，且是開(kāi)鏈，也是簡(jiǎn)單鏈，但不是初等鏈，因?yàn)関1出現(xiàn)兩次。10/5/202211圈 若鏈中所含的邊均不相同，則稱為簡(jiǎn)單鏈；若點(diǎn)均不相同，則稱為初等鏈或通路。除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的閉鏈，稱為初等回路或稱為圈。例如圖中e

6、1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9是一個(gè)圈。10/5/202212連通性 若一個(gè)圖G的任意兩點(diǎn)之間均至少有一條通路（初等鏈）連接起來(lái)，則稱這個(gè)圖G是一個(gè)連通圖，否則稱作不連通圖。例如圖中，v1和v6之間沒(méi)有通路，因此它不是連通圖，而如果去掉v6，則構(gòu)成一個(gè)連通圖。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/202213連通的意義 連通是一個(gè)很重要的概念，如果一個(gè)問(wèn)題所對(duì)應(yīng)的圖是一個(gè)不連通圖，則該問(wèn)題一定可以分解成互不相關(guān)的子問(wèn)題來(lái)加以研究，即可以把不連通圖分解成連通的子圖來(lái)研究。 e1 e2 e3 e4 e5v2 v3v1

7、v4v5v6e6e7e8e910/5/202214子圖 子圖的定義 設(shè)， G1=(V1,E1), G2=(V2,E2)，如果V1V2 ，又E1E2 ，則稱G1是G2的子圖。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9e1 e2 e3 e4 e5v2 v3v1必須指出，并不是從圖G2中任選一些頂點(diǎn)和邊在一起就組成G2的子圖G1，而只有在G2中的一條邊以及連接該邊的兩個(gè)端點(diǎn)均選入G1時(shí)，G1才是G2的子圖。10/5/202215特殊子圖 當(dāng)G1中不包含G2中所有的頂點(diǎn)和邊，則稱G1是G2的真子圖。部分圖 若V1=V2，E1E2 ，則稱G1為G2的一個(gè)部分圖。 若V1V2

8、，E1= u,v | uV1, vV1，則稱G1是G2中 由V1導(dǎo)出的導(dǎo)出子圖。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9e1 e2 e3 e4 e5v2 v3v110/5/202216有向圖在有些圖中，邊是沒(méi)有方向的，即u,v=v,u，這種圖稱為無(wú)向圖。而有些關(guān)系是不對(duì)稱的，例如父子關(guān)系、上下級(jí)關(guān)系、加工工序的先后順序等都具有單向性，用圖來(lái)表示這些關(guān)系時(shí)，得到的邊是具有方向的，用帶箭頭的線來(lái)表示，稱為弧。從頂點(diǎn)u指向的弧a，記作a=(u,v),(u,v)(v,u)，其中u稱為a的起點(diǎn)，v稱為a的終點(diǎn)，這樣的圖稱為有向圖。仍以V表示點(diǎn)的集合，以A表示弧的集合，則有

9、向圖表示為D（V，A） 10/5/202217有向圖例e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/202218有向圖的鏈路 有向圖中，在不考慮邊的方向時(shí)，也可以相同地定義鏈，若有向圖D（V，A）中，P是一個(gè)從u到v的鏈，且對(duì)P中每一條弧而言，在序列中位于該弧前面的點(diǎn)恰好是其起點(diǎn)，而位于該弧后面的點(diǎn)恰好是其終點(diǎn)，這個(gè)鏈P就稱為是D中從u到v的一條路。當(dāng)路的起點(diǎn)與終點(diǎn)相同，即u=v時(shí)，稱作一條回路。頂點(diǎn)全不相同的路稱為初等路。除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的回路稱為初等回路。 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e910/5/202219

10、11.2 樹(shù)及最小樹(shù)問(wèn)題一個(gè)沒(méi)有圈的圖稱為一個(gè)無(wú)圈圖或稱為林。一個(gè)連通的無(wú)圈圖則稱為樹(shù)，一個(gè)林的每個(gè)連通子圖都是一個(gè)樹(shù)。定理 以下關(guān)于樹(shù)的六種不同描述是等價(jià)的：無(wú)圈連通圖。無(wú)圈，q=p-1。連通，q=p-1。無(wú)圈，但若任意增加一條邊，則可得到一個(gè)且僅一個(gè)圈。連通，但若任意舍棄一條邊，圖便不連通。 每一對(duì)頂點(diǎn)之間有一條且僅有一條鏈。10/5/202220部分樹(shù) 若T是圖G（V，E）的部分圖，且T是樹(shù)，則稱T為G的部分樹(shù)。若T是圖G的部分樹(shù)，則從G中去掉T中所有的邊，所得到的子圖稱為G中的T的余樹(shù)，也稱為G的一個(gè)余樹(shù)。余樹(shù)不一定是樹(shù)！ 一個(gè)沒(méi)有圈的圖稱為一個(gè)無(wú)圈圖或稱為林。一個(gè)連通的無(wú)圈圖則稱為樹(shù)

11、，一個(gè)林的每個(gè)連通子圖都是一個(gè)樹(shù)。10/5/202221網(wǎng)絡(luò)概念圖只能用來(lái)研究事物之間有沒(méi)有某種關(guān)系，而不能研究這種關(guān)系的強(qiáng)弱程度。網(wǎng)絡(luò) 賦權(quán)的圖 權(quán) 程度的度量，數(shù)量描述。 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202222網(wǎng)絡(luò)最短樹(shù)問(wèn)題 最短樹(shù)問(wèn)題的一般提法是：選取網(wǎng)絡(luò)中的部分圖，使得網(wǎng)絡(luò)連通，且使總權(quán)數(shù)最短。在實(shí)際應(yīng)用中，經(jīng)常碰到需要求一個(gè)賦權(quán)連通圖的最短樹(shù)的問(wèn)題。例如，用節(jié)點(diǎn)表示城市，用邊表示可以在兩個(gè)城市之間架設(shè)光纜，邊上的權(quán)表示光纜的長(zhǎng)度，試求應(yīng)如何架設(shè)光纜，才能使任意兩城市之間均由光纜相通，且使光纜的總長(zhǎng)度最短。求最短樹(shù)的方法，依據(jù)的是樹(shù)的特

12、點(diǎn)，即無(wú)圈和連通，加上最短的要求，方法主要有兩種：一種稱為破圈法，一種稱為生長(zhǎng)法 10/5/202223網(wǎng)絡(luò)最短樹(shù)-破圈法原理 破圈法原理如果網(wǎng)絡(luò)圖中無(wú)圈并且q=p-1，則已經(jīng)是樹(shù)；如果網(wǎng)絡(luò)圖中有圈，則截去該圈中權(quán)數(shù)最大的邊；這樣，并不影響網(wǎng)絡(luò)圖的連通性，且能使邊數(shù)減少一個(gè)；經(jīng)過(guò)一定次數(shù)的截邊，網(wǎng)絡(luò)圖中將再也沒(méi)有圈，成為無(wú)圈圖；如果此時(shí)的網(wǎng)絡(luò)滿足q=p-1，則已經(jīng)是樹(shù)；由于每次截去的邊在圈中具有最大的權(quán)數(shù)，因此獲得的樹(shù)也是最短的樹(shù)。10/5/202224 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2破圈法步驟在網(wǎng)絡(luò)圖中尋找一個(gè)圈，若已經(jīng)無(wú)圈則轉(zhuǎn)。在圈中選取權(quán)數(shù)最大的邊，從

13、網(wǎng)絡(luò)圖中截去該邊，對(duì)新的網(wǎng)絡(luò)，轉(zhuǎn)。若q=p-1，則已找到最短樹(shù)，否則網(wǎng)絡(luò)圖不連通，無(wú)最短樹(shù)。方法示例：例 對(duì)圖中的網(wǎng)絡(luò)，用破圈法求最短樹(shù)。 10/5/202225網(wǎng)絡(luò)最短樹(shù)-生長(zhǎng)法原理 生長(zhǎng)法原理 類似于自然界中植物生長(zhǎng)的過(guò)程，結(jié)合就近生長(zhǎng)和避免構(gòu)成圈的要求，逐步生長(zhǎng)直到所有的點(diǎn)都已經(jīng)被包含。如果原網(wǎng)絡(luò)不連通，則在生長(zhǎng)過(guò)程中會(huì)出現(xiàn)某些點(diǎn)不能被生長(zhǎng)，則結(jié)束。避圈的原理是已經(jīng)被包含在生長(zhǎng)過(guò)的樹(shù)中的點(diǎn)不再被生長(zhǎng)。由于在每次生長(zhǎng)時(shí)都采用就近生長(zhǎng)的方法，生成的樹(shù)一定是最短樹(shù)。10/5/202226 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2生長(zhǎng)法步驟 從圖上任選一點(diǎn)i，令 若這樣

14、的邊不存在，則原圖沒(méi)有最短部分樹(shù)。令 若S=V，則已找到最短樹(shù)，否則，從Sk中的各點(diǎn)到Sk中各點(diǎn)的邊中選權(quán)數(shù)最小的邊，設(shè)為i，j，則10/5/202227生長(zhǎng)法示例 取S=v1, 則S到其余點(diǎn)的距離在距離矩陣中第一行10/5/202228 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/20222910/5/20223010/5/202231 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/20223211.3 最短路問(wèn)題最短路問(wèn)題的一般提法是：欲尋找網(wǎng)絡(luò)中從起點(diǎn)1到終點(diǎn)n的最短路線，即尋求連接這兩點(diǎn)的邊的總長(zhǎng)度為最小的通路，最短路線中的

15、網(wǎng)絡(luò)大都是有向網(wǎng)絡(luò)，也可以是無(wú)向網(wǎng)絡(luò)。 9757845646547sabcdeft10/5/202233最短路問(wèn)題的狄克斯拉算法 把V分成兩個(gè)集合令計(jì)算求若vk=vn則已經(jīng)求得vn到v1的最短路線，否則繼續(xù)計(jì)算 使用條件 lij010/5/202234算法解釋 若以P(vi)記v1到vi的最短距離，則根據(jù)動(dòng)態(tài)規(guī)劃原理應(yīng)有 第一步 取P(v1)0，而T(vj)則是對(duì)P(vj)所取的初值； v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202235第二步 利用P(vi)已知，據(jù)上式對(duì)T(vj)進(jìn)行修正； v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v

16、210/5/202236第三步 對(duì)T(vj)求 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202237k=2, 不是最優(yōu)，繼續(xù) v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202238在所有的T(vj)中確定最小的 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202239k=3, 不是最優(yōu)，繼續(xù) v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202240k=5, 不是最優(yōu)，繼續(xù) v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202241k

17、=6=n, 已經(jīng)是最優(yōu)。如果希望計(jì)算v1到v4的最短距離，繼續(xù) v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202242表格實(shí)現(xiàn) v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202243vjv1v2v3v4v5v6初始值T( vj )010/5/202244福德算法 適用于有負(fù)權(quán)，但無(wú)負(fù)回路的有向或無(wú)向網(wǎng)絡(luò)，設(shè)dj(k)為從1到j(luò)的邊數(shù)不超過(guò)k的路線中距離最短的。算法依據(jù)的思想是動(dòng)態(tài)規(guī)劃最優(yōu)性原理，在此處形成遞推公式： 其算法步驟如下： 令計(jì)算若對(duì)所有j則最優(yōu)，否則把k的值加1，繼續(xù)計(jì)算。若k=n-1，則說(shuō)明存在負(fù)回路，最短路線不

18、存在。 10/5/202245福德算法示例 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202246 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v210/5/202247 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2025(2)10(2)9(3)10/5/202248 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2620025(2)10(2)9(3)10(5)8(3)1052010/5/202249例 求：5年內(nèi)，哪些年初購(gòu)置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。 解：（1）分析：可行的購(gòu)置方案（更新計(jì)劃）是

19、很多的， 如： 1） 每年購(gòu)置一臺(tái)新的，則對(duì)應(yīng)的費(fèi)用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購(gòu)置新的，一直用到第五年年底，則總費(fèi)用為： 11+5+6+8+11+18 = 59 顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。 第i年度 1 2 3 4 5購(gòu)置費(fèi) 11 11 12 12 13設(shè)備役齡 0-1 1-2 2-3 3-4 4-5維修費(fèi)用 5 6 8 11 1810/5/202250 （2）方法：將此問(wèn)題用一個(gè)賦權(quán)有向圖來(lái)描述，然后求這個(gè)賦權(quán)有向圖的最短路。 求解步驟： 1）畫(huà)賦權(quán)有向圖： 設(shè) Vi 表示第i年初，(Vi ,Vj )表示第i 年初購(gòu)買(mǎi)新設(shè)備用到第j年

20、初（j-1年底），而Wi j 表示相應(yīng)費(fèi)用，則5年的一個(gè)更新計(jì)劃相當(dāng)于從V1 到V6的一條路。 2）求解 （標(biāo)號(hào)法） 10/5/202251W12 =11+5=16W13 =11+5+6=22W14 =11+5+6+8=30W15 =11+5+6+8+11=41W16 =11+5+6+8+11+18=59 W23 =11+5=16 W24 =11+5+6=22W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6=23W36 =12+5+6+8=31

21、 10/5/20225211.4 網(wǎng)絡(luò)最大流問(wèn)題所謂最大流問(wèn)題就是在一定的條件下，要求流過(guò)網(wǎng)絡(luò)的物流、能量流或信息流等流量為最大的問(wèn)題，在最大流問(wèn)題中一般有如下規(guī)定：網(wǎng)絡(luò)有一個(gè)起點(diǎn)s和一個(gè)終點(diǎn)t網(wǎng)絡(luò)是有向網(wǎng)絡(luò)，即流有方向性。在網(wǎng)絡(luò)各條弧上都有一個(gè)權(quán)，表示允許流過(guò)的最大流量。若以bij表示由i到j(luò)的弧上允許流過(guò)的最大流量，以xij表示實(shí)際流過(guò)該弧的流量，則0 xij bij網(wǎng)絡(luò)中，除起點(diǎn)s和終點(diǎn)t之外的任何頂點(diǎn)，流入量總和應(yīng)該等于流出量的總和。 10/5/202253最大流問(wèn)題的數(shù)學(xué)模型 vs1011 65 4 7 3 915vt v5 v3 v4 v210/5/202254最大流-最小割集定理

22、 最大流最小割集定理揭示了最小割集（網(wǎng)絡(luò)中的瓶頸）容量與最大流量的關(guān)系，也提供了一個(gè)求最大流的方法。網(wǎng)絡(luò)割集容量最小割集 所有割集中容量最小的一個(gè)割集。流過(guò)網(wǎng)絡(luò)的最大流量等于最小割集的容量割集10/5/202255 vs1011 65 4 7 3 915vt v5 v3 v4 v229(vs v2) (v3 v2) (v3 v4) (v3 v5)v2 v4 v5 vtvs v3.20(vs v3) (v2 v4) (v2 v5)v3 v4 v5 vtvs v224(vs v2) (vs v3)v2 v3 v4 v5 vtvs容量割集SS10/5/202256福德富克遜方法原理 算法的原理首先,

23、依據(jù)最大流問(wèn)題的要求,為網(wǎng)絡(luò)分配一個(gè)可行流。所謂可行流,是指所有弧上流量滿足容量限制,所有中間點(diǎn)滿足平衡條件的流；若這一可行流的流量就是最大流量，則問(wèn)題已經(jīng)解決；若不是最大流量，則增加流量獲得流量更大的可行流。網(wǎng)絡(luò)中的最大流量fmax值大小是由網(wǎng)絡(luò)中最狹窄處瓶頸的容量所決定的。 10/5/202257福德富克遜方法流圖 10/5/202258福德富克遜方法討論 若弧(vi,vj)上的流量滿足xij=bij，則稱該弧為飽和弧，否則稱為非飽和弧。 若弧(vi,vj)上的流量xij=0。則稱該弧為零流弧，否則稱為非零流弧。 一條從s到t的初等鏈?zhǔn)怯蓅開(kāi)始的點(diǎn)、邊序列，其中沒(méi)有相同的點(diǎn)，也不考慮弧的方

24、向。 把這條鏈中的s到t方向相同的弧稱為正向弧。 把這條鏈中的s到t方向相反的弧稱為逆向弧。在上述的可行流中，從s到t的某個(gè)初等鏈滿足： 其上的正向弧均為非飽和弧。 其上的逆向弧均為非零流弧。則稱該鏈為一條流量增廣鏈。 10/5/202259流量增廣鏈: 從s到t的某個(gè)初等鏈滿足 其上的正向弧均為非飽和弧。 其上的逆向弧均為非零流弧。結(jié)論：若在可行流中，存在從s到t的增廣鏈，則該可行流不是最大流，其流量可以增加；否則若不存在從s到t的增廣鏈，則該可行流是最大流。 增廣鏈的性質(zhì)： Vs到增廣鏈上任一點(diǎn)也有增廣鏈; 增廣鏈上任一點(diǎn)到Vt也有增廣鏈;10/5/202260福德富克遜方法步驟 為網(wǎng)絡(luò)分

25、配初始流xij標(biāo)在圖中弧旁的( )內(nèi)尋求增廣鏈，若不存在，則已最優(yōu), 否則在增廣鏈上調(diào)整流量，產(chǎn)生新的可行流。 重復(fù)、兩步，直到最優(yōu)。10/5/202261尋求增廣鏈的方法 尋求流量增廣鏈的方法，是依據(jù)增廣鏈的性質(zhì)而產(chǎn)生的，其基本思路類似于最短樹(shù)問(wèn)題的生長(zhǎng)法。從s開(kāi)始，逐個(gè)檢查每個(gè)點(diǎn)i，看是否存在從s到i的增廣鏈。如果存在從s到i的增廣鏈， 而（Vi Vj）非飽和或（Vj Vi）非零流，則存在從V1到Vj的增廣鏈。 10/5/202262福德富克遜方法示例 為網(wǎng)絡(luò)分配初始流xij標(biāo)在圖中弧旁的( )內(nèi) vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(1)(

26、5)(7)(5)(8)10/5/202263尋求增廣鏈從s開(kāi)始，賦上標(biāo)記（，），表示s是源點(diǎn)，能夠得到任意多的量。s稱為已標(biāo)記的點(diǎn)。也表示增廣鏈可以從V1延伸到V1 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(1)(5)(7)(5)(8)-, 10/5/202264如果vi是已經(jīng)標(biāo)記的點(diǎn), vj是未標(biāo)記的點(diǎn)則當(dāng)(vi ,vj)是非飽和弧時(shí), vj可以標(biāo)記: vi+,ej ej=minei, bij-xij 當(dāng)(vj ,vi)是非零流弧時(shí), vj可以標(biāo)記: vi-,ej ej=minei, xji如果vt可以標(biāo)記,則找到增廣鏈, 否則繼續(xù).如果對(duì)于一切未

27、標(biāo)記的點(diǎn), 均不能再標(biāo)記, 則已經(jīng)是最優(yōu).10/5/202265如圖v1是已經(jīng)標(biāo)記的點(diǎn), 其它點(diǎn)是未標(biāo)記的點(diǎn) (v1 ,v2)是非飽和弧, v2可以標(biāo)記: v1+,e2 e2=mine1,b12-x12 (v1 ,v3)是飽和弧, 目前v3和其它點(diǎn)暫時(shí)不能標(biāo)記，即暫時(shí)沒(méi)有從v1 到v3或其它點(diǎn)的增廣鏈。 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(1)(5)(7)(5)(8)-, vs+, 1110/5/202266如圖v2是已經(jīng)標(biāo)記的點(diǎn), v3是未標(biāo)記的點(diǎn) (v3 ,v2)是非零流弧, v3可以標(biāo)記: v2-,e3 e3=mine2, x32=min

28、11,3-, vs+, 11v2-, 3v2+, 4v3+, 3v5+, 4 vs115 4 315vt v5 v3 v4 v2(4)(9)(1)(5)(7)(5)(8)10 7 9(3) 610/5/202267vt已經(jīng)標(biāo)記, 找到流量增廣鏈。 vs10115 6 4 7 3 915vt v5 v3 v4 v2(4)(9)(3)(1)(5)(7)(5)(8)-, vs+, 11v2-, 3v2+, 4v3+, 3v5+, 4正向流流量增加et，逆向流流量減少et 調(diào)整后流量 f=1710/5/202268 vs10115 4 315vt v5 v3 v4 v2(8)(9)(3)(1)(5)(

29、7)(9)(8)(4) 9 6 7-, vs+, 7v2-, 3v3+, 1v3+, 3v4+, 3vt已經(jīng)標(biāo)記, 找到流量增廣鏈。10/5/202269正向流流量增加et=3，逆向流流量減少et調(diào)整后流量 f=20 vs10115 4 315vt v5 v3 v4 v2(11)(9)(4)(5)(7)(9)(11)(4) 9 6 710/5/202270vsv2已經(jīng)標(biāo)記，其余點(diǎn)不能標(biāo)記，已經(jīng)最優(yōu)最大流量 fmax=20 vs10115 4 315vt v5 v3 v4 v2(11)(9)(4)(5)(7)(9)(11)(4) 9 6 7-, vs+, 410/5/20227111.5 最小費(fèi)

30、用最大流問(wèn)題定義 已知網(wǎng)絡(luò)G =(V，E，C，d)，f 是G上的一個(gè)可行流， 為一條從vs到vt的增廣鏈， 稱為鏈的費(fèi)用。 若 * 是從vs到vt的增廣鏈中費(fèi)用最小的增廣鏈，則稱 * 是最小費(fèi)用增廣鏈。結(jié)論：如果可行流 f在流量為W(f )的所有可行流中的費(fèi)用最小，并且 *是關(guān)于f 的所有增廣鏈中的費(fèi)用最小的增廣鏈，那么沿增廣鏈 *調(diào)整可行流f，得到的新可行流f *也是流量為W(f*)的所有可行流中的最小費(fèi)用流。當(dāng)f * 是最大流時(shí)，就是最小費(fèi)用最大流。 10/5/202272尋找關(guān)于f 的最小費(fèi)用增廣鏈： 構(gòu)造一個(gè)關(guān)于f 的賦權(quán)有向圖L(f ) ，其頂點(diǎn)是原網(wǎng)絡(luò)G的頂點(diǎn)，而將G中的每一條弧 ( vi, vj )變成兩個(gè)相反方向的?。╲i， vj）和(vj , vi)，并且定義圖中弧的權(quán)l(xiāng)ij為：1.當(dāng) ，令 2.當(dāng)（vj，vi）為原來(lái)網(wǎng)絡(luò)G中（vi， vj）的反向弧，令 在網(wǎng)絡(luò)G中尋找關(guān)