第4節(jié) 網絡最大流問題

1、公路系統(tǒng)中的車輛流公路系統(tǒng)中的車輛流 控制系統(tǒng)中的信息流控制系統(tǒng)中的信息流 供水系統(tǒng)中的水流供水系統(tǒng)中的水流 金融系統(tǒng)中的現金流金融系統(tǒng)中的現金流 問題背景問題背景 網絡最大流問題問題的提出 n網絡中存在流量限制時，求解一條線路使網絡中存在流量限制時，求解一條線路使 得從得從起點起點與與終點終點之間可通過的之間可通過的流量最大流量最大。 v1 v2 v3 v4 v5 v6 10 8 4 6 5 3 5 3 11 17 例：上圖為例：上圖為v1到到v6的一交通網，權表示相應運輸線的最大的一交通網，權表示相應運輸線的最大 通過能力，制定一方案，使從通過能力，制定一方案，使從v1運到運到v6的運輸產

2、品數量最的運輸產品數量最 多。多。 設有網絡設有網絡d=(v, a, c)，其中，其中c=cij， cij為弧為弧(vi,vj) 上的上的容量容量，現在，現在d上要通過一個流上要通過一個流f=fij， fij為弧為弧 (vi,vj)上的上的流量流量。 問題：問題：如何安排如何安排fij，可使網絡，可使網絡d上的總流量最大？上的總流量最大？ v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 一、一般提法：一、一般提法： max v=v（f） ijij cf 0 tsi tifv sifv ff jj jiij ,0 )( )

3、( 容量約束容量約束 平衡約束平衡約束 s.t. v2 vs v3 v4 v5 vt 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 注：滿足兩約束條件的流注：滿足兩約束條件的流f稱為可行流，稱為可行流，v(f)稱為該可行流的流量稱為該可行流的流量 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 1 1 3 3 6 2 飽和弧飽和弧 fij=cij 非飽和弧非飽和弧 fijcij 零流弧零流弧 fij=0 非零流弧非零流弧 fij0 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11

4、6 3 5 3 1 2 2 1 3 3 6 2 f為一可行流，為一可行流，u為為vs至至vt的鏈，令的鏈，令 u+=正向弧正向弧， u-=反向弧反向弧。若。若u+中弧中弧 皆非飽和皆非飽和，且，且u-中弧皆非零，則稱中弧皆非零，則稱u為關于為關于f 的一條的一條增廣鏈增廣鏈。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 f為一可行流，為一可行流，u為為vs至至vt的鏈，令的鏈，令 u+=正向弧正向弧， u-=反向弧反向弧。若。若u+中弧中弧 皆非飽，且皆非飽，且u-中弧皆非零，則稱中弧皆非零，則稱u為關于為關于f的的

5、 一條一條增廣鏈增廣鏈。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 f為一可行流，為一可行流，u為為vs至至vt的鏈，令的鏈，令 u+=正向弧正向弧， u-=反向弧反向弧。若。若u+中弧中弧 皆非飽，且皆非飽，且u-中弧皆非零，則稱中弧皆非零，則稱u為關于為關于f的的 一條一條增廣鏈增廣鏈。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 1 f為一可行流，為一可行流，u為為vs至至vt的鏈，令的鏈，令 u+=正向弧正向弧， u-=反向弧反向弧。

6、若。若u+中弧中弧 皆非飽，且皆非飽，且u-中弧皆非零，則稱中弧皆非零，則稱u為關于為關于f的的 一條一條增廣鏈增廣鏈。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 3 2 0 1 5 3 6 2 把把v分成兩部分：分成兩部分：va和和vb(va vb= , va vb= v) 且且vs va、 vt vb，則弧集，則弧集(va,vb)稱為稱為d的的截集（割集）截集（割集）。 截集上的容量截集上的容量和稱為和稱為截量（割集容量），記為截量（割集容量），記為c(va,vb) 。 v1 vs v2 v3 v4 vt 8 10 4 17 5 5 3 11

7、 6 3 5 3 1 2 2 1 3 3 6 2 (vs,v2), (v1,v2), (v1,v3), (v1,v4)； 截量為：截量為： c(va,vb) =8+4+5+3=20 例例 若若va=vs,v1，則，則 截集為：截集為： 任一可行流的流量都不會超過任一截集的截量任一可行流的流量都不會超過任一截集的截量 即：即：v(f) c (va,vb) 。 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） 最大流最小截定理：最大流最小截定理：網絡的最大流量等于最小截量。網絡的最大流量等于最小截量。 (cijfij) v1 vs v2

8、v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） va=vs， (vs,v1), (vs,v2)，截量為：，截量為：6 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） va=vs，(vs,v1), (vs,v2)，截量為：，截量為：6 va=vs ,v1，(vs,v2), (v1,vt)，截量為：，截量為：7 v1 vs v2v3 vt （2，2） （4，3） （3，1） （

9、1，0） （3，3） （5，2） （2，2） va=vs，(vs,v1), (vs,v2)，截量為：，截量為：6 va=vs ,v1，(vs,v2), (v1,vt)，截量為：，截量為：7 va=vs ,v2，截量為：，截量為：7 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） va=vs，(vs,v1), (vs,v2)，截量為：，截量為：6 va=vs ,v1，(vs,v2), (v1,vt)，截量為：，截量為：7 va=vs ,v2，截量為：，截量為：7 va=vs ,v3，截量為：，截量為：12 v1 vs v2v3 vt

10、 （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） va=vs，(vs,v1), (vs,v2)，截量為：，截量為：6 va=vs ,v1，(vs,v2), (v1,vt)，截量為：，截量為：7 va=vs ,v2，截量為：，截量為：7 va=vs ,v3，截量為：，截量為：12 va=vs ,v1,v2，截量為：，截量為：5 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） （1）所有的截集：）所有的截集： va=vs，(vs,v1), (vs,v2)，截量為：，截量為：6 va=vs ,v1，(

11、vs,v2), (v1,vt)，截量為：，截量為：7 va=vs ,v2，截量為：，截量為：7 va=vs ,v3，截量為：，截量為：12 va=vs ,v1,v2，截量為：，截量為：5 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） （2）最小截量最小截量min c (va,vb)= 5； （3）v(f*)=5= min c (va,vb) f*是最大流。是最大流。 理論依據：理論依據：p261,p261,推論推論 不存在關于不存在關于f的增廣鏈的增廣鏈可行流可行流f是最大流是最大流 網絡中的所有點：網絡中的所有點：標號點和未標

12、號點。標號點和未標號點。 標號點：標號點：已檢查和未檢查點。已檢查和未檢查點。 標號點包括兩部分標號點包括兩部分：第一個標號表明它的標第一個標號表明它的標 號的來源，以便找出增廣鏈；第二個標號是號的來源，以便找出增廣鏈；第二個標號是 為確定增廣鏈的調整量。為確定增廣鏈的調整量。 標號法的思路 所有點所有點 未標號未標號 未檢查未檢查 所有所有 標號點標號點 檢查檢查 注注: 給發(fā)點給發(fā)點vs標上（標上（0，），則），則vs成為標號未檢查成為標號未檢查 vi 標號標號 未檢查未檢查 vi 標號標號 檢查檢查 vj 標號標號 未檢查未檢查 考查考查 （vi, vj) 網絡最大流問題網絡最大流問題標

