[互聯(lián)網(wǎng)]12997171025437500011-圖與網(wǎng)絡

1、chapter 11：圖與網(wǎng)絡模型圖與網(wǎng)絡模型l11.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念l11.2最短路問題最短路問題l11.3 最小生成樹問題最小生成樹問題l11.4 最大流問題最大流問題l11.5 最小費用最大流問題最小費用最大流問題page 3圖論：圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系 圖g區(qū)別于幾何學中的圖。這里只關(guān)心圖中有多少個點、以及哪些點之間有連線。例如：在一個人群中，對相互認識這個關(guān)系我們可以用圖來表示例如：在一個人群中，對相互認識這個關(guān)系我們可以用圖來表示一般情況下，圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。(v1)趙趙

2、(v2)錢錢(v3)孫孫(v4)李李(v5)周周(v6)吳吳(v7)陳陳e2e1e3e4e5(v1)趙趙(v2)錢錢孫孫(v3) 李李(v4)周周(v5)吳吳(v6)陳陳(v7)e2e1e3e4e5page 4圖論：圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。圖論：圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。對于反映對象之間的關(guān)系并不是重要的。圖的定義：若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，若用點表示研究的對象，用邊表示這些對象

3、之間的聯(lián)系，則圖則圖g可以定義為可以定義為 “點點” 和和 “邊邊” 的集合，記作：的集合，記作：,evg 其中其中: v點集點集 e邊集邊集 圖圖g區(qū)別于幾何學中的圖。這里只關(guān)心圖中有多少個點以區(qū)別于幾何學中的圖。這里只關(guān)心圖中有多少個點以及哪些點之間有連線。及哪些點之間有連線。無向圖page 5定義定義: 圖中的點用圖中的點用v表示，邊用表示，邊用e表示。表示。對每條邊可用它所連接的點表示，記作：，記作：e1=v1,v1; e2=v1,v2; v3e7e4e8e5e6e1e2e3v1v2v4v5l 端點，關(guān)聯(lián)邊，相鄰若有邊若有邊e可表示為可表示為 e=vi,vj，稱，稱vi和和vj是是 邊

4、邊 e 的的端點端點，反之稱，反之稱 邊邊e 為為 點點vi或或vj的的關(guān)聯(lián)邊關(guān)聯(lián)邊。若若 點點vi、vj 與同一條邊關(guān)聯(lián)，稱與同一條邊關(guān)聯(lián)，稱 點點vi和和vj 相鄰相鄰；若；若 邊邊ei和和ej 具有公共的端具有公共的端點，稱點，稱 邊邊ei和和ej 相鄰相鄰。page 6如果如果 邊邊e 的兩個端點相重，稱該邊的兩個端點相重，稱該邊為為 環(huán)環(huán)如右圖中邊如右圖中邊e1為環(huán)為環(huán)如果兩個點之間多于一條邊，稱為如果兩個點之間多于一條邊，稱為多重邊多重邊，如右圖中的，如右圖中的e4和和e5對無環(huán)、無多重邊的圖稱作對無環(huán)、無多重邊的圖稱作簡單圖簡單圖v3e7e4e8e5e6e1e2e3v1v2v4v

5、5l 環(huán)，多重邊，簡單圖page 7與某一個與某一個 點點vi 相關(guān)聯(lián)的相關(guān)聯(lián)的 邊的數(shù)目邊的數(shù)目 稱為稱為 點點vi的的次次（也叫做度），記作（也叫做度），記作d(vi)右圖中右圖中d(v1)4，d(v3)=5，d(v5)=1次為奇數(shù)的點稱作次為奇數(shù)的點稱作奇點奇點，次為偶數(shù)的，次為偶數(shù)的點稱作點稱作偶點偶點，次為，次為1的點稱為的點稱為懸掛點懸掛點，次為次為0的點稱作的點稱作孤立點孤立點。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次圖的次: 一個圖的次等于各點的次之和。一個圖的次等于各點的次之和。l 次，奇點，偶點，孤立點page 8圖中某些點和邊的交替序列，若其圖中某些點和

