運(yùn)輸網(wǎng)絡(luò)最大流問題本節(jié)內(nèi)容的安排基本概念與基本定理尋求最大流的標(biāo)號(hào)法一、引言1.應(yīng)用背景在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題,控制系統(tǒng)中的信息流問題，常見的人流，物流，水流，氣流，電流，現(xiàn)金流等。在一定條件下,求解給定系統(tǒng)的最大流量,就是網(wǎng)絡(luò)最大流問題.2.問題描述 連通網(wǎng)絡(luò)G(V,A)中有m個(gè)節(jié)點(diǎn),n條弧,弧eij

上的流量上界為cij

,求從起始節(jié)點(diǎn)vs

到終點(diǎn)vt

的最大流量的問題就是最大流問題。引例：如下輸水網(wǎng)絡(luò)，南水北調(diào)工程，從v1到v6送水，弧旁數(shù)字為管道容量，問應(yīng)當(dāng)如何輸水使得流量最大？v2v451v1v6v3v5108533171131、網(wǎng)絡(luò)與流設(shè)一個(gè)賦權(quán)有向圖D=（V,A）,在V-----圖中的節(jié)點(diǎn)，中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt

,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于A-----圖中的弧，D中的每一個(gè)弧（vi

,vj）∈A,都有一個(gè)非負(fù)數(shù)cij

,叫做弧的容量---

cij

。我們把這樣的圖D叫做一個(gè)容量網(wǎng)絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)，記做D=（V，A，C）?；〉娜萘浚菏菍?duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通過能力，記為c(vi,vj)或簡(jiǎn)寫為cij

。二、基本概念sts’t’對(duì)有多個(gè)發(fā)點(diǎn)和多個(gè)收點(diǎn)的網(wǎng)絡(luò),可以另外虛設(shè)一個(gè)總發(fā)點(diǎn)和一個(gè)總收點(diǎn),并將其分別與各發(fā)點(diǎn)、收點(diǎn)連起來（見圖），就可以轉(zhuǎn)換為只含一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)。所以一般只研究具有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)流：加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量,即弧線上的流量f(vi,vj)：加在弧(vi,vj)上的負(fù)載量簡(jiǎn)記為fij，

fij>=0.網(wǎng)絡(luò)上的流：是指定義在弧集合上的一個(gè)函數(shù)f={f(vi,vj)},注意：弧的流量f(vi,vj)：表示弧(vi,vj)上每單位時(shí)間內(nèi)的實(shí)際通過能力弧的容量c(vi,vj)：表示?。╲i,vj)上每單位時(shí)間內(nèi)的最大通過能力零流：網(wǎng)絡(luò)上所有的fij

=0例如下圖表示的就是這個(gè)網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案），每一個(gè)弧上的流量fij就是運(yùn)輸量。例如：f12=1,f13=2,f24=3等等。v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvtv3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt對(duì)于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流，有幾個(gè)顯著的特點(diǎn)：(1)發(fā)點(diǎn)的凈流出量和收點(diǎn)的凈流入量必相等。(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零。(3)每一個(gè)弧上的流量不能超過它的最大通過能力（即容量）稱滿足下列條件的流為可行流：（1）容量限制條件：對(duì)于每一個(gè)?。╲i,vj）∈A有0f(vi,vj)c(vi,vj)（簡(jiǎn)記為0

fij

cij）2、可行流與最大流（2）平衡條件：

總流量v(f)=發(fā)點(diǎn)的凈輸出量v(f)=收點(diǎn)的凈輸入量-v(f)容量網(wǎng)絡(luò)的可行流總是存在的，如當(dāng)所有弧的流均取零，即對(duì)所有的i,j,有f(vi,vj)=0就是一個(gè)可行流可行流中fij＝cij

的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。fij＞0

的弧為非零流弧，fij＝0

的弧叫做零流弧。13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)

圖中誰(shuí)是零流弧，誰(shuí)是飽和弧？就是要求一個(gè)流{fij

},使其流量v(f)達(dá)到最大,并且滿足

0fij

cij網(wǎng)絡(luò)的最大流:求網(wǎng)絡(luò)的最大流，即是指滿足容量限制條件和平衡條件的條件下，使v(f)值達(dá)到最大.容量網(wǎng)絡(luò)D，若給μ定向?yàn)閺膙s到vt，圖上的弧分為兩類：凡與μ方向相同的稱為前向弧，凡與μ方向相反的稱為后向弧，其集合分別用μ+和μ-表示。

