第八章圖與網(wǎng)絡(luò)分析2ppt課件

1、第第1頁頁第八章第八章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析 最短路問題最短路問題 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題 最小費(fèi)用最大流問題最小費(fèi)用最大流問題 第第2頁頁第八章第八章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析 最短路問題最短路問題 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題 最小費(fèi)用最大流問題最小費(fèi)用最大流問題 第第3頁頁最短路問題最短路問題第第4頁頁最短路問題提出最短路問題提出在現(xiàn)實生活中，除公路運(yùn)輸網(wǎng)絡(luò)、電訊網(wǎng)絡(luò)在現(xiàn)實生活中，除公路運(yùn)輸網(wǎng)絡(luò)、電訊網(wǎng)絡(luò)等網(wǎng)絡(luò)圖以外，還有輸油管線這樣的圖。在輸油等網(wǎng)絡(luò)圖以外，還有輸油管線這樣的圖。在輸油管線圖中，為反映油的輸送情況，兩點間不僅有管線圖中，為反映油的輸送情況，兩點間不僅有連線，線上往

2、往還標(biāo)有箭頭，以表示油的流動方連線，線上往往還標(biāo)有箭頭，以表示油的流動方向。又如，指揮系統(tǒng)圖、控制系統(tǒng)圖等圖中都標(biāo)向。又如，指揮系統(tǒng)圖、控制系統(tǒng)圖等圖中都標(biāo)有指向。從這樣的一類圖中就可以概括為有向圖有指向。從這樣的一類圖中就可以概括為有向圖的概念。的概念。第第5頁頁有向網(wǎng)絡(luò)與混合圖有向網(wǎng)絡(luò)與混合圖 如果在圖如果在圖D=D=（V V，A A中，給每一弧賦予權(quán)值，如中，給每一弧賦予權(quán)值，如 將弧將弧aij=(vi,vj)aij=(vi,vj)有權(quán)值有權(quán)值 wij wij，記為，記為w(aij)=wijw(aij)=wij則賦權(quán)有向圖則賦權(quán)有向圖D=D=（V V，A A稱為有向網(wǎng)稱為有向網(wǎng)絡(luò)，在不至

3、于混淆時，也簡稱網(wǎng)絡(luò)。絡(luò)，在不至于混淆時，也簡稱網(wǎng)絡(luò)。 混合圖如果一個圖中既有邊，也有弧，那么稱這混合圖如果一個圖中既有邊，也有弧，那么稱這種圖為混合圖。它往往出現(xiàn)在既有單行線，又有種圖為混合圖。它往往出現(xiàn)在既有單行線，又有雙行線的交通圖中。雙行線的交通圖中。12534372第第6頁頁最短路問題引例最短路問題引例下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條線所需的費(fèi)用?，F(xiàn)在某人要從線所需的費(fèi)用。現(xiàn)在某人要從v1v1出發(fā)，通過這個交出發(fā)，通過這個交通網(wǎng)到通網(wǎng)到v8v8去，求使總費(fèi)用最小的旅行路線。去，求使總費(fèi)用最小的旅行路線。v2v523464v3v1

4、v4v6121061210v8v9v72363從從v1v1到到v8v8：P1=P1=（v1v1，v2v2，v5v5，v8v8） 費(fèi)用費(fèi)用 6+1+6=13 6+1+6=13P2=P2=（v1v1，v3v3，v4v4， v6 v6， v7 v7， v8 v8） 費(fèi)用費(fèi)用 3+2+10+2+4=21 3+2+10+2+4=21P3= P3= 從從v1v1到到v8v8的旅行路線的旅行路線 從從v1v1到到v8v8的路。的路。旅行路線總費(fèi)用旅行路線總費(fèi)用 路上所有弧權(quán)之和。路上所有弧權(quán)之和。最短路問題中，不考慮有向環(huán)、并行弧。最短路問題中，不考慮有向環(huán)、并行弧。v2v523464v3v1v4v6121