13、號法標號法 1.標號過程標號過程 n給vs標上(0，+)，這時vs是標號而未檢查點，其余為 未標號點。 n若在弧(vi，vj)上，fij0，則給vj標(-vi，l(vj)， 其中 n于是于是vi成為標號而已檢查過的點，重復上述步驟，成為標號而已檢查過的點，重復上述步驟， 一旦一旦vt被標號，表明得到一條從被標號，表明得到一條從vs到到vt的增廣鏈，轉入的增廣鏈，轉入 2.調整過程調整過程 n如果所有標號已檢查過，而標號不能進行下去，則算法如果所有標號已檢查過，而標號不能進行下去，則算法 結束，這時可行流為最大流。結束，這時可行流為最大流。 min, jiijij l vl vcf min, j

14、iji l vl vf 網絡最大流問題標號法 n1.標號過程標號過程 n2.調整過程調整過程 * * * , , , ij ij ijijijt ij ij v v f ffv vl v f v v 利用反向追蹤法找出增廣鏈。調整量為利用反向追蹤法找出增廣鏈。調整量為 = l(vt) 去掉所有的標號，對新的可行流去掉所有的標號，對新的可行流f*重新進行標號過程。重新進行標號過程。 步驟：步驟： (1)給給vs標號為標號為0,+， 流出未飽和弧流出未飽和弧(vs , vj) ,給給vj標號標號vs ,j,其中其中j=csj- fsj 或或流入非零弧流入非零弧 (vj , vs) ,給給vj標號標

15、號-vs, j ,其中其中j=fsj (cijfij)，用標號法求最大流。，用標號法求最大流。 0,+ vs, 4 選與選與vs關聯的關聯的 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） （3,0） (2)把節(jié)點集把節(jié)點集v分為分為 va：已標號點集：已標號點集 vb：未標號點集：未標號點集 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0 , + vs, 4 （3,0） 考慮所有弧考慮所有弧(vi , vj)或或(vj ,

16、 vi) ,其中其中vi va, vj vb，若該弧為，若該弧為 流出未飽弧流出未飽弧,則給則給vj標號標號vi , j,其中其中j=mini, cij- fij 流入非零弧流入非零弧,則給則給vj標號標號-vi , j ,其中其中j= mini, fij (3) -v1 , 1 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0 , + vs , 4 （3,0） (4) v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0 ,

17、+ vs , 4 -v1 , 1 重復（重復（2）,（3），依次進行的結局可能為），依次進行的結局可能為 vt已標號，得到一條增廣鏈已標號，得到一條增廣鏈u(反向追蹤反向追蹤)，轉（，轉（5）；）； vt未標號未標號,且無法再標號且無法再標號,此時的流為此時的流為最大流最大流,此時的截集此時的截集為為最小截最小截。 （3,0） v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0 , + vs, 4 -v1, 1 (4) 重復（重復（2）,（3），依次進行的結局可能為），依次進行的結局可能為 vt已標號，得到一條

18、增廣鏈已標號，得到一條增廣鏈u(反向追蹤反向追蹤)，轉（，轉（5）；）； vt未標號未標號,且無法再標號且無法再標號,此時的流為此時的流為最大流最大流,此時的截集此時的截集為為最小截最小截。 v2 , 1 （3,0） v3 (4) 重復（重復（2）,（3），依次進行的結局可能為），依次進行的結局可能為 vt已標號，得到一條增廣鏈已標號，得到一條增廣鏈u(反向追蹤反向追蹤)，轉（，轉（5）；）； vt未標號未標號,且無法再標號且無法再標號,此時的流為此時的流為最大流最大流,此時的截集此時的截集為為最小截最小截。 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2）

19、（1,1） （5,3） （2,1） （4,3） 0, + vs, 4 -v1, 1v2, 1 （3,0） v4, 1 (4) 重復（重復（2）,（3），依次進行的結局可能為），依次進行的結局可能為 vt已標號，得到一條增廣鏈已標號，得到一條增廣鏈u(反向追蹤反向追蹤)，轉（，轉（5）；）； vt未標號未標號,且無法再標號且無法再標號,此時的流為此時的流為最大流最大流,此時的截集此時的截集為為最小截最小截。 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0, + vs, 4 -v1, 1v2 , 1 （3,0）

20、 v4 , 1 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0, + vs, 4 -v1, 1v2, 1 （3,0） -v2, 1 v4 , 1 (5) 調整。取調整。取( ) min j tj vu l v ，令，令 uvvf uvvf uvvf f jiij jiij jiij ij ),( ),( ),( ，得新流，得新流 ij f,轉轉(1)。 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0, + vs, 4 -

21、v1, 1-v2, 1 （3,0） -v2, 1 v4, 1 v2 vs v1 v4 v3 vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） 調整調整 v2 vs v1 v4 v3 vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） 0 ,+ vs, 3 v2 vs v1 v4 v3 vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） 0, + vs , 3 此時標號無法進行，當前流為最大流，最大流量為此時標

22、號無法進行，當前流為最大流，最大流量為5； 最小截為最小截為(vs,v2), (v1,v3)，截量為：，截量為：5 有三個發(fā)電站有三個發(fā)電站v1,v2,v3，發(fā)電能力分別為，發(fā)電能力分別為15、10和和 40兆瓦，經輸電網可把電力送到兆瓦，經輸電網可把電力送到8號地區(qū)，電網能力如號地區(qū)，電網能力如 圖所示。求三個發(fā)電站輸到該地區(qū)的最大電力。圖所示。求三個發(fā)電站輸到該地區(qū)的最大電力。 v2 v1 v3 v4 v5 v6 v7 v8 40 15 30 15 45 10 15 10 20 v0 10 15 40 10 10 15 15 15 0 10 10 10 10 15 25 課堂練習課堂練習

23、例例1、圖中圖中a、b、c、d、e、f分別表示陸地和島嶼，分別表示陸地和島嶼， 表示橋梁及其編號。河兩岸分別互為敵對的雙表示橋梁及其編號。河兩岸分別互為敵對的雙 方部隊占領，問至少應切斷幾座橋梁（具體指出編號）才方部隊占領，問至少應切斷幾座橋梁（具體指出編號）才 能達到阻止對方部隊過河的目的。試用圖論方法進行分析。能達到阻止對方部隊過河的目的。試用圖論方法進行分析。 a b d e f c 實際應用實際應用 分析：轉化為一分析：轉化為一 個網絡圖，弧的個網絡圖，弧的 容量為兩點間的容量為兩點間的 橋梁數。橋梁數。 則問題為求最則問題為求最 小截。小截。 a b d e f c a b c d

24、e f 2 1 1 1 1 1 2 2 2 2 2 2 分析：轉化為一分析：轉化為一 個網絡圖，弧的個網絡圖，弧的 容量為兩點間的容量為兩點間的 橋梁數。橋梁數。 則問題為求最則問題為求最 小截。小截。 答案：答案：最小截為最小截為ae、 cd、cf a b d e f c a b c d e f 2 1 1 1 1 1 2 2 2 2 2 2 例例2、有一批人從我國有一批人從我國a城赴俄羅斯城赴俄羅斯b城，可能的旅城，可能的旅 行路線如圖：行路線如圖： 邊防隊擬建立足夠數量檢查站以便使每輛汽車至少邊防隊擬建立足夠數量檢查站以便使每輛汽車至少 必經過一個檢查站，建立檢查站的費用根據各路段條必經過一個檢查站，建立檢查站的費用根據各路段條 件有所不同（如圖數字所示），