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

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

對(duì)于網(wǎng)絡(luò)G=（V，A，C），定義在弧集合A上的一個(gè)函數(shù)f={f(vi

,vj)}稱為網(wǎng)絡(luò)流，f(vi

,vj)（簡(jiǎn)稱fij）為弧aij∈A上的流。

容量：在有向圖上，每條弧上給出的最大通過能力（最大可能負(fù)載）。cij流量：網(wǎng)絡(luò)中加在弧上的負(fù)載量（實(shí)際負(fù)載量）。fij3弧旁數(shù)字：

容量(a)圖是一個(gè)網(wǎng)絡(luò)v2v5348v3v1v4v65106111735v2v5313v3v1v4v61536222弧旁數(shù)字：

流量4

cij

fijvivjv2v5(3,3)(4,1)(8,3)v3v1v4v6(5,1)(10,5)(6,3)(11,6)(17,2)(3,2)(5,2)5（2）.可行流可行流

滿足下述條件的流f稱為可行流:1)容量限制條件:對(duì)每一弧(vi,vj)∈A0≤fij≤cij2)平衡條件:對(duì)中間點(diǎn)vi(i≠s,t),有V(f)稱為可行流f的流量,即發(fā)點(diǎn)的凈輸出量。如所有fij=0，零流?？尚辛骺偸谴嬖诘?（3）.最大流

若V（f*）為網(wǎng)絡(luò)可行流，且滿足：V（f*）=Max{V（f）∣f}為網(wǎng)絡(luò)D中的任意一個(gè)可行流，則稱f*為網(wǎng)絡(luò)的最大流。（4）.前向弧與后向弧

設(shè)μ=（x,…,u，v,…A）是網(wǎng)絡(luò)G中的一條初等鏈并且定義鏈的方向是從x到A。若D中有?。╱，v），與μ方向一致，則稱（u，v）為鏈μ的前向弧，若D中有?。╱，v），與μ方向相反,則稱（v,u），為鏈μ的后向弧。7（5）.增廣鏈對(duì)可行流f={fij}：非飽和?。篺ij<cij飽和弧：fij=cij非零流?。篺ij>0零流?。篺ij=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)8μ=(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)9增廣鏈設(shè)f是一個(gè)可行流,μ是從vs到vt的一條鏈,若μ滿足下列條件,稱之為關(guān)于可行流f的一條增廣鏈。(vi,vj)∈μ-0<fij

≤

cij

后向弧是非零流弧，(vi,vj)∈μ+0≤fij<cij

前向弧是非飽和弧，v1v2v3v4v5v6(8,4)(6,0)(6,5)(3,3)(5,4)10（6）.截集與截量對(duì)于有向網(wǎng)絡(luò)G=(V,A,C），若S為V的子集，，則稱弧集為網(wǎng)絡(luò)G的一個(gè)截集，并將截集中所有弧容量之和稱為截容量，即為截集的截容量（簡(jiǎn)稱為截量）。（7）最小截與最小截量若是容量網(wǎng)絡(luò)中所有截集中截量最小的截集，即則稱為G上的最小截，為上的最小截量。11

性質(zhì)

任何一個(gè)可行流的流量V(f)都不會(huì)超過任一截集的容量。即可行流f*，截集(V1*，V1*),若V(f*)=C(V1*，V1*），則f*必是最大流，(V1*，V1*)必是D的最小截集。定理

若f*是網(wǎng)絡(luò)G=（V，A，C）上的可行流，則可行流f*為最大的充要條件為μ中不存在關(guān)于f*的增廣鏈。最大流最小截量定理。任一個(gè)網(wǎng)絡(luò)D中，從vs到vt的最大流的流量等于分離vs，vt的最小截集的容量。127.4.2尋求最大流的標(biāo)號(hào)法（Ford—Fulkerson）從任一個(gè)可行流f出發(fā)（若網(wǎng)絡(luò)中沒有給定f，則從零流開始），經(jīng)過標(biāo)號(hào)過程與調(diào)整過程。（一）標(biāo)號(hào)過程13標(biāo)號(hào)：開始，vs標(biāo)上（0，∞），vs是標(biāo)號(hào)未檢查的點(diǎn)，其余點(diǎn)都是未標(biāo)號(hào)點(diǎn)，一般地，取一個(gè)標(biāo)號(hào)未檢查的點(diǎn)vi，對(duì)一切未標(biāo)號(hào)的點(diǎn)vj。（1）若弧（vi，vj）上，fij<cij，則給vj標(biāo)號(hào)(i，l(vj))，l(vj)=min[l(vi),cij-fij],vj成為標(biāo)號(hào)而未檢查的點(diǎn)。（2）若?。╲j，vi）上，fji>0，則給vj標(biāo)號(hào)(-i，l(vj))，l

(vj)=min[l(vi),fji],vj成為標(biāo)號(hào)而未檢查的點(diǎn)。fij<cijvivj(i,l(vj))l(vj)=min[l(vi),cij-fij],fji>0vivj(-i,

l(vj))l(vj)=min[l(vi),fji]14重復(fù)上述步驟，一旦vt被標(biāo)號(hào)，則得到一條vs到vt的增廣鏈。若所有標(biāo)號(hào)都已檢查過，而vt尚未標(biāo)號(hào)，結(jié)束，這時(shí)可行流，即最大流。（二）調(diào)整過程從vt開始，反向追蹤，找出增廣鏈μ，并在μ上進(jìn)行流量調(diào)整。（1）找增廣鏈

如vt的第一個(gè)標(biāo)號(hào)為k（或-k），則?。╲k，vt）∈μ（或?。╲t，vk)∈μ)。檢查vk的第一個(gè)標(biāo)號(hào)，若為i（或-i），則(vi,vk)∈μ(或(vk,vi)∈μ)。再檢查vi的第一個(gè)標(biāo)號(hào),依此下去,直到vs。被找出的弧構(gòu)成了增廣鏈μ。15（2）流量調(diào)整令調(diào)整量是l(vt)，構(gòu)造新的可行流f′，令