5、061210v8v9v72363第第8頁頁幾個概念幾個概念路：設(shè)路：設(shè)p是是D中一個首尾相連的弧的集合，如果中一個首尾相連的弧的集合，如果vs是是它的第一條弧的始點，它的第一條弧的始點，vt是它的最后一條弧的是它的最后一條弧的終點，則稱它是以點終點，則稱它是以點vi為始點，以點為始點，以點vt為終點的為終點的一條路。一條路。路長：路路長：路p中所有弧的權(quán)值的和稱為路中所有弧的權(quán)值的和稱為路p的長，記為的長，記為設(shè)圖設(shè)圖D=D=（V V，A A是一有向網(wǎng)絡(luò)是一有向網(wǎng)絡(luò)paijijawpw)()( v2v523464v3v1V4 v6121061210v8v9v72363第第9頁頁設(shè)設(shè)P P是以點

6、是以點vsvs為始點，以點為始點，以點vtvt為終點的所有路的集合，為終點的所有路的集合， 假如假如 , ,且且 ，則稱，則稱p0p0是以點是以點vsvs 為始點，以點為始點，以點vtvt為終點的最短路。而稱其路長為為終點的最短路。而稱其路長為點點 vs vs到點到點vtvt的距離，記為的距離，記為 。幾個概念幾個概念Pp 0)()(0pwMinpwPp)(),(0pwvvdts注意：在有向網(wǎng)絡(luò)中注意：在有向網(wǎng)絡(luò)中, ,一般一般),(),(sttsvvdvvd最短路及一點到另一點的距離最短路及一點到另一點的距離第第10頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近

7、算法逐步逼近算法 路矩陣算法路矩陣算法第第11頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第12頁頁求解最短路問題的求解最短路問題的Dijkstra算法算法條件：當(dāng)所有條件：當(dāng)所有wij0時，用來求給定點時，用來求給定點vs到任一到任一個點個點vj最短路的公認(rèn)的最好方法。最短路的公認(rèn)的最好方法。事實：如果事實：如果P是是D中從中從vs到到vj的最短路，的最短路，vi是是P中的一中的一基解基解個點，那么，從個點，那么，從vs沿沿P到到vi的路是從的路是從vs到到vi的的最基解最基解短路。短路。 Dijkstra算法是Dijk

8、stra在1959年提出的，可用于求解指定兩點間的最短路問題，或從指定點到其余各點的最短路問題。由于其以標(biāo)號為主要特征，又稱為標(biāo)號法。v1v2v3v4v5最短路的子路是最短路最短路的子路是最短路第第13頁頁Dijkstra算法算法0ijw 第第14頁頁 1. 1.標(biāo)號標(biāo)號 P P固定標(biāo)號或永久性標(biāo)號）固定標(biāo)號或永久性標(biāo)號）從始點到該標(biāo)號點的最短路權(quán)從始點到該標(biāo)號點的最短路權(quán)ui ui 。 2. 2.標(biāo)號標(biāo)號 T T臨時性標(biāo)號）臨時性標(biāo)號）從始點到該標(biāo)號點的最短路權(quán)上界從始點到該標(biāo)號點的最短路權(quán)上界ui ui 。選用符號的意義選用符號的意義P( i, ui)3.前點標(biāo)號前點標(biāo)號i表示點表示點vs

9、到到vj的最短路上的最短路上vj的前一點。的前一點。T( i, ui)Dijkstra算法步驟：算法步驟： ijijjwvPvTvT)(),(min)( ,)ijv vE0)(1 vP0jv )()(min0jsvjvTvTj 1,6圖上標(biāo)號法圖上標(biāo)號法v5v223464v3v1v4121061210v8v9v72363v60,01,1,1,31,1,1,1,11,1永久標(biāo)號永久標(biāo)號永久標(biāo)號永久標(biāo)號臨時標(biāo)號臨時標(biāo)號1,6圖上標(biāo)號法圖上標(biāo)號法v5v223464v3v1v4121061210v8v9v72363v60,01,1,11,1,31,1,1,0,01,14,111,3永久標(biāo)號永久標(biāo)號臨時

10、標(biāo)號臨時標(biāo)號v5v223464v3v1v4121061210v8v9v72363v60,01,1,1,11,1,1,1,3圖上標(biāo)號法圖上標(biāo)號法4,111,31,63,53,5永久標(biāo)號永久標(biāo)號臨時標(biāo)號臨時標(biāo)號v5v223464v3v1v4121061210v8v9v72363v60,01,4,111,11,1,1,1,3圖上標(biāo)號法圖上標(biāo)號法3,52,62,6永久標(biāo)號永久標(biāo)號臨時標(biāo)號臨時標(biāo)號v5v223464v3v1v4121061210v8v9v72363v60,01,4,111,11,1,1,35,125,95,9圖上標(biāo)號法圖上標(biāo)號法3,52,6永久標(biāo)號永久標(biāo)號臨時標(biāo)號臨時標(biāo)號v5v22346

11、4v3v1v4121061210v8v9v72363v60,04,111,11,5,121,35,95,123,52,6圖上標(biāo)號法圖上標(biāo)號法永久標(biāo)號永久標(biāo)號臨時標(biāo)號臨時標(biāo)號4,11v5v223464v3v1v4121061210v8v9v72363v64,110,01,11,1,35,123,52,6圖上標(biāo)號法圖上標(biāo)號法5,9永久標(biāo)號永久標(biāo)號臨時標(biāo)號臨時標(biāo)號標(biāo)號結(jié)束標(biāo)號結(jié)束反向追蹤反向追蹤第第23頁頁例例 求如下交通網(wǎng)絡(luò)中各對點間最短路路長。求如下交通網(wǎng)絡(luò)中各對點間最短路路長。DijkstraDijkstra算法標(biāo)號法算例算法標(biāo)號法算例31025v4v1v2v5v312262448混合圖混合圖

12、第第24頁頁 無向網(wǎng)絡(luò)無向網(wǎng)絡(luò): :負(fù)權(quán)弧時。負(fù)權(quán)弧時。wijvivjwijwijvjvi無向網(wǎng)絡(luò)中，最短路無向網(wǎng)絡(luò)中，最短路最短鏈。最短鏈。多個點對之間最短路？多個點對之間最短路？v1v2v312-3Dijkstra算法失效算法失效Dijkstra算法注意的問題算法注意的問題逐步逼近算法逐步逼近算法路矩陣算法路矩陣算法第第25頁頁5727461263202657710v3v1v2v4v5v6v7練習(xí)：求如下無向網(wǎng)絡(luò)中練習(xí)：求如下無向網(wǎng)絡(luò)中v1v1到到v7v7的最短路的最短路Dijkstra算法求最短鏈算法求最短鏈第第26頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步

13、逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第27頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第28頁頁逐次逼近算法逐次逼近算法 計算指定點計算指定點v1v1到其余各點的最短路時，到其余各點的最短路時，某些問題會出現(xiàn)有負(fù)權(quán)弧的圖某些問題會出現(xiàn)有負(fù)權(quán)弧的圖, ,如：如： 此時此時DijkstraDijkstra算法標(biāo)號法有可能失效。算法標(biāo)號法有可能失效。逐次逼近法對于這類問題的解決很有幫助。逐次逼近法對于這類問題的解決很有幫助。 v1v2v312-3第第29頁頁逐次逼近算法思想逐次逼近算法思想該公式表明，該公式表明，P(1)

14、1j中的第中的第j個分量等于個分量等于P(0)1j的分量的分量與基與基本表中第本表中第j列相應(yīng)元素路長的最小值，它相當(dāng)于在點列相應(yīng)元素路長的最小值，它相當(dāng)于在點v1與與vj之間插入一個轉(zhuǎn)接點之間插入一個轉(zhuǎn)接點v1,v2,vn中的任一個，含點中的任一個，含點v1與與vj后所有可能路中的最短路的路長；每迭代一次，就相后所有可能路中的最短路的路長；每迭代一次，就相當(dāng)于增加一個轉(zhuǎn)接點，而當(dāng)于增加一個轉(zhuǎn)接點，而P(k)1j中的每一個分量則隨著中的每一個分量則隨著k的的增增加呈不增的趨勢，直到出現(xiàn)穩(wěn)定。加呈不增的趨勢，直到出現(xiàn)穩(wěn)定。)1(11)(1ijkinikjwPMinP第第30頁頁用于計算指定點用于

15、計算指定點v1v1到其余各點的最短路到其余各點的最短路)1(11)(1ijkinikjwPMinPj=1,2,n. k=1,2,tn.2.2.計算計算逐次逼近算法基本步驟逐次逼近算法基本步驟jjwP1)0(1 j=1,2,n.1.1.令令(k)(1)11kjjPP其元素既是其元素既是v1v1到到vjvj的最短路長。的最短路長。3.3.當(dāng)出現(xiàn)當(dāng)出現(xiàn)時，時，例例 計算從點計算從點v1v1到所有其它頂點的最短路到所有其它頂點的最短路解：初始條件為解：初始條件為 3, 5, 2, 0114113112111PPPP 以后按照公式以后按照公式 進(jìn)行迭代。進(jìn)行迭代。 直到得到直到得到 ，迭代停止。，迭代停

16、止。v1v2v3v4v6v5v8v72-35467-24-3342-1)1(11)(1ijkinikjwPMinP) 1(1)(1tjtjPPv1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij 11jP 21jP 31jP 41jP 51jP 61jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-2042000253021230312561361102123031256123661368150212303123653123661236613687141236810021230312365312366123687912

17、3681002123031236612368791236810123653利用下利用下標(biāo)追蹤標(biāo)追蹤路徑路徑第第33頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第34頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第35頁頁 某些問題需要求網(wǎng)絡(luò)上任意兩點間的最短路。某些問題需要求網(wǎng)絡(luò)上任意兩點間的最短路。當(dāng)然，它也可以用標(biāo)號算法依次改變始點的辦法當(dāng)然，它也可以用標(biāo)號算法依次改變始點的辦法來計算，但是比較麻煩。來計算，但是比較麻煩。 這里介紹這里介紹Floyd

18、Floyd在在19621962年提出的路矩陣法，年提出的路矩陣法，它可直接求出網(wǎng)絡(luò)中任意兩點間的最短路。它可直接求出網(wǎng)絡(luò)中任意兩點間的最短路。FloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想第第36頁頁 網(wǎng)絡(luò)D=（V，A，W），令U=(dij)nn， 表示D中vi到vj的最短路的長度。iju 考慮D中任意兩點vi，vj，如將D中vi，vj以外的點都刪掉，得只剩vi，vj的一個子網(wǎng)絡(luò)D0，記ij(0)ij ,A ijwv vd當(dāng)否wij為?。榛。?vi，vj的權(quán)。的權(quán)。 在D0中加入v1及D中與vi，vj，v1相關(guān)聯(lián)的弧，得D1，D1中vi到vj的最短路記為 ,則一定有(1)i

19、jd(1)(0)(0)(0)i11j min, ijijddddvivjv1wijFloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想第第37頁頁 再在D1中加入v2及D中與vi，vj，v1， v2相關(guān)聯(lián)的弧，得D2，D2中vi到vj的最短路長記為 ，則有(2)ijd(2)(1)(1)(1)iji22 j min, ijdddd隨著轉(zhuǎn)接點的逐步增加隨著轉(zhuǎn)接點的逐步增加, ,我們會發(fā)現(xiàn)我們會發(fā)現(xiàn) 二指定點間路的條數(shù)也會隨之增加，但是其最短路二指定點間路的條數(shù)也會隨之增加，但是其最短路及路長可以確定；及路長可以確定； 當(dāng)當(dāng)V V中所有的點都可以作為轉(zhuǎn)接點時，指定點中所有的點都可以作為轉(zhuǎn)

20、接點時，指定點vivi到到vjvj間所有路中的最短路自然是圖中指定點間所有路中的最短路自然是圖中指定點vivi到到vjvj間的最短路。間的最短路。FloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想第第38頁頁FloydFloyd算法算法( (路矩陣法路矩陣法) )步驟步驟設(shè)有有向網(wǎng)絡(luò)設(shè)有有向網(wǎng)絡(luò)D=D=（V V，A A），其權(quán)矩陣為），其權(quán)矩陣為A=(aij)nnA=(aij)nn，AvvjiAvvwajijiijij),( , 0),( ,如下構(gòu)造路矩陣序列：如下構(gòu)造路矩陣序列：則則n n階路矩陣階路矩陣D(n)D(n)中的元素中的元素d(n)ijd(n)ij就是就是vivi到

21、到vjvj的最短路的路長。的最短路的路長。令權(quán)矩陣令權(quán)矩陣A為初始路矩陣為初始路矩陣D0），即令），即令D0）=A2. 2. 依次計算依次計算K K階路矩陣階路矩陣D DK K）= =（d(k)ijd(k)ijnn, k=1,2,nnn, k=1,2,n，,) 1() 1() 1()(kkjkikkijkijdddMind這里這里第第39頁頁路矩陣序列的含義路矩陣序列的含義 K K階路矩陣階路矩陣D DK K） 其中的元素表示相應(yīng)兩點間可能以點其中的元素表示相應(yīng)兩點間可能以點v1v1、v2v2、vkvk為為 轉(zhuǎn)接點的所有路中路長最短的路的路長。轉(zhuǎn)接點的所有路中路長最短的路的路長。D0）其中的任

22、一元素表示相應(yīng)兩點間無轉(zhuǎn)接點時最短路路長。其中的任一元素表示相應(yīng)兩點間無轉(zhuǎn)接點時最短路路長。一階路矩陣一階路矩陣D D1 1） 其中的元素表示相應(yīng)兩點間可能以點其中的元素表示相應(yīng)兩點間可能以點v1v1為轉(zhuǎn)接點的所為轉(zhuǎn)接點的所有路中路長最短的路的路長；有路中路長最短的路的路長；為使計算程序化，轉(zhuǎn)接點按頂點下標(biāo)的順序依次加入為使計算程序化，轉(zhuǎn)接點按頂點下標(biāo)的順序依次加入n n階路矩陣階路矩陣D(n)D(n) 其中的元素其中的元素d(n)ijd(n)ij就是就是vivi到到vjvj的可能以點的可能以點v1v1、v2v2、vnvn為轉(zhuǎn)接點的所有路中路長最短的路的路長。既是為轉(zhuǎn)接點的所有路中路長最短的路

23、的路長。既是vivi到到vjvj的最短路的路長。的最短路的路長。第第40頁頁例例 求如下交通網(wǎng)絡(luò)中各對點間最短路路長。求如下交通網(wǎng)絡(luò)中各對點間最短路路長。051250 102 A2302826042440該圖的權(quán)矩陣為：該圖的權(quán)矩陣為：FloydFloyd算法算法( (路矩陣法路矩陣法) )算例算例31025v4v1v2v5v312262448第第41頁頁例例 求如下交通網(wǎng)絡(luò)中各對點間最短路路長。求如下交通網(wǎng)絡(luò)中各對點間最短路路長。FloydFloyd算法算法( (路矩陣法路矩陣法) )算例算例 0051250 102 D =A230282604244031025v4v1v2v5v312262

24、448 0051250 102 D =A2302826042440(1)(0)(0)(0)i11j min, ijijdddd利用公式利用公式發(fā)現(xiàn)第一行，第一列元素不變發(fā)現(xiàn)第一行，第一列元素不變 105125 D220213621472302841274133042440031025v4v1v2v5v312262448 105125 D2202136214723028412741330424400(2)(1)(1)(1)i22j min, ijijdddd利用公式利用公式發(fā)現(xiàn)第二行，第二列元素不變發(fā)現(xiàn)第二行，第二列元素不變 255 D021362341272214721470232554133

25、44400121257202521731025v4v1v2v5v312262448 255 D0213621472302325541274133042440012214712572025217(3)(2)(2)(2)i33j min, ijijdddd利用公式利用公式發(fā)現(xiàn)第三行，第三列元素不變發(fā)現(xiàn)第三行，第三列元素不變0 3 D21363232554133412001324213256502147224132604531624031025v4v1v2v5v31226244802147204127042400221471257 3 D2136323255413341200132421325650

26、21472241326045316240 4 D0213623032552011325/1456202413264133440221472531/5416413245(4)(3)(3)(3)i44j min, ijijdddd利用公式利用公式發(fā)現(xiàn)第四行，第四列元素不變發(fā)現(xiàn)第四行，第四列元素不變31025v4v1v2v5v31226244831025v4v1v2v5v312262448 4 D021362147230325502401202413264133440221472531/54164132451325/1456 5 D0213621472303255024012024132641334

27、40221472531/54164132451325/1456D(5)中的元素給出相應(yīng)兩點間中的元素給出相應(yīng)兩點間的最短路，其下標(biāo)給出最短路的最短路，其下標(biāo)給出最短路個頂點下標(biāo)個頂點下標(biāo),比如：比如：第第47頁頁練習(xí)練習(xí) 已知有已知有7 7個村子，相互間道路的距離如下圖個村子，相互間道路的距離如下圖示。擬合建一所小學(xué)，已知示。擬合建一所小學(xué)，已知A A處有小學(xué)生處有小學(xué)生3030人，人，B B處處4040人，人，C C處處2525人，人，D D處處2020人，人，E E處處5050人，人，F(xiàn) F處處6060人，人， G G處處6060人人, ,問小學(xué)應(yīng)建在哪一個村子，使學(xué)生上學(xué)最問小學(xué)應(yīng)建在哪

28、一個村子，使學(xué)生上學(xué)最方便原則所有人走的總路程最短；盡可能公方便原則所有人走的總路程最短；盡可能公平。）。平。）。FloydFloyd算法算法( (路矩陣法路矩陣法) )算例算例AGFECB522747163D26第第48頁頁第八章第八章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析 最短路問題最短路問題 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題 最小費(fèi)用最大流問題最小費(fèi)用最大流問題 第第49頁頁第八章第八章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析 最短路問題最短路問題 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題 最小費(fèi)用最大流問題最小費(fèi)用最大流問題 第第50頁頁網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題50年代福特年代福特Ford）、富克遜）、富克遜Fulkerson

29、建立建立的的“網(wǎng)絡(luò)流理論網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。第第51頁頁問題的提出問題的提出 在一個輸油管網(wǎng)中，有生產(chǎn)石油的油井、儲存石油的油在一個輸油管網(wǎng)中，有生產(chǎn)石油的油井、儲存石油的油庫、轉(zhuǎn)運(yùn)石油的中間泵站，同時，還有各種口徑不同的輸油庫、轉(zhuǎn)運(yùn)石油的中間泵站，同時，還有各種口徑不同的輸油管。當(dāng)一個輸油管網(wǎng)給定后，單位時間內(nèi)最多可把多少石油管。當(dāng)一個輸油管網(wǎng)給定后，單位時間內(nèi)最多可把多少石油從油井輸送到油庫？具體方案如何？從油井輸送到油庫？具體方案如何？ 分析：就輸油管網(wǎng)絡(luò)問題，可用頂點表示油井、油分析：就輸油管網(wǎng)絡(luò)問題，可用頂點表示油井、油庫和中間泵站，用

30、有向邊表示輸油管，用有向邊上庫和中間泵站，用有向邊表示輸油管，用有向邊上的權(quán)表示單位時間沿相應(yīng)的輸油管可以輸送石油的的權(quán)表示單位時間沿相應(yīng)的輸油管可以輸送石油的最大數(shù)量容量）。最大數(shù)量容量）。 第第52頁頁tvsv1234,v v v vtvsv問題的提出問題的提出管道網(wǎng)絡(luò)中每邊的最大通過能力即容量是有限的，實際流管道網(wǎng)絡(luò)中每邊的最大通過能力即容量是有限的，實際流量也不一定等于容量，上述問題就是要討論如何充分利用量也不一定等于容量，上述問題就是要討論如何充分利用裝置的能力，以取得最好效果流量最大），這類問題通裝置的能力，以取得最好效果流量最大），這類問題通常稱為最大流問題。常稱為最大流問題。v

31、sv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第第53頁頁容量容量發(fā)點源）發(fā)點源）收點匯）收點匯）中間點中間點容量網(wǎng)絡(luò)容量網(wǎng)絡(luò)( ,)ijDv v的每條弧上有非負(fù)數(shù)的點的點一個入次為一個入次為0sv的點的點一個出次為一個出次為0tv其余點其余點( , ,)DV A Cijc網(wǎng)絡(luò)有向圖網(wǎng)絡(luò)有向圖D=D=（V V，A A，C C） 網(wǎng)絡(luò)上流的基本概念網(wǎng)絡(luò)上流的基本概念vsv1v3vtv2v48799562510第第54頁頁流流( ,)ijijv vf對D中任一弧都給定一個實際流量ijff 集合集合(1)(2)滿足下面條件的流：容量限制條件中間點平衡

32、條件ijijcf 0 jijkkiff輸出量輸出量中間點的輸入量中間點的輸入量 ( )( )sjjtjjv fstv fff用表示網(wǎng)絡(luò)中從的流量 vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)00f 任何網(wǎng)絡(luò)必存在可行流，如流量為 的可行流：運(yùn)輸問題中，每個運(yùn)運(yùn)輸問題中，每個運(yùn)輸方案就是一個流輸方案就是一個流可行流可行流第第55頁頁 ( )ijfv f在容量網(wǎng)絡(luò)中，尋求一個流使其流量最大網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題ijijcf 0( )0( )ijjiv fffv f( , )tjv vA()is(, )is t()i t且滿足此為一個特殊的