6、邊的交替序列，若其中各邊互不相同，且對任意中各邊互不相同，且對任意vt-1和和vt均相鄰，稱為均相鄰，稱為鏈鏈。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起點與終點重合的鏈稱作起點與終點重合的鏈稱作圈（回路）圈（回路）如果任意兩個頂點之間至少存在一條如果任意兩個頂點之間至少存在一條鏈，稱這樣的圖為鏈，稱這樣的圖為連通圖連通圖l 鏈，圈（回路），連通圖 如果我們把上面例子中的如果我們把上面例子中的“相互認識相互認識”關(guān)系改為關(guān)系改為“認識認識” ” 的關(guān)系，那么只的關(guān)系，那么只用兩點之間的連線就很難用兩點之間的連線就很難刻畫他們之間的關(guān)系了，

7、刻畫他們之間的關(guān)系了，這時我們引入一個這時我們引入一個帶箭頭帶箭頭的連線的連線，稱為，稱為弧弧。相互認。相互認識用兩條反向的弧表示。識用兩條反向的弧表示。11.1 圖與網(wǎng)絡的基本概念有向圖的定義：圖圖d被定義為被定義為 “點點” 和和 “弧弧” 的集合，記作：的集合，記作：其中其中: v點集；點集； a弧集弧集a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙趙(v2)錢錢(v3)孫孫(v4)李李(v5)周周(v6)吳吳(v7)陳陳,avd page 10無向圖無向圖 g(v, e)，對，對g的每一條的每一條 邊邊(vi , vj) 相應賦予數(shù)量指標相應賦予數(shù)量

8、指標wij，稱稱wij為邊為邊(vi , vj)上的上的權(quán)權(quán)，稱圖，稱圖g為為賦權(quán)圖賦權(quán)圖賦權(quán)的有向圖賦權(quán)的有向圖 d = (v, a)，指定一點為，指定一點為 發(fā)點發(fā)點（vs），指定另一點為），指定另一點為 收點收點（vt），稱其它點為），稱其它點為中間點中間點，并把，并把 d 中每一條弧的中每一條弧的 賦權(quán)數(shù)賦權(quán)數(shù) cij 稱為弧稱為弧(vi,vj)的的容量容量，這樣的賦權(quán)有向圖，這樣的賦權(quán)有向圖d就稱為就稱為網(wǎng)絡網(wǎng)絡910201571419256l 賦權(quán)圖，網(wǎng)絡權(quán)可以代表距離、費用、通過能力(容量) 等等page 11有些問題，如選址、管道鋪設時的選線、設備更新、投有些問題，如選址、管道

9、鋪設時的選線、設備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應用。路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應用。最短路問題對一個賦權(quán)的圖（對一個賦權(quán)的圖（g或或d）中的指定的兩個點）中的指定的兩個點 vs 和和 vt 找到一條從找到一條從 vs 到到 vt 的路，使得這條路上所有的路，使得這條路上所有 ?。ㄟ叄┑臋?quán)數(shù)的總和最小，?。ㄟ叄┑臋?quán)數(shù)的總和最小，這條路被稱之為從這條路被稱之為從vs到到vt的最短路。的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從這條路上所有弧的權(quán)數(shù)的總和被稱為

10、從vs到到vt的距離。的距離。從給定的網(wǎng)絡圖中找出一點到各點 或任意兩點之間距離最短的一條路 dijkstra 算法 (雙標號法）(3,1)v23527531512 v1（0,s)v5(8,4)v6(2,1)v3(3,3)v41. 給出給出 點點vs 以標號以標號 ( 0, s )2. 找出已標號的點的集合找出已標號的點的集合 i，沒標號的點的集合，沒標號的點的集合 j，以及，以及弧的集合弧的集合 3. 如果如果 b是空集，則計算結(jié)束。是空集，則計算結(jié)束。 如果如果vt已標號已標號 ( lt, kt )，則，則 vs到到vt的距離為的距離為lt，而，而從從 vs到到vt的最短路徑，則可以從的最