去掉所有的標(biāo)號(hào),對(duì)新的可行流f′={fij′},重新進(jìn)入標(biāo)號(hào)過程。16例用標(biāo)號(hào)法求下圖網(wǎng)絡(luò)的最大流。弧旁的數(shù)字是(cij,fij)。解：（一）標(biāo)號(hào)過程。（1）給vs標(biāo)上（0，∞）；v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，∞）在弧（vs，v2）上，fs2=cs2=3,不滿足標(biāo)號(hào)條件。（2）檢查vs，在?。╲s，v1）上，fs1=1，cs1=5，fs1<cs1,給v1標(biāo)號(hào)(s,l(v1)),其中（vs，4）17（3）檢查v1，在?。╲2，v1）上，f21>0，給v2標(biāo)號(hào)(-1,l(v2)),在弧（v1，v3）上，f13=2，c13=2，不滿足標(biāo)號(hào)條件。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=1>0，給v3標(biāo)號(hào)(-2,l(v3)),這里（-v2，1）18在弧（v2，v4）上，f24=3，c24=4，f24<c24,給v4標(biāo)號(hào)(2,l(v4)),其中（5）檢查v3，在?。╲3，vt）上，f3t=1，c3t=2，

f3t<c3t，給vt標(biāo)號(hào)(3,l(vt)),這里vt得到標(biāo)號(hào)，標(biāo)號(hào)過程結(jié)束。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)19（二）調(diào)整過程：從vt開始逆向追蹤，找到增廣鏈。μ（vs,v1,v2,v3,vt）=1，在μ上進(jìn)行流量=1的調(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)20去掉各點(diǎn)標(biāo)號(hào)，從vs開始，重新標(biāo)號(hào)。點(diǎn)v1：標(biāo)號(hào)過程無法進(jìn)行，所以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′）=C[V1，V1]=5V1=(vs,v1)V1=(v2,v3,v4,vt)問題：(v2,v1)是不是截集[V1，V1]中的??？21例用標(biāo)號(hào)法求下圖網(wǎng)絡(luò)的最大流?；∨缘臄?shù)字是(cij,fij)。v1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)vt22解：第一輪

標(biāo)號(hào)過程

（1）vs標(biāo)（0，+∞），vs為已標(biāo)號(hào)未檢查點(diǎn)。

（2）檢查vs，給v2標(biāo)號(hào)（vs，l(v2)）

，vs成為已標(biāo)號(hào)已檢查的點(diǎn)，v2成為已標(biāo)號(hào)未檢查的點(diǎn)。

（3）檢查v2，給v1標(biāo)號(hào)（-v2，l(v1)）

。同理給v4標(biāo)號(hào)為（v2，1），v2成為已標(biāo)號(hào)已檢查的

點(diǎn)，v1，v4成為已標(biāo)號(hào)未檢查的點(diǎn)。

（4）檢查v1，給v3標(biāo)號(hào)為（v1，2），v3成為已標(biāo)號(hào)未檢

查的點(diǎn)。

（5）檢查v3，給vt標(biāo)號(hào)為（v3，2）。

因?yàn)関t已被標(biāo)號(hào)，所以說明找到一條增廣鏈。

調(diào)整過程

按點(diǎn)的第一個(gè)標(biāo)號(hào)，以vt點(diǎn)開始，回溯找到一條增廣

鏈，

如下圖紅線所示：23vt(0，+∞)（vs，4）（-v2，2）（v2，1）（v1，2）（v3，2）v1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)24vtv1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)在增廣鏈上進(jìn)行了流量調(diào)整。前向弧后向弧于是調(diào)整后流量如下圖所示。(0，+∞)（vs，4）（-v2，2）（v2，1）（v1，2）（v3，2）25v1v4v2vsv3(3，3)(5，3)(2，0)(6，4)(3，2)(2，2)(2,0)(6，5)(5，2)vt26第二輪：標(biāo)號(hào)過程（1）vs標(biāo)（0，+∞），vs為已標(biāo)號(hào)未檢查點(diǎn)。（2）檢查vs，給v2標(biāo)號(hào)（v