33、線性規(guī)劃問題，將會看到利用圖的特點，此為一個特殊的線性規(guī)劃問題，將會看到利用圖的特點，解決這個問題的方法要比單純形法較為直觀方便。解決這個問題的方法要比單純形法較為直觀方便。第第56頁頁設(shè)設(shè)是網(wǎng)絡(luò)是網(wǎng)絡(luò)D=（V，A，C的一個可行流的一個可行流（v1，v2是飽和的是飽和的2、如果、如果fij0，該弧是非，該弧是非0弧；??；（v1，v2是非是非0弧弧3、如果、如果fij=0，該弧是，該弧是0流弧；流??；弧關(guān)于流的分類弧關(guān)于流的分類ijffv1v2v1v2第第58頁頁割集和割集的容量割集和割集的容量vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)(1

34、11VVVV和11,VvVvts1V1V),(11VV設(shè)有網(wǎng)絡(luò)設(shè)有網(wǎng)絡(luò)D=V，A，C，點，點vs與點與點vt的是集合的是集合V中中的任意兩點，若點集的任意兩點，若點集V被剖分成兩個非空集被剖分成兩個非空集合合，使，使，記以，記以中的點為始點，中的點為始點，的的A A中弧的集合記為中弧的集合記為則稱這個弧的集合是分離點則稱這個弧的集合是分離點vs與點與點vt的割集又稱截集）。的割集又稱截集）。中的點為終點中的點為終點割集的容量是割集中各弧的容量之和，用割集的容量是割集中各弧的容量之和，用 表示。表示。11( ,)c V V1324( ,),(,)v vv v112134 , , tVs v vV

35、v v v割集的容量為割集的容量為9+9=189+9=18割集割集如圖如圖KK割集的意義：若把某一割集的弧從網(wǎng)絡(luò)中丟去，則從割集的意義：若把某一割集的弧從網(wǎng)絡(luò)中丟去，則從vs到到vt便不存便不存路，即割集是從路，即割集是從vs到到vt的必經(jīng)之道！這里的必經(jīng)之道！這里(v3,v2)不屬于此割集不屬于此割集第第59頁頁考慮考慮KK的不同畫法的不同畫法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)1234,v v v v t34(, ),(, )v tvt12( ,),( ,)s vs v1 , s v s2 ,s v12 ,s v v13 ,s