11、短路徑，則可以從vt 反向追蹤到起點反向追蹤到起點vs （根據(jù)（根據(jù) kt 的記錄）而得到。的記錄）而得到。 如果如果vt 未標號，則可以斷言不存在從未標號，則可以斷言不存在從 vs到到vt的路。的路。11.2 最短路問題dijkstra 雙標號法 的步驟：jvivvvbjiji,),(如果上述的弧如果上述的弧(b)的集合不是空集，則轉(zhuǎn)下一步。的集合不是空集，則轉(zhuǎn)下一步。4. 對對b中的每一條弧，計算中的每一條弧，計算 sij = li + cij 。在所有的。在所有的 sij中，中，找到其值為最小的弧。不妨設此弧為（找到其值為最小的弧。不妨設此弧為（vc,vd），則給），則給此弧的終點以雙標

12、號（此弧的終點以雙標號（scd , c），返回步驟），返回步驟2。11.2 最短路問題dijkstra 雙標號法 的步驟：例例1. 求下圖中求下圖中v1到到v6的最短路的最短路11.2 最短路問題dijkstra 雙標號法 ：v23527531512v1v6v5v3v4v23527531512v1v6v5v3v4（0，s）0+30+20+5（2，1）2+1（3，1）(3,3)3+73+5(8,4) v1 v1到到v6v6的最短距離的最短距離為為8 8；最短路為：最短路為：v1 v3 v1 v3 v4 v4 v6v6page 15從上例知，只要某點已標號，說明已找到起點從上例知，只要某點已標號，

13、說明已找到起點vs到到該點的最短路線及最短距離，因此可以將每個點標該點的最短路線及最短距離，因此可以將每個點標號，求出號，求出vs到任意點的最短路線，如果某個點到任意點的最短路線，如果某個點vj不能不能標號，說明標號，說明vs不可達不可達vj 。注：無向圖最短路的求法只將上述步驟中的弧改成邊即可。注：無向圖最短路的求法只將上述步驟中的弧改成邊即可。page 16例例3. 求下圖求下圖v1到各點的最短距離及最短路線。到各點的最短距離及最短路線。4526178393261216180452231039612641166188122482418所有點都已標號，點上的標號就是 v1 到該點的最短距離，

14、最短路線就是紅色的鏈。page 17課堂練習：課堂練習：1. 用用dijkstra算法求下圖從算法求下圖從v1到到v6的最短距離及路線。的最短距離及路線。v3v54v1v2v4v635222421v1到到v6的最短路為：的最短路為：6521vvvvpage 182. 求從求從v1到到v8的最短路徑的最短路徑237184566134105275934682page 19237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路徑為的最短路徑為v1v4v7v5v8，最短距離為，最短距離為10page 203. 求下圖中求下

15、圖中v1點到另外任意一點的最短路徑點到另外任意一點的最短路徑v1v2v3v4v6v5322762133page 21v1v2v3v4 v6v5322762133024714page 22v1v2v3v4 v6v5322762133024714page 23例例4. 電信公司準備在甲、乙兩地沿路架設一條光纜線，問電信公司準備在甲、乙兩地沿路架設一條光纜線，問如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。 v1 （甲地）（甲地）1517624431065

16、v2v7 (乙地乙地)v3v4v5v6page 24解：這是一個求無向圖的最短路的問題。解：這是一個求無向圖的最短路的問題。 v1 （甲地）（甲地）1517624431065v2v7 (乙地乙地)v3v4v5v6(0,s)(10,1)(13,3)(14,3)(16,5)(18,5)(22,6)甲地到乙地的最短路為：甲地到乙地的最短路為：76531vvvvvpage 25例例5. 設備更新問題。某公司使用一臺設備，在每年年初，設備更新問題。某公司使用一臺設備，在每年年初，公司就要決定是購買新的設備還是繼續(xù)使用舊設備。如果購公司就要決定是購買新的設備還是繼續(xù)使用舊設備。如果購置新設備，就要支付一定

17、的購置費，當然新設備的維修費用置新設備，就要支付一定的購置費，當然新設備的維修費用就低。如果繼續(xù)使用舊設備，可以省去購置費，但維修費用就低。如果繼續(xù)使用舊設備，可以省去購置費，但維修費用就高了。請設計一個五年之內(nèi)的更新設備的計劃，使得五年就高了。請設計一個五年之內(nèi)的更新設備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。已知：內(nèi)購置費用和維修費用總的支付費用最小。已知：設備每年年初的價格表設備每年年初的價格表年份年份12345年初價格年初價格1111121213page 26設備維修費如下表設備維修費如下表使用年數(shù)使用年數(shù)0-11-22-33-44-5每年維修費用每年維修費用568111

18、8解：解：將問題轉(zhuǎn)化為最短路問題，如下圖：用將問題轉(zhuǎn)化為最短路問題，如下圖：用vi表示表示“第第i年年年年初購進一臺新設備初購進一臺新設備”,弧（?。╲i,vj）表示第）表示第i年年初購進的設備一年年初購進的設備一直使用到第直使用到第j年年初。年年初。v1v2v3v4v5v6page 27把所有弧的權(quán)數(shù)計算如下表，把權(quán)數(shù)賦到圖中，再用把所有弧的權(quán)數(shù)計算如下表，把權(quán)數(shù)賦到圖中，再用dijkstra算法求最短路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723pag

19、e 28 最終得到下圖，可知，最終得到下圖，可知，v1到到v6的距離是的距離是53，最短路徑有兩條：，最短路徑有兩條： v1v3v6和和 v1v4v6 v1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 v2（16,1）16(30,1)(53,3)(53,4)page 29性質(zhì)性質(zhì)1：任何樹中必存在次為：任何樹中必存在次為1的點。的點。性質(zhì)性質(zhì)2：n 個頂點的樹必有個頂點的樹必有n-1 條邊。條邊。性質(zhì)性質(zhì)3：樹中任意兩個頂點之間，恰有且僅有一條鏈。：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質(zhì)性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B

20、通。：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)性質(zhì)5：樹無回圈，但不相鄰的兩個點之間加一條邊，?。簶錈o回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。得到一個圈。v1v2v3v4v5v6l 樹：無圈的連通圖即為樹11.3 最小生成樹問題圖圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)下列圖中，哪些是樹？下列圖中，哪些是樹？page 31圖圖g1=v1、e1和圖和圖g2=v2，e2，如果有如果有 ，稱，稱g1是是g2的一個的一個子圖子圖若有若有 ，則稱，則稱g1是是g2的一個的一個支撐子圖支撐子圖2121

