1第五章圖論與網(wǎng)絡(luò)優(yōu)化2§5-1引論§5-2圖論基本概念

§5-3樹(shù)及其優(yōu)化問(wèn)題§5-4最短路問(wèn)題§5-5最大流問(wèn)題3§5-5最大流問(wèn)題

在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問(wèn)題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問(wèn)題等等。而網(wǎng)絡(luò)系統(tǒng)最大流問(wèn)題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問(wèn)題，它對(duì)于解決生產(chǎn)實(shí)際問(wèn)題起著十分重要的作用。一.網(wǎng)絡(luò)與流二.增廣鏈與截集三.標(biāo)號(hào)法4問(wèn)題描述:

連通有向圖D(V,A)有m個(gè)節(jié)點(diǎn),n條弧,弧aij上的流量上界為cij,求從起始節(jié)點(diǎn)vs到終點(diǎn)vt的最大流量。下圖是聯(lián)結(jié)某個(gè)起始地vs和目的地vt的交通運(yùn)輸網(wǎng)，每一條弧aij

旁邊的權(quán)cij表示這段運(yùn)輸線的最大通過(guò)能力，貨物經(jīng)過(guò)交通崗從vs運(yùn)送到vt。要求指定一個(gè)運(yùn)輸方案，使得從vs到vt的貨運(yùn)量最大，這個(gè)問(wèn)題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題。vtv3v2v1v4vs1735108611453Cij5

一.網(wǎng)絡(luò)與流定義12

設(shè)一個(gè)賦權(quán)有向圖D=（V,A）,在V中指定兩個(gè)點(diǎn)：一個(gè)發(fā)點(diǎn)，記作vs，一個(gè)收點(diǎn)，記作vt,其它的點(diǎn)叫做中間點(diǎn)。

D中的任一個(gè)弧aij∈A,都對(duì)應(yīng)有非負(fù)權(quán)cij，稱為aij上的容量，所有cij

的集合記作C，稱為D上的容量集，簡(jiǎn)稱容。這樣的賦權(quán)有向圖

D稱為一個(gè)網(wǎng)絡(luò)，記做D=（V，A，C）（三元組表示）。