36、v v24 ,s v v123 ,s v v v124 ,s v v v1234 ,s v v v v234,v v v t134,v v v t134,v v v t24,v v t13,v v t1234,v v v v t4,v t t21213( ,),(,),(,)s vv vv v124( ,),(,)s vvv1324(,),(,)v vvv212323( ,),(,),(,),(, )s vv vv vv t1434( ,),(,),(, )s vvvvt243(,),(, )vvv t13434(,),(,),(, )v vvvvt152117181924142515VV割集

37、割集割集容量割集容量由于有限網(wǎng)絡(luò)的割集只有有限多個，則截集容量的集由于有限網(wǎng)絡(luò)的割集只有有限多個，則截集容量的集合合是有限的實數(shù)集合，令是有限的實數(shù)集合，令稱割集容量為稱割集容量為C0的割集為的割集為D的最小截集。的最小截集。11(,)C V V011 ( ,)Cmin C V V第第60頁頁111111( , ,),( ),( ,),( ,)( )( ,)ststfDV A CvvW fV Vv vV VW fC V V設(shè) 為網(wǎng)絡(luò)的任一可行流( 為發(fā)點為收點），流量為是分離的任一割集，割集容量為C則有基本定理基本定理(可行流與割集的關(guān)系可行流與割集的關(guān)系)割集的意義：若把某一割集的弧從網(wǎng)絡(luò)中

38、丟去，則從割集的意義：若把某一割集的弧從網(wǎng)絡(luò)中丟去，則從vs到到vt便不存便不存路，即割集是從路，即割集是從vs到到vt的必經(jīng)之道！的必經(jīng)之道！最大流最大流-最小割定理：最小割定理：的最小割的容量的最小割的容量分離分離的最大流的流量的最大流的流量到到從從中，中，任一個網(wǎng)絡(luò)任一個網(wǎng)絡(luò)tstsvvvvG, 的的可可增增廣廣鏈鏈到到不不存存在在從從是是最最大大流流可可行行流流tsvvf第第61頁頁鏈及可增廣鏈鏈及可增廣鏈鏈鏈在最大流問題中，研究的是有向網(wǎng)絡(luò)圖。在最大流問題中，研究的是有向網(wǎng)絡(luò)圖。但是在求最大流的方法中，則要使用無向但是在求最大流的方法中，則要使用無向網(wǎng)絡(luò)中的鏈。這時，就要將它看成無向

39、網(wǎng)網(wǎng)絡(luò)中的鏈。這時，就要將它看成無向網(wǎng)絡(luò)圖，即將網(wǎng)絡(luò)中的弧看成邊。那么，以絡(luò)圖，即將網(wǎng)絡(luò)中的弧看成邊。那么，以發(fā)點發(fā)點vsvs為始點、以收點為始點、以收點vtvt為終點的點、邊為終點的點、邊交錯序列即無向圖中的鏈稱為連接點交錯序列即無向圖中的鏈稱為連接點vsvs、vtvt的鏈，并用其頂點序列來表示。的鏈，并用其頂點序列來表示。第第62頁頁( ,)( ,)ijijijijijfv vffv vf非增廣鏈上的弧(,)(,)min0ijijijijijijijcfv vfv v()( )v fv f,ststvvvvD中，若 為從 到 的一條鏈，給 定向為從 到前向弧集 ：與 同向后向弧集 ：與 反

40、向，11fc30f 10nf22fcnnfc0( ,)0( ,)ijijijijijijstffcv vfcv vvv 是可行流，若則稱 為從 到 的可增廣鏈。非飽和弧非飽和弧非非0流弧流弧可增廣鏈可增廣鏈第第63頁頁這樣就得到了一個尋求最大流的方法這樣就得到了一個尋求最大流的方法(算法思想算法思想)：從一個可行流開始，尋求關(guān)于這個可行流的可增從一個可行流開始，尋求關(guān)于這個可行流的可增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個新的廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個新的可行流，其流量比原來的可行流要大，重復(fù)這個可行流，其流量比原來的可行流要大，重復(fù)這個過程，直到不存在關(guān)于該流的可增廣鏈時過程，直

41、到不存在關(guān)于該流的可增廣鏈時就得到了最大流。就得到了最大流。沿著這條鏈從沿著這條鏈從 vs vs 到到 vt vt 輸送流，還有潛力可挖，輸送流，還有潛力可挖，只需按照調(diào)整方法，就可以把流量提高，調(diào)整后只需按照調(diào)整方法，就可以把流量提高，調(diào)整后的流，在各點仍滿足平衡條件及容量限制條件，的流，在各點仍滿足平衡條件及容量限制條件，即仍為可行流。即仍為可行流?？稍鰪V鏈的實際意義可增廣鏈的實際意義第第64頁頁求解最大流的標(biāo)號算法：求解最大流的標(biāo)號算法：1.()1( ,)2,:( ),min,(,)( )0,min,(,)(3)(2siijjiijijjijijiijjijijjiiijvvvvavvf

42、ccfvbvvffv 標(biāo)號過程 尋找可增廣鏈 ：（ ）給 以標(biāo)號（ ）對已標(biāo)號的對于 的所有未標(biāo)號的鄰接點若是 發(fā)出的前向非飽和弧的終點， 即令標(biāo)號為；否則不標(biāo)號對是 發(fā)出的后向非零弧的起點， 即令標(biāo)號為；否則不標(biāo)號重復(fù))2.121tstijtijijtijvvvfffff直到 若 未得到標(biāo)號，說明不存在 到 的增廣鏈； 否則按如下方法調(diào)整。調(diào)整過程（增加流量）：增廣鏈上的前向?。?）令增廣鏈上的后向弧不在增廣鏈上（ ）去掉所有標(biāo)號，回到第 步，對可行流重新標(biāo)號。()( )tw fw f則有第第65頁頁1v2v3vb) b) 接著檢查與相鄰接的點接著檢查與相鄰接的點1v3v2v4v5vsvtv