21、eevv 和和2121eevv ，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5(a)v3e7e4e8e6e2e3v1v2v4v5(b)（g圖）圖）l 子圖，支撐子圖page 32如果如果g2是是g1的支撐圖（生成圖），又是樹圖，則稱的支撐圖（生成圖），又是樹圖，則稱g2是是g1的的生成樹（或支撐樹）。生成樹（或支撐樹）。v1v2v3v4v5v1v2v3v4v5g1g2l 圖的生成樹（支撐樹）page 33破圈法l 求支撐樹的方法：破圈法 和 避圈法page 34生成樹（支撐樹）生成樹（支撐樹）l 求支撐樹的方法：破圈法 和 避圈法page 35v1v2v

22、3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5l 求支撐樹的方法：破圈法 和 避圈法避圈法page 36最小生成樹問題：在一個賦權(quán)的、連通的、無向圖 g 中找出一個生成樹，并使得這個生成樹的所有邊的權(quán)數(shù)之和為最小l 圖的最小生成樹（支撐樹）1. 在給定的賦權(quán)的連通圖上任找一個圈在給定的賦權(quán)的連通圖上任找一個圈2. 在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。3、如果所余下的圖已不包含圈，則計算結(jié)束

23、，所余下的、如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第圖即為最小生成樹，否則返回第1步。步。求解最小生成樹的破圈算法page 37v1v2v4v5v6435215878破圈法破圈法：任取一圈，去掉圈中最長邊，直到無圈。：任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v3邊數(shù)邊數(shù)n-1=5l 圖的最小生成樹（支撐樹）6page 38v1v2v3v4v5v643521min c(t)=15l 圖的最小生成樹（支撐樹）page 39page 40page 413749346321min c(t)=12min c(t)=15254173

24、314475答案：答案：page 4234122323242min c(t)=12213638534567454321min c(t)=18例例6. 用破圈算法求圖（用破圈算法求圖（a）中的一個最小生成樹）中的一個最小生成樹11.3 最小生成樹問題v1331728541034v7v6v5v4v2v3(a)7v6v5v4v2v3(b)v133725434v7v6v5v4v2v31(c)v13372434v7v6v5v4v2v31(d)v4v1337234v7v6v5v2v31(e)v133723v7v6v5v4v2v31(f)例例7. 某大學準備對其所屬的某大學準備對其