鏈的方向：若μ是聯(lián)結(jié)vs和vt的一條鏈，定義鏈的方向是從vs到vt。3、增廣鏈stf1<c1f4<c4f5<c5f2>0f3>0增廣鏈：一條鏈中的可行流，如果滿足：中的每一條弧都是非飽和弧中的每一條弧都是非零流弧則稱μ為從vs到vt

的關(guān)于f的一條增廣鏈。stf1<c1f4<c4f5<c5f2>0f3>0v2v53-34-18-3v3v1v4v65-110-511-66-317-23-25-2μ=(v1,v2,v3,v4,v5,v6)μ+={(v1,v2),(v2,v3),(v3,v4),(v5,v6)}μ-={(v5,v4)}后向弧13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一個(gè)增廣鏈顯然圖中增廣鏈不止一條

4、截集與截量我們?cè)趫D中畫一條線，使所有始點(diǎn)屬于Vs，而終點(diǎn)屬于Vt

，v2v53(3)4（1）8(3）v3v1v4v65（1）10（5)11(66（3017(2)3（2）5（2）

=(v1,v2,v3)V11=(v4,v5,v6)

=(v1,v2,v3)V11=(v4,v5,v6)截集為所有被割斷的弧線，黃色弧集：v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2vsv1v2v4v3vt374556378V1截集為所有被割斷的弧線，弧線上的容量之和，稱作截量。13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)則截集為：截量為2413(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)，則截集為截量為20sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)對(duì)應(yīng)的截量也不相同，其中截量最小的截集稱為最小截集。由于V與V的分解方法不同，所以截集就不相同截集與可行流無(wú)關(guān)，而只與網(wǎng)絡(luò)本身有關(guān)最小截量是個(gè)定值結(jié)論2：可行流f

*＝{fij*}是最大流，當(dāng)且僅當(dāng)D中不存在關(guān)于f

*的增廣鏈。結(jié)論1：即任何一個(gè)可行流的流量都不會(huì)超過任一截集的容量總結(jié)：對(duì)最大流問題有下列結(jié)論和定理：三、最大流問題的標(biāo)號(hào)法步驟：判斷是否存在增廣鏈,并設(shè)法把增廣鏈找出來,并予以調(diào)整,最終使圖中無(wú)增廣鏈.此算法從網(wǎng)絡(luò)中的一個(gè)可行流f出發(fā)（如果D中沒有f，可以令f是零流），運(yùn)用標(biāo)號(hào)法，經(jīng)過標(biāo)號(hào)過程和調(diào)整過程，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。在標(biāo)號(hào)過程中，網(wǎng)絡(luò)中的點(diǎn)分為兩種：已標(biāo)號(hào)的點(diǎn)（分為已檢查和未檢查）和未標(biāo)號(hào)的點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的，以便找出增廣鏈。第二個(gè)標(biāo)號(hào)是從上一個(gè)標(biāo)號(hào)點(diǎn)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值，是為了用來確定增廣鏈上的調(diào)整量θ。

1．

標(biāo)號(hào)過程標(biāo)號(hào)過程開始，先給vs

標(biāo)號(hào)（0，+∞）。這時(shí)，vs

是標(biāo)號(hào)未檢查的點(diǎn)，其它都是未標(biāo)號(hào)點(diǎn)。如果vt有了標(biāo)號(hào)，表示存在一條關(guān)于f的增廣鏈。如果標(biāo)號(hào)過程無(wú)法進(jìn)行下去，并且vt未被標(biāo)號(hào)，則表示不存在關(guān)于f的增廣鏈。此時(shí)，就得到了網(wǎng)絡(luò)中的一個(gè)最大流。例

求圖10-25的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù)表示（cij

,fij）。

解：

1.標(biāo)號(hào)過程。1）首先給vs標(biāo)號(hào)（0，+∞）

2）看vs

:在弧(vs

,v2)上,fs2=cs3=3,不具備標(biāo)號(hào)條件。在弧(vs

,v1)上,fs1=1<cs1=5,

故給v1標(biāo)號(hào)（vs

,l(v1)),

其中l(wèi)(v1)表示最大可調(diào)整量=min[+∞,5–1]=4.