網(wǎng)絡(luò)D上的流，是指定義在弧集合A上的一個(gè)函數(shù)f={f(vi,vj)}={fij},f(vi,vj)=fij叫做弧(vi,vj)上的流量。6vtv3v2v1v4vs（17,2）(5,2)(10,5)（8,3)(6,3)(11,6)(4,1）(5,1)（3,2）fij(3,3)下圖表示的就是這個(gè)網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案），每一個(gè)弧上的流量fij

就是運(yùn)輸量。例如fs1=5,fs2=3,f13=2等等。對(duì)于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流，有幾個(gè)顯著的特點(diǎn)：

(1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等；

(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零；

(3)每一個(gè)弧上的流量不能超過(guò)它的最大通過(guò)能力（即容量）7

定義13

使A中任一弧aij對(duì)應(yīng)一個(gè)實(shí)數(shù)fij，如果fij

滿足容量約束：

0

fij

cij

，則稱fij為aij上的流量，所有aij上對(duì)應(yīng)的流量集合記作F，稱為D上的流量集，簡(jiǎn)稱流。

定義14

設(shè)F={fij|aij∈A}為網(wǎng)絡(luò)D的流，若fij滿足守恒條件：對(duì)于發(fā)點(diǎn)vs,有：對(duì)于收點(diǎn)vt,有：對(duì)于中間點(diǎn)，有：

則稱F為D上的可行流，其中，v(F)稱為對(duì)應(yīng)F的流量，取正值為輸出量，取負(fù)值為輸入量，可行流中使流量取得最大值者，稱為最大流。8二.增廣鏈與截集

任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。網(wǎng)絡(luò)系統(tǒng)中最大流問(wèn)題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流f,其流量v(f)達(dá)到最大值。因此，求最大流的思路是從一個(gè)初始可行流（如零流）出發(fā)，逐步增大流量，一直到不能再增大為止。于是，必須要尋找允許流量增大的通道。如果存在這樣的通道，說(shuō)明流量還可以增大；如果不存在，說(shuō)明流量已經(jīng)達(dá)到極限，最大流也就得到。顯然，這類通道即是D所對(duì)應(yīng)的基礎(chǔ)圖上從vs到vt的一條鏈。9

設(shè)有網(wǎng)絡(luò)D及可行流F，則（1）當(dāng)fij=cij

，aij稱為飽和?。划?dāng)fij<cij

，aij稱為非飽和弧，（2）fij=0，aij稱為零流??；fij>0，aij稱為非零流弧。

設(shè)L是網(wǎng)絡(luò)D中一條從發(fā)點(diǎn)νs到收點(diǎn)vt的簡(jiǎn)單鏈。定義鏈的方向是從νs到

vt

，于是鏈L上的弧被分為兩類：一類是弧的方向與鏈的方向相同，叫做前向?。ㄕ蚧。?，前向弧的集合記做L+。二類是弧的方向與鏈的方向相反，叫做后向?。ǚ聪蚧。?，后向弧的集合記做L–。顯然：L+∪L–=L;L+∩L–=

10增廣鏈的作用：增大流量增廣鏈滿足的條件：正向弧是非飽和弧（非飽和弧的作用是增大流量）;逆向弧是非零流?。ǚ橇懔骰〉淖饔檬菧p少流量）；飽和弧的作用：減少流量零流弧的作用：增大流量非飽和非零流弧的作用：增大流量和減少流量。定義15

設(shè)網(wǎng)絡(luò)D上有可行流F，若簡(jiǎn)單鏈L上各弧的流量滿足：則L稱為關(guān)于F的一條增廣鏈。11

定義16

設(shè)一個(gè)網(wǎng)絡(luò)D=（V，A，C）。如果點(diǎn)集V被剖分為兩個(gè)非空集合V1和，使得：則弧集稱為分離vs與vt的一個(gè)截集，記作：而值稱為截集S的容量，簡(jiǎn)稱截量。記作：

顯然S與都不是唯一的。對(duì)V做不同的劃分，可以得到不同的截集與截量。使截量取最小值的截集稱為最小截集。記作S*。

12vsv1v2v4v3vt374556378V1例如在右圖中，取

則于是，截集而截集容量

由于V的分解方法不同，所以截集就不相同，對(duì)應(yīng)的截集的容量也不相同，其中容量最小的稱為最小截集。13下面的事實(shí)是顯然的：一個(gè)網(wǎng)絡(luò)D中，任何一個(gè)可行流f的流量v(f)都小于或等于這個(gè)網(wǎng)絡(luò)中任何一個(gè)截集(V1,的截量。并且，如果網(wǎng)絡(luò)上的一個(gè)可行流那么f*一定是D上的最大流，而（V1*,）一定是D的所有的截集中截量最小的一個(gè)（即最小截集）f*

和網(wǎng)絡(luò)中的一個(gè)截集（V1*,滿足條件v*(f*)=s(V1*,

14定理8設(shè)網(wǎng)絡(luò)D=(V,A,C),F*與S*中是D上的最大流與最小截集，則有：v(F*)=C(S*)。即：在一個(gè)網(wǎng)絡(luò)D中，最大流的流量等于分離vs和vt

的最小截集的截量。定理8為我們提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法。亦即，如果網(wǎng)絡(luò)D中有一個(gè)可行流f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f的增廣鏈。如果沒(méi)有增廣鏈，那么f一定是最大流。如有增廣鏈，那么可以不斷改進(jìn)和增大可行流f的流，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。15

三．標(biāo)號(hào)法

從網(wǎng)絡(luò)中的一個(gè)可行流f出發(fā)（如果D中沒(méi)有f，可以令f是零流），運(yùn)用標(biāo)號(hào)法，經(jīng)過(guò)標(biāo)號(hào)過(guò)程和調(diào)整過(guò)程，可以得到網(wǎng)絡(luò)中的一個(gè)最大流。標(biāo)號(hào)法的要點(diǎn)：按照一定的規(guī)則，用一個(gè)二維數(shù)組，從出發(fā)點(diǎn)Vs起開(kāi)始標(biāo)號(hào)過(guò)程；然后通過(guò)查號(hào)過(guò)程來(lái)尋找增廣鏈L，如果存在L，就在L上調(diào)高流量，再重新標(biāo)號(hào)與查號(hào)；如果找不到L了，則意味著已得最大流。16

在標(biāo)號(hào)過(guò)程中，網(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)包含兩部分（vi，lj）：第一部分表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的,其目的是為了找出增廣鏈；如（vi，lj）的vi表示在的vi點(diǎn)得到；第二部分是為了用來(lái)確定增廣鏈上的調(diào)整量θ，如（vi，lj）中的lj表示增廣鏈上的調(diào)整量θ=

lj

。滿足：和1.標(biāo)號(hào)過(guò)程17取初始可行流；給發(fā)點(diǎn)vs

標(biāo)號(hào)，其中：即發(fā)點(diǎn)vs的標(biāo)號(hào)為（0，+∞）。(2)取一個(gè)已標(biāo)號(hào)的點(diǎn)vi，即，對(duì)于vi一切未標(biāo)號(hào)的鄰接點(diǎn)vj（）按下列規(guī)則處理：(a)如果在?。╲i,vj）上，fij<cij

，那么給vj

標(biāo)號(hào)(vi,lj)。其中：

lj=min[li,cij–fij]。這時(shí)，vj成為標(biāo)號(hào)未檢查點(diǎn)，即。(b)如果在?。╲j,vi）上，fji>0,那么給vj標(biāo)號(hào)(-vi,lj).其中：

lj=min[li,fji]。這時(shí)，vj成為標(biāo)號(hào)未檢查點(diǎn)，即。

此時(shí)有：，(3)重復(fù)步驟2，直到vt被標(biāo)號(hào)或標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，則標(biāo)號(hào)法結(jié)束。若vt被標(biāo)號(hào)，則存在一條可增廣鏈，轉(zhuǎn)調(diào)整過(guò)程，若vt未被標(biāo)號(hào)，而標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，這時(shí)的可行流就是最大流。，如：18

2.調(diào)整過(guò)程

首先按照vt和其它標(biāo)號(hào)點(diǎn)的第一部分，反向追蹤，找出增廣鏈L

。例如，已知vt標(biāo)號(hào)的第一個(gè)部分是vk，則弧（vk,vt）在L上；再看vk的第一個(gè)部分，若是vi，則弧(vi,vk)也在L上；依次類推，直到vs為止。這時(shí)，所找出的弧就成為網(wǎng)絡(luò)D的一條增廣鏈L。得新的可行流，去掉原有標(biāo)號(hào)，對(duì)新的可行流重新進(jìn)行標(biāo)號(hào)過(guò)程，直到找到網(wǎng)絡(luò)D的最大流為止。取調(diào)整量θ=lt

，即vt標(biāo)號(hào)的第二部分，令：19例9求下圖中的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù)表示（cij,fij）。vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)圖5-13（例9）20（1）首先給vs標(biāo)號(hào)（vs，ls）=（0，+∞）（2）檢查vs:

在弧(vs

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

,v1)上,fs1=1<cs1=5,故給v1標(biāo)號(hào)（vs,l1),

其中：

l1=min[ls,(cs1–fs1)]=min[+∞,5–1]=4.（3）檢查v1:

在?。╲1

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

,v1)上,f21=1>0,故給v2標(biāo)號(hào)（-v1