25、所屬的7個學院辦公室計算機聯(lián)網(wǎng)，個學院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡的可能聯(lián)通的途徑如下圖，圖中這個網(wǎng)絡的可能聯(lián)通的途徑如下圖，圖中v1,v7 表表示示7個學院辦公室，請設計一個網(wǎng)絡能聯(lián)通個學院辦公室，請設計一個網(wǎng)絡能聯(lián)通7個學院辦個學院辦公室，并使總的線路長度為最短。公室，并使總的線路長度為最短。11.3 最小生成樹問題v1331728541034v7v6v5v4v2v3圖圖11-14 此問題實際上是求圖此問題實際上是求圖11-1411-14的最小生成樹，的最小生成樹，這在例這在例6 6中已經(jīng)求得，中已經(jīng)求得，即按照圖即按照圖 (f) (f) 的設計，的設計，可使此網(wǎng)絡的總的線可使此網(wǎng)絡的總的線

26、路長度為最短，為路長度為最短，為1919百米。百米。v563522241263v1v2v7v4v3v6圖圖11-2611.4 最大流問題最大流問題：給一個帶收發(fā)點的網(wǎng)絡，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。一、最大流的數(shù)學模型 例例8. 某石油公司擁有一個管道網(wǎng)絡，使用這個網(wǎng)絡可以把石油從采地某石油公司擁有一個管道網(wǎng)絡，使用這個網(wǎng)絡可以把石油從采地運送到一些銷售點，這個網(wǎng)絡的一部分如下圖所示。由于管道的直徑運送到一些銷售點，這個網(wǎng)絡的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（的變化，它的各段管道（vi,vj）的流量）的流量cij（容量

27、）是不一樣的。（容量）是不一樣的。cij的單的單位為萬加侖位為萬加侖/小時。如果使用這個網(wǎng)絡系統(tǒng)從采地小時。如果使用這個網(wǎng)絡系統(tǒng)從采地 v1向銷地向銷地 v7運送石油，運送石油，問每小時能運送多少加侖石油？問每小時能運送多少加侖石油？v563522241263v1v2v7v4v3v6圖圖11-2611.4 最大流問題 我們可以為此例題建立線性規(guī)劃數(shù)學模型：我們可以為此例題建立線性規(guī)劃數(shù)學模型： 設弧設弧(vi,vj)上流量為上流量為fij，網(wǎng)絡上的總的流量為，網(wǎng)絡上的總的流量為f，則有：，則有：1 41 22 32 51 44 34 64 72 34 33 53 62 53 55 73 64

28、66 75 76 74 71 21 4,1, 2, 6;1, 2,70,1, 2, 6;1, 2,71 2ijijijm a xf =fffffffffffffffffffffffffcijfij目 標 函 數(shù) ：約 束 條 件 ：一、最大流的數(shù)學模型11.4 最大流問題 1、在這個線性規(guī)劃模型中，其約束條件中的前、在這個線性規(guī)劃模型中，其約束條件中的前6個方程表示個方程表示了網(wǎng)絡中的流量必須滿足守恒條件：了網(wǎng)絡中的流量必須滿足守恒條件：發(fā)點的流出量必須等于收點的總流入量；發(fā)點的流出量必須等于收點的總流入量；其余的點稱之為中間點，它的總流入量必須等于總流出量。其余的點稱之為中間點，它的總流入量

29、必須等于總流出量。2、對每一條弧、對每一條弧(vi,vj)的流量的流量fij要滿足流量的可行條件，應小要滿足流量的可行條件，應小于等于弧于等于弧(vi,vj)的容量的容量cij，并大于等于零，即，并大于等于零，即0fij cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡流 fij 稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。11.4 最大流問題一、最大流的數(shù)學模型二、最大流問題的網(wǎng)絡圖論解法 對網(wǎng)絡上弧的容量的表示作改進。對一條?。▽W(wǎng)絡上弧的容量的表示作改進。對一條?。╲i,vj)的的容量我們用一對數(shù)容量我們用一

30、對數(shù)cij,0標在?。嗽诨。╲i,vj) 上，上，cij靠近靠近vi點點，0靠靠近近vj點，表示從點，表示從vi到到vj容許通過的容量為容許通過的容量為cij，而從，而從vj到到vi 容容許通過的容量為許通過的容量為0，這樣我們可以省去弧的方向了。如下圖，這樣我們可以省去弧的方向了。如下圖: (a)和和 (b)、(c)和和(d)的意義相同。的意義相同。vivjcij0（b）vivj（a） cijcijvivj（cji）（c）vivj cij cji（d）11.4 最大流問題63522241263v1v2v5v7v4v3v60000000000011.4 最大流問題二、最大流問題的網(wǎng)絡圖論解法