43、6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),( 已飽和，流量不可再增。再檢查已飽和，流量不可再增。再檢查 ，可調(diào)整量為，可調(diào)整量為 4-2=2，可提供量可提供量+，取調(diào)整量，取調(diào)整量1v2v2min42,2 先給標(biāo)號先給標(biāo)號 （，+）1） 尋找可增廣鏈：尋找可增廣鏈：sv第第66頁頁1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),(3v)

44、 1,(sv 下對已標(biāo)號點可望調(diào)整點接著向下檢查。下對已標(biāo)號點可望調(diào)整點接著向下檢查。 已飽已飽 和。再檢查與和。再檢查與 相鄰接且未標(biāo)號的點相鄰接且未標(biāo)號的點 6v2v,5v6v給給 標(biāo)號標(biāo)號 ，其中，其中 表示表示 的所調(diào)整量的所調(diào)整量2來自來自 ，且為正向流向前流）且為正向流向前流） 。)2 ,(svsv2vsv2v)2 ,(sv) 1 ,(sv第第67頁頁調(diào)整量為調(diào)整量為1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(

45、sv5min30, 22)2 ,(2v5v給給 標(biāo)號為標(biāo)號為)2 ,(2v第第68頁頁1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v可令調(diào)整量為可令調(diào)整量為1min3, 22)2 ,(5v給給 標(biāo)號為標(biāo)號為)2 ,(5v1v表示可控量，反方向流量。表示可控量，反方向流量。5v, 015 fd) 檢查與 相鄰接且未標(biāo)號的點 ， 。而 對 來講是流入，現(xiàn)欲增加流出量，應(yīng)壓縮 的流入量，只要的流入量1vtv1v5

46、v1v第第69頁頁1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5vf) 下面檢查與下面檢查與 相鄰接且未標(biāo)號的點相鄰接且未標(biāo)號的點 ，同理，調(diào)整量：，同理，調(diào)整量：1v4v4min52, 22給給 標(biāo)號為標(biāo)號為).2 ,(1v4v)2 ,(1v)2 ,(4vg) 最后，給最后，給 標(biāo)號標(biāo)號tv).2 ,(4vmin42, 22t第第70頁頁1v3v2v4v5vsvtv6v)5 , 5()2 ,