v1標(biāo)號(hào)為：（vs,4），此時(shí)vs為已檢查的標(biāo)號(hào)點(diǎn)。vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(0,+)。（3）看v1:在?。╲1

,v3）上,f13=c13=2,不具備標(biāo)號(hào)條件.

在弧(v2

,v1)上,f21=1>0,

故給v2標(biāo)號(hào)（-v1,l(v2)）,

其中l(wèi)(v2)=min[l(v1),f21]=min[4,1]=1.

v2標(biāo)號(hào)（-v1,1），此時(shí)v1為已檢查的標(biāo)號(hào)點(diǎn)vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(0,+)(–v1,1)（4）看v2:在?。╲2

,v4）上，f24

=3<c24=4,

故給v4標(biāo)號(hào)（v2,l(v4)）其中l(wèi)(v4)=min[l(v2),(c24–f24)]=min[1,1]=1.

在?。╲3

,v2)上，f32

=1>0,故給v3標(biāo)號(hào)（-v2，l(v3)),

其中

l(l(v3

)=min[l(v2),f32]=min[1,1]=1。(0,+)vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(–v1,1)(-v2,1)(v2,1)（5）在v3

,v4中任意選一個(gè)，如v3

,在?。╲3,vt）上，f3t

=1<c3t=2,故給vt標(biāo)號(hào)(v3,l(vt)),

其中l(wèi)(vt)=min[l(v3),(c3t-f3t)]=min[1,1]=1.

因?yàn)関t被標(biāo)上號(hào)，根據(jù)標(biāo)號(hào)法，轉(zhuǎn)入調(diào)整過程。vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(0,+)(vs,4)(–v1,1)(v2,1)(-v2,1)(v3,1)

（1）如果在前向?。╲i,vj）上，有fij<cij

,那么給vj

標(biāo)號(hào)（vi,l(vj)）.其中l(wèi)(vj)=min[l(vi),cij

–

fij].

這時(shí)，vj

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

（2）如果在后向?。╲j

,vi）上，有fji

>0,那么給vj標(biāo)號(hào)（-vi,l(vj)）.其中l(wèi)(vj)=min[l(vi),fji

].這時(shí)，vj

成為標(biāo)號(hào)未檢查點(diǎn)。于是vi成為標(biāo)號(hào)已檢查的點(diǎn)?？偨Y(jié)標(biāo)號(hào)過程重復(fù)以上步驟，如果所有的標(biāo)號(hào)都已經(jīng)檢查過，而標(biāo)號(hào)過程無(wú)法進(jìn)行下去，則標(biāo)號(hào)法結(jié)束。這時(shí)的可行流就是最大流。但是，如果vt

被標(biāo)上號(hào)，表示得到一條增廣鏈μ，轉(zhuǎn)入下一步調(diào)整過程。

2.調(diào)整過程

利用反向追蹤找增廣鏈，調(diào)整增廣鏈的流量，去掉舊的標(biāo)號(hào)，對(duì)新的可行流重新進(jìn)行標(biāo)號(hào)。具體做法如下：（1）按照vt和其它已檢查的標(biāo)號(hào)點(diǎn)的第一個(gè)標(biāo)號(hào)，反向追蹤，找出增廣鏈μ

，確定調(diào)整量θ。（2)得新的可行流。

(3)再去掉所有的標(biāo)號(hào)，對(duì)新的可行流f’={f’ij},重新進(jìn)行標(biāo)號(hào)過程，直到找到網(wǎng)絡(luò)D的最大流為止。非增廣鏈上的弧vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(5,2)(1,0)(1,0)(2,2)(cij

,fij)f*=fs1+θ=1+1=2在μ+上f3t+θ=1+1=2在μ+上f*=f21–θ=1–1=0在μ-上f32

–

θ=1–1=0在μ-上其它的不變?cè)鰪V鏈的調(diào)整量為1，則有：

調(diào)整后的可行流f*如圖,再對(duì)這個(gè)可行流從新進(jìn)行標(biāo)號(hào)過程，尋找增廣鏈。一直到標(biāo)號(hào)過程無(wú)法進(jìn)行下去，不存在從vS到vt的增廣鏈，算法結(jié)束。vsv1v2v3v4vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij

,fij)vsv1v2v3v4vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(cij

,fij)(0,+)(vs,3)最大流的流量v(f

*)=fs1+fs2=5.最小截集它的容量也為5.得到的截集為最小截集（V1，），其中V1是標(biāo)號(hào)的集合，是未標(biāo)號(hào)的集合。此時(shí)，網(wǎng)絡(luò)中的可行流f*即是最大流，sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)(0,)(s,2)(-v2,2)(v1,2)(-v3,1)(v4,1)例:用標(biāo)號(hào)法求下圖中s→t的最大流量,并找出該網(wǎng)絡(luò)的最小割.ε(v2)=min{ε(s),(cs2-fs2)}=2ε(v1)=min{ε(v2),f12}=min{2,4}=2ε(v3)=min{ε(v1),(c13-f13)}=min{2,5}=2ε(v4)=min{ε(v3),f43}=min{2,1}=1ε(t)=min{ε(v4),(c4t-f4t)}=min{1,2}=1sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)V*(f)==９＋５－０＝１４sv2v4v3v1t7(6)8(8)9(5)5(3)2(0)9(9)6(0)10(9)5(5)(-v2,1)(0,)(v1,1)(s,1)KK(0+,)(s+,6)(2,6)(3+,1)(4+,1)(0+,)(s+,5)(2+,2)(5,2)(4+,2)例：(0+,)(s+,3)(2,3)最小截集最大流的流量為：14+12+5+4=35例：求下圖所示網(wǎng)絡(luò)的最大流vsv1vtv5v4v3v24310413354278解：給定初始可行流為全零流，即f（0）

=0給vs

標(biāo)號(hào)（0，+∞），檢查vs

：給v1

標(biāo)號(hào)(vs

,4),給v2

標(biāo)號(hào)(vs

,3),給v3

標(biāo)號(hào)(vs

,10),vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(0,+)(vs

,4)(vs

,3)(vs

,10)檢查v1：給v4

標(biāo)號(hào)(v1,1)，檢查完畢；(v1,1)檢查v2：給v5

標(biāo)號(hào)(v2,3)，檢查完畢；vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(v2,3)檢查v5：給vt

標(biāo)號(hào)(v5,3)，檢查完畢；(v5,3)因?yàn)榻K點(diǎn)vt

已標(biāo)號(hào)，故找出一條從vs到vt的增廣鏈μ：vs

—

v2—v5—vt

.取=3vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）vsv1vtv5v4v3v2（4,0）（10,0）（3,0）（3,0）（3,0）（4,0）（1,0）（2,0）（5,0）（4,0）（7,0）（8,0）(vs

,4)(v1,3)(vs

,10)(v1,1)vsv1vtv5v4v3v2（4,0）（10,0）（3,3）（3,0）（3,0）（4,0）（1,0）（2,0）（5,3）（4,0）（7,0）（8,3）(v2,2)(0,+)(v5,2)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(vs

,2)(v3,3)(vs

,10)(v2,3)vsv1vtv5v4v3v2（4,2）（10,0）（3,3）（3,2）（3,0）（4,0）（1,0）（2,0）（5,5）（4,0）（7,0）（8,5）(v3,4)(0,+)(v4,3)vsv1vtv5v4v3v2（4,2）（10,3）（3,3）（3,2）（3,3）（4,0）（1,0）（2,0）（5,5）（4,3）（7,3）（8,5）vsv1vtv5v4v3v2（4,2）（10,3）（3,3）（3,2）（3,3）（4,0）（1,0）（2,0）（5,5）（4,3）（7,3）（8,5）vsv1vtv5v4v3v2（4,2）（10,6）（3,3）（3,2）（3,3）（4,3）（1,0）（2,0）（5,5）（4,3）（7,3）（8,8）(0,+)(vs

,2)(vs

,7)(v3,4)(v5,2)(v5,3)vsv1vtv5v4v3v2（4,3）（10,6）（3,3）（3,2）（3,3）（4,3）（1,1）（2,0）（5,5）（4,3）（7,4）（8,8）vsv1vtv5v4v3v2（4,2）（10,6）（3,3）（3,2）（3,3）（4,3）（1,0）（2,0）（5,5）（4,3）（7,3）（8,8）(0,+)(vs

,2)(vs

,4)(v1,1)(v1,1)(v4,1)vsv1vtv5v4v3v2（4,3）（10,6）（3,3）（3,2）（3,3）（4,3）（1,1）（2,0）（5,5）（4,3