31、用以上方法對例用以上方法對例8的圖的容量標號作改進，得下圖：的圖的容量標號作改進，得下圖：（1）找出一條從發(fā)點到收點的路，在這條路上的每一條?。┱页鲆粭l從發(fā)點到收點的路，在這條路上的每一條弧 順流方向順流方向的容量都大于零的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。如果不存在這樣的路，則已經(jīng)求得最大流。（2）找出這條路上各條弧的）找出這條路上各條弧的 最小的順流的容量最小的順流的容量pf，從而通過這條路，從而通過這條路增加網(wǎng)絡的流量增加網(wǎng)絡的流量pf。（3）在這條路上，減少每一條弧的順流容量）在這條路上，減少每一條弧的順流容量pf ，同時增加這些弧的，同時增加這些弧的逆流容量逆流容量

32、pf，返回步驟（，返回步驟（1）。）。 * * * * * 為了使算法更快捷有效，我們一般在步驟（為了使算法更快捷有效，我們一般在步驟（1 1）中盡量選擇包）中盡量選擇包含弧數(shù)最少的路。含弧數(shù)最少的路。11.4 最大流問題二、最大流問題的網(wǎng)絡圖論解法基本算法步驟：基本算法步驟： 第一次迭代：選擇路為第一次迭代：選擇路為 v1 v4 v7 ?；。??；。?v4 , v7 ）的）的順流容量為順流容量為2，決定了，決定了pf=2，改進的網(wǎng)絡流量圖如下圖：，改進的網(wǎng)絡流量圖如下圖：63522241263v1v2v5v7v4v3v60000000000042022第一次迭代第一次迭代后的總流量后的總流量2

33、11.4 最大流問題二、最大流問題的網(wǎng)絡圖論解法用此方法對例用此方法對例8求解：求解： 第二次迭代：選擇路為第二次迭代：選擇路為v1 v2 v5 v7 。弧。弧（ v2 , v5 ）的順流容量為）的順流容量為3，決定了，決定了pf=3，改進的網(wǎng)，改進的網(wǎng)絡流量圖如下圖：絡流量圖如下圖：635222413v1v2v5v7v4v3v6000000004202203330355第二次迭代第二次迭代后的總流量后的總流量11.4 最大流問題二、最大流問題的網(wǎng)絡圖論解法 第三次迭代：選擇路為第三次迭代：選擇路為v1 v4 v6 v7 ?；?。?。?v4 , v6 ）的順流容量為）的順流容量為1，決定了，決定

34、了pf=1，改進的網(wǎng)，改進的網(wǎng)絡流量圖如下圖：絡流量圖如下圖：222413v1v2v5v7v4v3v600000042022033333013166第三次迭代第三次迭代后的總流量后的總流量11.4 最大流問題二、最大流問題的網(wǎng)絡圖論解法 第四次迭代：選擇路為第四次迭代：選擇路為v1 v4 v3 v6 v7 ?；??；。?v3 , v6 ）的順流容量為）的順流容量為2，決定了，決定了pf=2，改進的網(wǎng)絡流量，改進的網(wǎng)絡流量圖如下圖：圖如下圖： 22233v1v2v5v7v4v3v611000203203335031200213388第四次迭代第四次迭代后的總流量后的總流量111.4 最大流問題二、

35、最大流問題的網(wǎng)絡圖論解法 第五次迭代：選擇路為第五次迭代：選擇路為v1 v2 v3 v5 v7 ?；??；。?v2 , v3 ）的順流容量為）的順流容量為2，決定了，決定了pf=2，改進的網(wǎng)絡流量，改進的網(wǎng)絡流量圖如下圖：圖如下圖：22v1v2v5v7v4v3v6101202033350120213315002020510第五次迭代第五次迭代后的總流量后的總流量1011.4 最大流問題二、最大流問題的網(wǎng)絡圖論解法經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路條路路上的每一條弧順流容量都大于零，運算停止。路上的每一條弧順流容量都大于零，運算停止