,l2）,

其中：l2=min[l1,f21]=min[4,1]=1.vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)解：用標(biāo)號(hào)法。

1.標(biāo)號(hào)過(guò)程（0，+∞）（vs

,4)（-v1

,1）21（4）檢查v2:

在?。╲2

,v4）上，f24

=3<c24=4,故給v4標(biāo)號(hào)（v2

,l4），

其中：l4=min[l2,(c24

–f24)]=min[1,1]=1.

在?。╲3

,v2)上，f32

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

其中：l3=min[l2,f32]=min[1,1]=1。（5）在v3

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

。

在?。╲3,vt）上，f3t

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

其中：lt=min[l3,(c3t-f3t)]=min[1,1]=1。因?yàn)関t被標(biāo)上號(hào)，根據(jù)標(biāo)號(hào)法，轉(zhuǎn)入調(diào)整過(guò)程。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)222.調(diào)整過(guò)程從vt開(kāi)始，按照標(biāo)號(hào)點(diǎn)的第一部分，用反向追蹤的方法，找出一條從vs到vt的增廣鏈L={vs,v1,v2,v3,vt}，如圖5-13（a）中紅線所示。不難看出：L+={(vs,v1),(v3,vt)},L–

={(v2,v1),(v3,v2)},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)圖5-13（a）23取θ=lt＝1，在L上調(diào)整f得：進(jìn)而得到圖5-13（b）圖5-13(b)vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)2200vsv1v2v3v4vt(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)圖5-13（a）24調(diào)整后的可行流f（1），如圖5-13（b）所示，再對(duì)這個(gè)可行流從新進(jìn)行標(biāo)號(hào)過(guò)程，尋找增廣鏈。首先給vs標(biāo)號(hào)（0，+∞），看vs：給v1標(biāo)號(hào)（vs,3）?？磛1：在弧（v1

,v3）上，f13=c13；

?。╲2

,v1）上，f21=0,均不符合條件。因此標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，不存在從vS到vt的增廣鏈，算法結(jié)束。這時(shí)，網(wǎng)絡(luò)中的可行流f（1）

即是最大流。

圖中，標(biāo)號(hào)點(diǎn)集V1={vs,v1}；未標(biāo)號(hào)點(diǎn)的集

圖5-13(b)vsv1v2v3v4vt(3,3)(5,2

)(4,3)(1,0

)(1,0

)(2,2)(3,0)(5,3)(2,2

)（0，+∞）（vs,3）最大流的流量f*=v(f（1）)=fs2+f13=3+2=5最小截集（V1，）={(vs,v2),(v1,v3)}={as1,a13}c25例10

求圖5-14所示網(wǎng)絡(luò)的最大流vsv1vtv5v4v3v24310413354278圖5-14(例10)26解：給定初始可行流為全零流，即f（0）

=0給vs標(biāo)號(hào)：(0,ls)=（0，+∞）。查vs：給v1

標(biāo)號(hào)：(vs,min{ls,cs1-fs1})=(vs,min{+∞,4-0})=(vs,4)；給v2

標(biāo)號(hào)：(vs,min{ls,cs2-fs2})=(vs,min{+∞,3-0})=(vs,3)；給v3

標(biāo)號(hào)：(vs,min{ls,cs3-fs3})=(vs,

min{+∞,10-0}=10)=(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）(vs,4)(vs,3)(vs,10)（0，+∞）27(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)28因?yàn)榻K點(diǎn)vt

已標(biāo)號(hào)，故找出一條從vs到vt的增廣鏈L：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）29(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）30(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）31vsv1vtv5v4v3v2（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,10)(v3,4)(v5,2)(v5,3)32vsv1vtv5v4v3v2（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）（7,4）（8,8）33vsv1vtv5v4