47、3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v2調(diào)整流量：從調(diào)整流量：從 到到 所畫出的紅線即為可增廣鏈。沿所畫出的紅線即為可增廣鏈。沿該可增廣鏈，從該可增廣鏈，從 倒推，標(biāo)倒推，標(biāo)“”號的在實際流量上加上號的在實際流量上加上該調(diào)整量，標(biāo)該調(diào)整量，標(biāo)“”符號的在實際流量上減去該調(diào)整量。完符號的在實際流量上減去該調(diào)整量。完成調(diào)整過程。成調(diào)整過程。svtvtv反反向向追追蹤蹤第第71頁頁1v3v2v4v5vsvtv6v)5

48、, 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v1v3v2v4v5vsvtv6v)5 , 5()2 , 3()4 , 4()4 , 5()4 , 4()4 , 5()3 , 3() 1 , 3()2 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v第第72頁頁1v3v2v4v5vsvtv6v)5 , 5()2 , 3()4 ,

49、 4()4 , 5()4 , 4()4 , 5()3 , 3() 1 , 3()2 , 3()2 , 2()2 , 2(),() 1 ,(sv當(dāng)標(biāo)到當(dāng)標(biāo)到 時，與時，與 ， 相鄰接的點相鄰接的點 ， ， 都不滿足標(biāo)都不滿足標(biāo)號條件，標(biāo)號無法繼續(xù)，且沒有完成標(biāo)號。此時最大流量即號條件，標(biāo)號無法繼續(xù)，且沒有完成標(biāo)號。此時最大流量即為所求。為所求。) 1 ,(svsv3v1v2v6vtv12354211ssswfff312456 ,; ,;stVv vVv v v v v v標(biāo)號點集未標(biāo)號集12361236( , )( , ),( ,),( ,)( , )11ssssV Vv vv vv vC V

50、Vccc割集割集容量重新開始標(biāo)號，尋找可增廣鏈。重新開始標(biāo)號，尋找可增廣鏈。第第73頁頁最小割的意義最小割的意義第第74頁頁tusu1234,u u u utusu解決問題解決問題vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第第75頁頁vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(3)10(8),(vs,2)(-v2,2)(v1,1)(-v3,1)(v4,1)vsv1v3vtv2v48(8)7(6)9(5)9(9)5(5)6(0)2(0)5(3)10(9),(vs,1)(-v2,1)(v1,2)KKW=

51、5+9=14第第76頁頁下圖中，下圖中，A,B,C,D,E,FA,B,C,D,E,F分別表示陸地和島嶼，分別表示陸地和島嶼， 表示橋梁及其表示橋梁及其編號。若河兩岸分別為互為敵對的雙方部隊占領(lǐng)，問至少應(yīng)切斷幾座橋梁編號。若河兩岸分別為互為敵對的雙方部隊占領(lǐng)，問至少應(yīng)切斷幾座橋梁具體指出編號才能達(dá)到阻止對方部隊過河的目的。試用圖論方法進(jìn)行分具體指出編號才能達(dá)到阻止對方部隊過河的目的。試用圖論方法進(jìn)行分析。析。14ABCDEF8911101314127123456最大流問題應(yīng)用舉例最大流問題應(yīng)用舉例第第77頁頁在圖中任給可在圖中任給可行流，用標(biāo)號行流，用標(biāo)號法尋找網(wǎng)絡(luò)最法尋找網(wǎng)絡(luò)最大流！大流！弧容

52、量：兩點間的橋梁數(shù)?；∪萘浚簝牲c間的橋梁數(shù)。ABCDFE122211221122ABCDEF8911101314127123456轉(zhuǎn)化為求網(wǎng)絡(luò)最小割轉(zhuǎn)化為求網(wǎng)絡(luò)最小割第第78頁頁 設(shè)容量網(wǎng)絡(luò)設(shè)容量網(wǎng)絡(luò)G G有若干發(fā)點，若干個點，有若干發(fā)點，若干個點，可以添加兩個新點可以添加兩個新點vsvs，vt vt ，用容量為，用容量為 的有向邊分別連結(jié)的有向邊分別連結(jié)vs vs 與發(fā)點，收點與與發(fā)點，收點與vtvt，得到新的網(wǎng)絡(luò)得到新的網(wǎng)絡(luò)GG，G G 為只有一個發(fā)點，為只有一個發(fā)點，一個收點的網(wǎng)絡(luò)，求解一個收點的網(wǎng)絡(luò)，求解G G 的最大流問題的最大流問題即可得到即可得到G G的解。的解。多發(fā)點多收點網(wǎng)絡(luò)

53、的最大流問題多發(fā)點多收點網(wǎng)絡(luò)的最大流問題最大流問題應(yīng)用舉例最大流問題應(yīng)用舉例第第79頁頁 設(shè)有設(shè)有5位待業(yè)者，位待業(yè)者，5項工作，他們各自能勝任工作項工作，他們各自能勝任工作的情況如圖所示，要求設(shè)計一個就業(yè)方案，使盡的情況如圖所示，要求設(shè)計一個就業(yè)方案，使盡量多的人能就業(yè)。量多的人能就業(yè)。1x2x3x4x5x1y2y3y4y5y其中其中51,xx 表示工人。表示工人。51,yy 表示工作。表示工作。最大匹配問題最大匹配問題第第80頁頁1x2x3x4x5x1y2y3y4y5y圖中最大匹配問題，可以轉(zhuǎn)化為最大流問題求解。在圖中最大匹配問題，可以轉(zhuǎn)化為最大流問題求解。在圖中增加兩個新點圖中增加兩個新

54、點 分別作為發(fā)點，收點。并用分別作為發(fā)點，收點。并用有向邊把它們與原圖中頂點相連，令全部邊上的容量有向邊把它們與原圖中頂點相連，令全部邊上的容量均為均為1。當(dāng)網(wǎng)絡(luò)流達(dá)到最大時，假如。當(dāng)網(wǎng)絡(luò)流達(dá)到最大時，假如 上的流量為上的流量為1，就讓就讓 作作 工作，此即為最大匹配方案。工作，此即為最大匹配方案。svtv,svtv),(jiyxixjy第第81頁頁1x2x3x4x5x1y2y3y4y5ysvtv),() 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 ,(1x) 1 ,(1y第第82頁頁1x2x3x4x5x1

55、y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(4y) 1 , 1 () 1 , 1 () 1 ,(sv) 1 ,(2x)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (第第83頁頁1x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (第第84頁頁1x2x3x4

56、x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(5y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 () 1 ,(3x第第85頁頁1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (

57、)0 , 1 (第第86頁頁1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(2y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(4x) 1 ,(5y) 1 ,(3x) 1 ,(4y)0 , 1 () 1 ,(2x) 1 ,(1y) 1 ,(4x)0 , 1 (第第87頁頁1x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 () 1 , 1 () 1 , 1 ()

58、1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (第第88頁頁1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1

59、() 1 ,(sv)0 , 1 () 1 ,(5x) 1 ,(4y)0 , 1 () 1 ,(3x) 1 ,(5y第第89頁頁1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 ,(2y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(2x) 1 ,(5x) 1 ,(4y)0 , 1 () 1 ,(3x) 1 ,(

60、5y,1x,2x,3x4x,2y,1y,4y5y第第90頁頁第八章第八章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析 最短路問題最短路問題 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題 最小費(fèi)用最大流問題最小費(fèi)用最大流問題 第第91頁頁第八章第八章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析 最短路問題最短路問題 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題 最小費(fèi)用流問題最小費(fèi)用流問題 第第92頁頁最小費(fèi)用流問題最小費(fèi)用流問題 最大流問題僅注意網(wǎng)絡(luò)流的流通能力，沒有考最大流問題僅注意網(wǎng)絡(luò)流的流通能力，沒有考 慮流通的費(fèi)用。慮流通的費(fèi)用。 實際上費(fèi)用因素是很重要的。例如在交通運(yùn)輸實際上費(fèi)用因素是很重要的。例如在交通運(yùn)輸 問題中，往往要求在完成運(yùn)輸任務(wù)的前提下，問題