36、。得到最大流量為得到最大流量為10。 最大流量圖如下圖：最大流量圖如下圖：22v1v2v5v7v4v3v612352235511.4 最大流問題二、最大流問題的網(wǎng)絡圖論解法11.5 最小費用最大流問題一個帶收發(fā)點的網(wǎng)絡，對每一條弧（vi,vj），除了給出容量cij外，還給出了這條弧的單位流量的費用bij，要求一個最大流 f，并使得總運送費用最小(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)一、最小費用最大流的數(shù)學模型 例例9. 由于輸油管道的長短不一，所以在例由于輸油管道的長短不一，所以在例6中每段管道

37、（中每段管道（ vi,vj ）除了）除了有不同的流量限制有不同的流量限制cij外，還有不同的單位流量的費用外，還有不同的單位流量的費用bij ，cij的單位為的單位為萬加侖萬加侖/小時，小時， bij的單位為百元的單位為百元/萬加侖。如下圖所示。從采地萬加侖。如下圖所示。從采地 v1 向銷向銷地地 v7 運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流量的最小費用。??？求出最大流量的最小費用。11.5 最小費用最大流問題(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2

38、）v1v2v5v7v4v3v6(6,3) 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1, 2,6;ijijijvvaijijfbfffffffffffs tffffffffffffffffffffffffffcij2,3,7),0,(1, 2,6;2,3,7),ijfij一、最小費用最大流的數(shù)學模型11.5 最小費用最大流問題一、最小費用最大流的數(shù)學模型 一般來說，所謂最小費用流的問題就是：在給定了收點和一般來說，所謂最小費用流的問題就是：在給定了收

39、點和發(fā)點并對每條弧發(fā)點并對每條弧(vi,vj)賦權(quán)以容量賦權(quán)以容量cij及單位費用及單位費用bij的網(wǎng)絡的網(wǎng)絡中，中，求一個給定流量 f 的最小費用，這個給定流量，這個給定流量 f 應小應小于等于最大流量于等于最大流量f，否則無解。，否則無解。 求最小費用流的問題的線性規(guī)劃的模型只要把最小費用最求最小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模型中的約束條件中的發(fā)點流量大流模型中的約束條件中的發(fā)點流量f改為改為f即可。即可。11.5 最小費用最大流問題二、最小費用最大流問題的網(wǎng)絡圖論解法 對網(wǎng)絡上弧（對網(wǎng)絡上?。╲i,vj）的（）的（cij,bij）的表示作如下改動）的表示作如下改動11

40、.5 最小費用最大流問題vivj（cij,bij ）（0,-bij ）（b）vivj（a）（cij,bij ）（cij,bij ）vivj（cji,bji ）（c）（cij,bij ）vivj（cji,bji ）（0,-bij)（0,-bji)（d）11.5 最小費用最大流問題二、最小費用最大流問題的網(wǎng)絡圖論解法用以上方法對例用以上方法對例9的圖形進行改進，得下圖：的圖形進行改進，得下圖：(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-

41、4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖圖11-2811-2811.5 最小費用最大流問題二、最小費用最大流問題的網(wǎng)絡圖論解法最小費用最大流的基本算法：最小費用最大流的基本算法： 在對弧的標號作了改進的網(wǎng)絡圖上求最小費用最大流的基在對弧的標號作了改進的網(wǎng)絡圖上求最小費用最大流的基本算法，與求最大流的基本算法完全一樣，不同的只是：本算法，與求最大流的基本算法完全一樣，不同的只是： * 在步驟（在步驟（1）中要選擇一條總的單位費用最小的路，而）中要選擇一條總的單位費用最小的路，而不是包含邊數(shù)最小的路。不是包含邊數(shù)最小的路。用上述方法對例用上述方法對例9求解：求解： 第一次迭

42、代：找到最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭。第一次迭代后總流量為代后總流量為1，決定了，決定了pf=1,總費用為總費用為10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖圖11-2911-2911第一次迭代第一次迭代后的總流量后的總流量11.5 最小費用最大流問題二、最小費用最大流問題的網(wǎng)絡圖論解法 第二次迭代：找到最短路第二次迭代：找到最短路

43、v1 v4 v7。第二次迭代。第二次迭代后總流量為后總流量為3，總費用，總費用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖圖11-3011-3033第二次迭代第二次迭代后的總流量后的總流量11.5 最小費用最大流問題二、最小費用最大流問題的網(wǎng)絡圖論解法 第三次迭代：找到最短路第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后總流量為第三次迭代后總流量為5，總費用，總費用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-