第四節(jié) 最大流問題

1、1 第第4節(jié)節(jié) 網(wǎng)絡最大流問題網(wǎng)絡最大流問題例例 連接某產(chǎn)品產(chǎn)地連接某產(chǎn)品產(chǎn)地vs和銷地和銷地vt的交通網(wǎng)如下：的交通網(wǎng)如下：v1v4115v2vsv3vt325224?。ɑ。╲i，vj）：從）：從vi到到vj的運輸線，的運輸線，弧旁數(shù)字：這條運輸線的最大通過能力弧旁數(shù)字：這條運輸線的最大通過能力,制定一個運輸方案，使從制定一個運輸方案，使從vs到到vt的產(chǎn)品數(shù)量最多。的產(chǎn)品數(shù)量最多。2弧旁數(shù)字：弧旁數(shù)字：運輸能力。運輸能力。問題：這個運輸網(wǎng)絡中，從問題：這個運輸網(wǎng)絡中，從vs到到vt的最大輸送量是多少？的最大輸送量是多少？v1v4115v2vsv3vt32522437.4.1最大流的基本概念

2、與定理最大流的基本概念與定理（1）. 網(wǎng)絡流網(wǎng)絡流網(wǎng)絡流網(wǎng)絡流 對于網(wǎng)絡G=（V，A，C） ，定義在弧集合A上的 一個函數(shù)f = f(vi ,vj) 稱為網(wǎng)絡流， f(vi , vj) （簡稱fij）為弧aij A上的流。 容量容量：在有向圖上，每條弧上給出的最大通過能力（最大可能負載）。cij流量流量：網(wǎng)絡中加在弧上的負載量（實際負載量）。 fij4弧旁數(shù)字：弧旁數(shù)字： 容量容量(a)圖是一個網(wǎng)絡圖是一個網(wǎng)絡v2v5348v3v1v4v65106111735v2v5313v3v1v4v61536222弧旁數(shù)字：弧旁數(shù)字： 流量流量5 cij fijvivjv2v5(3,3)(4,1)(8,3

3、)v3v1v4v6(5,1)(10,5)(6,3)(11,6)(17 ,2)(3,2)(5 ,2)6（2）. 可行流可行流可行流可行流 滿足下述條件的流 f 稱為可行流:1)容量限制條件: 對每一弧(vi , vj )A 0fij cij2)平衡條件: 對中間點vi (is,t ),有 (,)(,) 0ijjiijjiv vAvvAff)V( : A),(A),(fffvsjjsvvjsvvsjs )V( : A),(A),(fffvtjjtvvjtvvtjt V( f ) 稱為可行流 f 的流量,即發(fā)點的凈輸出量。如所有如所有fij=0， 零流。零流?？尚辛骺偸强尚辛骺偸谴嬖诘拇嬖诘?（3）

4、. 最大流最大流 若若 V（f *） 為網(wǎng)絡可行流，且滿足：為網(wǎng)絡可行流，且滿足： V（f *）=MaxV（f ） f 為網(wǎng)絡為網(wǎng)絡D中的任意中的任意 一個可行流，則稱一個可行流，則稱f *為網(wǎng)絡的為網(wǎng)絡的最大流最大流。（4）.前向弧與后向弧前向弧與后向弧 設設=（x,u，v,A）是網(wǎng)絡）是網(wǎng)絡G中的一條初等鏈并且中的一條初等鏈并且定義鏈的方向是從定義鏈的方向是從x到到A。若。若D中有?。ㄖ杏谢。╱，v），與），與方向方向一致，則稱（一致，則稱（u，v）為鏈）為鏈的的前向弧前向弧，若，若D中有?。ㄖ杏谢。╱，v），與），與方向相反方向相反,則稱（則稱（v, u），為鏈），為鏈的的后向弧后向弧。

5、8（5）. 增廣鏈增廣鏈對可行流 f = fij ：非飽和?。篺ij 0零流弧：fij =0 鏈的方向：若是聯(lián)結(jié)vs和vt的一條鏈，定義鏈的方向是從vs到vt 。 v2v5(3,3)(4,1)(8,3)v3v1v4v6(5,1)(10,5)(6,3)(11,6)(17 ,2)(3,2)(5 ,2)9 = (v1,v2,v3,v4,v5,v6 )+=(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6) - =(v4,v5)v2v5(3,3)(4,1)(8,3)v3v1v4v6(5,1)(10,5)(6,3)(11,6)(17,2)(3,2)(5,2)10增廣增廣 鏈鏈 設 f

6、是一個可行流, 是從vs 到vt 的一條鏈,若滿 足下列條件,稱之為關于可行流 f 的一條增廣 鏈。(vi , vj ) - 0 fij cij 后向弧 是非零流弧，(vi , vj ) + 0 fij cij 前向弧是 非飽和弧，v1v2v3v4v5v6(8,4)(6,0)(6,5)(3,3)(5,4)11（6）. 截集與截量截集與截量 對于有向網(wǎng)絡對于有向網(wǎng)絡G=(V,A,C） ，若，若S為為V的子集，的子集， ，則稱弧集則稱弧集 為網(wǎng)絡為網(wǎng)絡G的一個截集，并將截集中所有弧容量之和稱為截容量，的一個截集，并將截集中所有弧容量之和稱為截容量，即即 為截集為截集 的的截容量截容量（簡稱為截量）

7、。（簡稱為截量）。(SS)= a|a=(u,v),uS,vS，aS, SC S, SC a（）（）=（ ）（7）最小截與最小截量）最小截與最小截量 S=V - S(S,S ) 若若 是容量網(wǎng)絡中所有截集中截量最小的截集，即是容量網(wǎng)絡中所有截集中截量最小的截集，即 則稱則稱 為為G上的上的最小截最小截， 為上的為上的最小截量最小截量。minC S* S*C S SS SG（,）=（ , ）|（ , ）為網(wǎng)絡 的一個截量S*S*（，）C S* S*（,）S*S*（，）12 性質(zhì)性質(zhì) 任何一個可行流的流量任何一個可行流的流量V(f)都不會超過任一截集的容都不會超過任一截集的容量。即量。即11 ( )

8、( ,)V fC V V可行流可行流f*，截集，截集(V1*，V1*), 若若V(f*)=C( V1*，V1*），），則則f*必是最大流，必是最大流， (V1*，V1*) 必是必是D的最小截集。的最小截集。定理定理 若若f*是網(wǎng)絡是網(wǎng)絡G=（V，A，C）上的可行流，則）上的可行流，則 可行流可行流f*為最大的充要條件為為最大的充要條件為中不存在關中不存在關 于于f*的增廣鏈。的增廣鏈。 最大流最小截量定理。任一個網(wǎng)絡最大流最小截量定理。任一個網(wǎng)絡D中，從中，從vs 到到 vt的最的最大流的流量等于分離大流的流量等于分離vs，vt的最小截集的容量。的最小截集的容量。137.4.2尋求最大流的標號

9、法（尋求最大流的標號法（FordFulkerson） 從任一個可行流從任一個可行流 f 出發(fā)（若網(wǎng)絡中沒有給定出發(fā)（若網(wǎng)絡中沒有給定 f ，則從零流開始），經(jīng)過標號過程與調(diào)整過程。則從零流開始），經(jīng)過標號過程與調(diào)整過程。（一）標號過程（一）標號過程 未未標標號號點點未未檢檢查查已已檢檢查查標標號號點點網(wǎng)網(wǎng)絡絡中中的的點點14標號：標號： 開始，開始，vs 標上（標上（0，），），vs 是標號未檢查的點，是標號未檢查的點，其余點都是未標號點，一般地，取一個標號未檢查其余點都是未標號點，一般地，取一個標號未檢查的點的點vi ，對一切未標號的點，對一切未標號的點vj 。（1）若弧（）若弧（vi，vj

10、）上，）上，fij0，則給，則給vj 標號標號(-i， l (vj)，l (vj)=minl (vi), fji, vj 成為標號而未檢查的點。成為標號而未檢查的點。fij0vivj(-i , l(vj)l(vj)=minl(vi),fji15 重復上述步驟，一旦重復上述步驟，一旦vt被標號，則得到一條被標號，則得到一條vs到到vt的的增廣鏈。若所有標號都已檢查過，而增廣鏈。若所有標號都已檢查過，而vt尚未標號，結(jié)束，尚未標號，結(jié)束，這時可行流，即最大流。這時可行流，即最大流。（二）調(diào)整過程（二）調(diào)整過程 從從vt 開始，反向追蹤，找出增廣鏈開始，反向追蹤，找出增廣鏈 ，并在，并在上進上進行流

11、量調(diào)整。行流量調(diào)整。（1）找增廣鏈）找增廣鏈 如如vt 的第一個標號為的第一個標號為k（或或-k），），則?。▌t?。╲k，vt）（或?。ɑ蚧。╲t，vk) )。檢查。檢查vk 的第一個標號，若為的第一個標號，若為i（或（或-i），則），則(vi,vk) (或或(vk,vi) )。再檢查。再檢查vi 的第一的第一個標號個標號,依此下去依此下去,直到直到vs 。被找出的弧構(gòu)成了增廣鏈。被找出的弧構(gòu)成了增廣鏈 。16（2）流量調(diào)整）流量調(diào)整令調(diào)整量令調(diào)整量 是是 l(vt)，構(gòu)造新的可行流，構(gòu)造新的可行流 f ，令令 uvv fuvvfuvvffjiijjiijjiijij ),( ),( ),(

12、- 去掉所有的標號去掉所有的標號,對新的可行流對新的可行流 f = fij,重新進重新進入標號過程。入標號過程。17例例 用標號法求下圖網(wǎng)絡的最大流?；∨缘臄?shù)字是用標號法求下圖網(wǎng)絡的最大流?；∨缘臄?shù)字是( cij , fij)。解：（一）標號過程。解：（一）標號過程。（1）給）給vs標上（標上（0，）；）；v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，） 415minmin111 ,)fc(),v( l)v( lsss在弧（在?。╲s，v2）上，）上， fs2=cs2=3, 不滿足標號條件不滿足標號條件。（2）檢查）檢查

13、vs，在弧（，在?。╲s，v1）上，）上，fs1=1，cs1=5， fs10， 給給v2標號標號 (-1, l l(v2), ,f),v( l)v( l114minmin2112 在弧（在?。╲1，v3）上，）上，f13=2， c13=2，不滿足標號條件。，不滿足標號條件。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（vs，4）（-v1，1）（4）檢查）檢查v2，在?。ǎ诨。╲3，v2）上，）上，f32=10， 給給v3標號標號 (-2, l(v3), 這里這里 , 11 , 1min),(min)(3223fvl

14、vl（-v2，1）19在?。ㄔ诨。╲2，v4）上，）上，f24=3，c24=4，f24c24, 給給v4標號標號(2, l(v4), 其中其中 ,min)fc(),v( l)v( l111min242424 （5）檢查）檢查v3，在弧（，在弧（v3，vt）上，）上，f3t=1， c3t=2， f3tc3t， 給給vt標號標號 (3, l(vt), 這里這里 ,min)fc(),v( lmin)v( lttt111333 vt得到標號，標號過程結(jié)束。得到標號，標號過程結(jié)束。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0,）（

15、vs，4）（-v1,1）（-v2,1）(v2，1)(v3，1)20（二）調(diào)整過程（二）調(diào)整過程 ：從：從vt 開始逆向追蹤，找到增廣鏈。開始逆向追蹤，找到增廣鏈。（vs,v1,v2,v3,vt） =1，在在上進行流量上進行流量 =1的調(diào)整，得的調(diào)整，得可行流可行流 f 如右如右圖所示：圖所示：v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0,）（vs，4）（-v1,1）（-v2,1）(v2，1)(v3，1)v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)21去

16、掉各點標號，從去掉各點標號，從vs開始，重新標號。開始，重新標號。點點v1：標號過程：標號過程無法進行，所以無法進行，所以f 即為最大流。即為最大流。V（f ）=3+2=5v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（0，）（vs，3）截集：截集：V1，V1=（vs，v2），（），（v1，v3） V（f ）=CV1，V1=5V1=(vs,v1) V1=(v2,v3,v4, vt)問題：問題：(v2,v1)是不是截集是不是截集V1，V1中的弧？中的弧？22例例 用標號法求下圖網(wǎng)絡的最大流。弧旁的數(shù)字是用標號法求下圖網(wǎng)絡的最大流

17、?；∨缘臄?shù)字是( cij , fij)。v1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)vt23解：解： 第一輪第一輪 標號過程標號過程（1）vs標（標（0，+），），vs為已標號未檢查點。為已標號未檢查點。（2）檢查）檢查vs，給，給v2標號（標號（vs，l(v2)） ，vs成為已標號已檢查的點，成為已標號已檢查的點，v2成為已標號未檢查的點。成為已標號未檢查的點。（3）檢查）檢查v2，給，給v1標號（標號（-v2，l(v1)） 。同理給。同理給v4標號為（標號為（v2，1），），v2成為已標號已檢查的成為已標號已檢查的 點，點，

18、v1，v4成為已標號未檢查的點。成為已標號未檢查的點。（4）檢查）檢查v1，給，給v3標號為（標號為（v1，2），），v3成為已標號未檢成為已標號未檢 查的點。查的點。（5）檢查）檢查v3，給，給vt標號為（標號為（ v3 ，2）。）。 因為因為vt已被標號，所以說明找到一條增廣鏈。已被標號，所以說明找到一條增廣鏈。 調(diào)整過程調(diào)整過程 按點的第一個標號，以按點的第一個標號，以vt點開始，回溯找到一條增廣點開始，回溯找到一條增廣 鏈，鏈， 如下圖紅線所示：如下圖紅線所示：2)min6-24l v (，1)min 42l v(，224vt(0， +)（vs，4）（-v2，2）（v2，1）（v1，2

19、）（v3，2）v1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)2522sstvv fvvl v（ ， ） ： （ ， ）=2+（ ）=2+2=4vtv1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)在增廣鏈上進行了流量調(diào)整。在增廣鏈上進行了流量調(diào)整。前向弧前向弧 后向弧后向弧 1313tvv fvvl v（ ， ） ： （ ， ）=1+（ ）=1+2=333tttvv fvvl v（ ， ） ： （ ， ）=3+（ ）=3+2=51212tvv fvvl v（ ， ） ：

20、（ ， ）=2-（ ）=2-2=0于是調(diào)整后流量如下圖所示。于是調(diào)整后流量如下圖所示。(0， +)（vs，4）（-v2，2）（v2，1）（v1，2）（v3，2）26v1v4v2vsv3(3，3)(5，3)(2，0)(6，4)(3，2)(2，2)(2,0)(6，5)(5，2)vt27 第二輪：第二輪： 標號過程標號過程（1）vs標（標（0，+），），vs為已標號未檢查點。為已標號未檢查點。（2）檢查）檢查vs，給，給v2標號（標號（vs，2），），v2成為已標號未檢查成為已標號未檢查 的點。的點。（3）檢查）檢查v2 ，給，給v4標號（標號（ v2 ，1），）， v4成為已標號未檢成為已標號未檢 查的點。查的點。（4）檢查）檢查v4 ，給，給vt標號為（標號為（ v4 ，1），）， vt被標，轉(zhuǎn)入下被標，轉(zhuǎn)入下 一階段。一階段。 調(diào)整過程調(diào)整過程 根據(jù)標號過程，以根據(jù)標號過程，以vt點開始，回溯找到一條增廣鏈，如點開始，回溯找到一條增廣鏈，如 下圖紅線所示。下圖紅線所示。2