計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第11章 網(wǎng)絡(luò)流

1第11章

網(wǎng)絡(luò)流網(wǎng)絡(luò)流問(wèn)題的定義

2網(wǎng)絡(luò)中的流與割的關(guān)系

11Ford-Fulkerson方法

24Ford-Fulkerson通用方法

24Edmonds-Karp算法

30Dinic算法

36二部圖的匹配問(wèn)題

44推進(jìn)-重標(biāo)號(hào)算法簡(jiǎn)介

631.網(wǎng)絡(luò)流問(wèn)題的定義2網(wǎng)絡(luò)流是一個(gè)圖的算法問(wèn)題。簡(jiǎn)單來(lái)說(shuō)，網(wǎng)絡(luò)流問(wèn)題就是在一個(gè)給定的網(wǎng)絡(luò)中找出一個(gè)從源點(diǎn)到匯點(diǎn)的最大流。定義11.1

一個(gè)流網(wǎng)絡(luò)(flownetwork)，簡(jiǎn)稱(chēng)網(wǎng)絡(luò)，是一個(gè)加權(quán)的簡(jiǎn)單有向圖G=(V,E)，邊(u,v)

E

的權(quán)值c(u,v)>0是個(gè)正數(shù)，稱(chēng)為容量。規(guī)定，邊(u,v)

E當(dāng)且僅當(dāng)c(u,v)=0。另外，圖中有兩個(gè)指定的頂點(diǎn)，分別稱(chēng)為源點(diǎn)和匯點(diǎn)，通常標(biāo)記為s

和t。例11.1v115124916582637sv2v3v4t3

4v110/154/46/81/3sv25/122/99/165/50/25/66/7v3v4t(a)

一個(gè)非規(guī)范流的例子v110/154/45/80/3sv25/120/99/165/50/25/64/7v3v4t(b)

規(guī)范化以后的流規(guī)范流如果邊(u,v)和(v,u)上都有非零的流，那么從點(diǎn)u運(yùn)送到點(diǎn)v的物資中有一部分又從v流回到u。顯然，這是個(gè)浪費(fèi)。這樣的流稱(chēng)為非規(guī)范流。在這種情況下，我們總可以把這對(duì)邊上的流等量減少使得有一個(gè)方向上的流為零。我們把這個(gè)操作稱(chēng)為規(guī)范化。如果任一對(duì)邊(u,v)和(v,u)上都有f(u,v)=0或者f(v,u)=0，那么f稱(chēng)為一個(gè)規(guī)范流。顯然，規(guī)范化不影響流的值。(見(jiàn)下面例子，圖11.2)5相對(duì)流定義11.4

假設(shè)f是網(wǎng)絡(luò)G=(V,E)上的一個(gè)流。定義邊(u,v)上的對(duì)應(yīng)于f的相對(duì)流為

(u,v)=f(u,v)-f(v,u)。集合V

V中所有邊的相對(duì)流組成網(wǎng)絡(luò)G=(V,E)上的一個(gè)相對(duì)流

。

(u,v)就是從u到v的凈流量。物理含義是，如果從u到v有運(yùn)輸量f(u,v)，從v到u有運(yùn)輸量f(v,u)，那么從u到v的凈運(yùn)輸量，即相對(duì)流，為

(u,v)=f(u,v)-f(v,u)。引入相對(duì)流相當(dāng)于代數(shù)中引入正負(fù)數(shù)一樣，便于我們對(duì)流進(jìn)行加減運(yùn)算。我們用字母f和

分別表示流和相對(duì)流。6

7

8

9

10最大流問(wèn)題由引理11.1和引理11.2可知，一個(gè)規(guī)范流f和一個(gè)相對(duì)流

之間有如下的一一對(duì)應(yīng)關(guān)系：從

f計(jì)算對(duì)應(yīng)于

f的相對(duì)流

:

(u,v)=f(u,v)-f(v,u)。從

計(jì)算對(duì)應(yīng)于

的規(guī)范流f:

f(u,v)=max{0,

(u,v)}。實(shí)際上，把

中所有

(u,v)<0的相對(duì)流改為0就得到規(guī)范流f。反之，把所有f(u,v)=0的流改為

-f(v,u)就得相對(duì)流

。另外，我們始終有關(guān)系：

(u,v)

f(u,v)

c(u,v)。因?yàn)橐?guī)范化不影響流的值，除特別聲明外，這一章討論的流都是規(guī)范流。定義11.6 網(wǎng)絡(luò)的最大流問(wèn)題就是在給定的一個(gè)流網(wǎng)絡(luò)G=(V,E)上找出一個(gè)有最大|f|值的流f。這個(gè)流稱(chēng)為網(wǎng)絡(luò)G的一個(gè)最大流。

我們可類(lèi)似地定義最大相對(duì)流問(wèn)題，并且等價(jià)于最大流問(wèn)題。11

2.網(wǎng)絡(luò)中的流與割的關(guān)系12

割的容量是

c(S,T)=15+3+7+2+5=32。13

14

15剩余網(wǎng)絡(luò)和增廣路徑定義11.8

假設(shè)f是網(wǎng)絡(luò)G(V,E)的一個(gè)流，

是對(duì)應(yīng)的相對(duì)流。對(duì)應(yīng)于f的剩余網(wǎng)絡(luò)Gf(V,Ef)定義如下：與原網(wǎng)絡(luò)G有相同的頂點(diǎn)集合V，相同的源點(diǎn)s和匯點(diǎn)t；

邊(u,v)

V

V

的容量為

cf(u,v)=c(u,v)-

(u,v)，稱(chēng)為對(duì)應(yīng)于f的剩余容量；(3) Ef包括所有剩余容量大于零的邊，不包括為零的邊：

Ef

={(u,v)|cf(u,v)>0}。剩余容量的含意：cf(u,v)=c(u,v)-

(u,v)=c(u,v)–[f(u,v)-f(v,u)]==[c(u,v)–f(u,v)]+f(v,u)。

這表明剩余容量由兩部分組成：(1) c(u,v)–f(u,v)，容量c(u,v)減去流f(u,v)后所剩下的容量。(2) 把流f(v,u)從u推回到v,，產(chǎn)生的(相對(duì))容量。16v110/154/45/80/3sv25/120/99/165/50/25/64/7v3v4t(a)

圖11-2(b)中的網(wǎng)絡(luò)流fv154108sv271375213v3v4t(b)

對(duì)應(yīng)的剩余網(wǎng)絡(luò)Gf3559例注：如果(u,v)

Ef，則

cf(u,v)=c(u,v)-

(u,v)>0。必有兩種可能：

(1) c(u,v)>0，所以(u,v)

E，

(2) c(u,v)=0，

(v,u)>0，f(v,u)>0，所以(v,u)

E。

總之，|Ef|

2|E|，

所以，構(gòu)造剩余網(wǎng)絡(luò)Gf(V,Ef)的時(shí)間是O(|V|+|E|)。17定理11.7

設(shè)f和

是網(wǎng)絡(luò)G

的一個(gè)流及相對(duì)流，而f’和

’是剩余網(wǎng)絡(luò)Gf

的一個(gè)流和相對(duì)流。那么，G中存在一個(gè)規(guī)范流f*，它的相對(duì)流是

*(u,v)=

(u,v)+

’(u,v)，并且有|f*|=|f|+|f’|。流f*稱(chēng)為f的一個(gè)增廣流，記為f*

=f+f’。

18

流f*可以通過(guò)

*=

+

’來(lái)計(jì)算。但是，f*也可以從f

和f’直接計(jì)算，增廣流f*的計(jì)算規(guī)則：(設(shè)f,f’都是規(guī)范流，容易驗(yàn)證)(A) f(u,v)>0，f(v,u)=0 (對(duì)稱(chēng)情況：(B)f(u,v)=0,f(v,u)>0)(A.1) 如果f’(u,v)>0，那么f*(u,v)=f(u,v)+f’(u,v)，f*(v,u)=0。(A.2)

如果f’(u,v)=0并有f(u,v)

f’(v,u)，那么置

f*(u,v)=f(u,v)-f(v,u)，f*(v,u)=0。(A.3) 如果f’(u,v)=0并有f(u,v)<f’(v,u)，

那么置f*(u,v)=0，f*(v,u)=f(v,u)-f(u,v)。19定義11.10

假設(shè)f是網(wǎng)絡(luò)G的一個(gè)流。剩余網(wǎng)絡(luò)Gf

中一條從源點(diǎn)s到匯點(diǎn)t的簡(jiǎn)單路徑p稱(chēng)為一條增廣路徑(augmentingpath)。這條路徑上剩余容量最小的邊稱(chēng)為關(guān)鍵邊，關(guān)鍵邊的剩余容量定義為這條路徑的容量cf

(p)，即cf

(p)=min{

cf

(u,v)|(u,v)

p}。

20增廣路徑流的例子v154108sv271375213v3v4t(a)

圖11-5(b)中剩余網(wǎng)絡(luò)的一條增廣路徑3559v11/50/40/100/8sv20/70/131/70/51/21/10/3v3v4t(b)

基于增廣路徑構(gòu)造的流1/30/50/50/9怎樣計(jì)算f*(u,v)和f*(v,u)前面，在定理11.7之后，我們介紹過(guò)從

f和

fp直接計(jì)算增廣流f*的規(guī)則。為方便對(duì)后面?zhèn)未a的理解，針對(duì)增廣路徑流，我們給出從f和cf(p)直接計(jì)算增廣流f*的規(guī)則如下，并給出簡(jiǎn)單解釋。假定網(wǎng)絡(luò)G上的流f是規(guī)范流。(見(jiàn)下頁(yè))21基于路徑p的增廣流f*的計(jì)算規(guī)則：如果邊(u,v)

p，規(guī)則如下:(如

(u,v)

p，f*(u,v)=f(u,v)不變)(I.1)如果f(u,v)>0，置f*(u,v)=f(u,v)+cf

(p)，f*(v,u)=0。這是因?yàn)?

(u,v)=f(u,v)>0，

p(u,v)=cf

(p)>0，

*(u,v)=f(u,v)+cf

(p)>0，f*(u,v)=max{0,

*(u,v)}=

f(u,v)+cf

(p)，f*(v,u)=0。(I.2)如果f(u,v)=0，但f(v,u)

cf(p)，置f*(v,u)=f(v,u)-cf(p)，f*(u,v)=0。這是因?yàn)?/p>

(u,v)=0-f(v,u)，

p(u,v)=cf

(p)-0，所以有：

*(u,v)=

(u,v)+

p(u,v)=cf

(p)-f(v,u)

0，

*(v,u)=-

*(u,v)0f*(u,v)=0，f*(v,u)=max{0,

*(v,u)}=f(v,u)-cf

(p)。(解釋?zhuān)阂黾觰到v的流cf

(p)，就相當(dāng)于減少?gòu)膙到u的流cf

(p)。)(I.3) 如果f(u,v)=0，但f(v,u)<cf(p)，置f*(v,u)=0，f*(u,v)=cf(p)-f(v,u)。(解釋?zhuān)阂黾觰到v的流cf

(p)，先把f(v,u)減到零，但仍不夠。這差額部分，cf(p)-f(v,u)，就是實(shí)際需要的從u到v的流。)22最大流最小割定理

定理11.9

設(shè)f是網(wǎng)絡(luò)G=(V,E)的一個(gè)最大流，那么一定存在一個(gè)割(S,T)使得|f|=c(S,T)，并且這個(gè)割的容量是最小的。證明：設(shè)Gf

是最大流f的剩余網(wǎng)絡(luò)。那么，有以下推理：

Gf中不存在從s到t的路徑，否則，f可以增廣為更大的流。定義割(S,T)如下：S是Gf中從s可以有路徑到達(dá)的頂點(diǎn)集合，而T

=V–S。因?yàn)镚f中不存在從s到t的路徑，s

S

而t

T。顯然，Gf

中沒(méi)有從S中任一點(diǎn)到T中任一點(diǎn)的邊。這說(shuō)明，網(wǎng)絡(luò)G中的任一條從S到T的邊(u,v)，u

S,v

T,的剩余容量為零。也就是cf(u,v)=c(u,v)-

(u,v)=0，即c(u,v)=

(u,v)。所以c(S,T)=

(S,T)=|f|。根據(jù)推論11.6，|f|小于等于任何一個(gè)割的容量，因此c(S,T)也小于等于任何一個(gè)割的容量。所以，c(S,T)的容量是最小的。

23

19這一節(jié)我們介紹傳統(tǒng)的且仍然被廣泛應(yīng)用的求網(wǎng)絡(luò)最大流的算法，即Ford-Fulkerson算法。Ford-Fulkerson的通用算法給定一個(gè)流網(wǎng)絡(luò)G(V,E)，F(xiàn)ord-Fulkerson的通用算法是：1.

先給每條邊(u,v)

E

一個(gè)初始流，f(u,v)

0。不在E中的邊的流約定為0，這顯然滿足流的兩個(gè)條件。2.

然后，不斷地在剩余網(wǎng)絡(luò)Gf中找一條增廣路徑p把當(dāng)前流增廣，直至找不到增廣路徑為止。

下面是這個(gè)算法的偽碼。Ford-Fulkerson(G(V,E),s,t)

foreachedge(u,v)

E；f(u,v)0endfor //初始流為0(接下頁(yè))3.Ford-Fulkerson算法25Gf

G

//流為0的剩余網(wǎng)絡(luò)就是G本身whilethereexistspathpfromstotinGf //Gf

中有增廣路徑p

cf(p)

min{cf(u,v)|(u,v)

p} //路徑p的容量

foreachedge(u,v)inp

G(V,E) //在G中增加流量

iff(u,v)>0 //必有

(u,v)>0

then f(u,v)

f(u,v)+cf(p)

else

if

f(v,u)

cf(p)

then

f(v,u)

f(v,u)-cf(p)

else

f(u,v)

cf(p)-f(u,v)

f(v,u)

0

endif endif

endfor

computeGf

//更新GfendwhileEnd26算法中，compute

Gf

這一步只需在剩余網(wǎng)絡(luò)Gf中更新在路徑p上的邊的容量即可。具體操作可用以下偽碼取代這一行：foreach(u,v)

pingraphGf

//在圖Gf中操作

cf(u,v)

cf(u,v)-cf(p)

ifcf(u,v)=0

then

Ef

Ef–{(u,v)} //容量為零的邊不出現(xiàn)在網(wǎng)絡(luò)中endifcf(v,u)

cf(v,u)+cf(p)Ef

Ef

{(v,u)} //也許邊(v,u)已在Ef中endfor我們稱(chēng)上面的算法為通用算法是因?yàn)樗鼪](méi)有指定用什么方法去找增廣路徑p，只要找到一條就行。讓我們看一個(gè)例子。27例11.7用Ford-Fulkerson方法找出下面網(wǎng)絡(luò)的一個(gè)最大流。請(qǐng)圖示每輪中的剩余網(wǎng)絡(luò)，所用增廣路徑，以及對(duì)應(yīng)的增廣流。sv1v2v3v45412181376109t19解：下面圖(11-7)中每一對(duì)小圖對(duì)應(yīng)一輪計(jì)算。左邊顯示的是對(duì)應(yīng)于上一輪增廣流(第一對(duì)是初始流)的剩余網(wǎng)絡(luò)及它的一條增廣路徑。右邊顯示的是基于這條路徑的增廣流。最后一輪中的剩余網(wǎng)絡(luò)中沒(méi)有增廣路徑，因而只有一個(gè)小圖，計(jì)算結(jié)束。這時(shí)，前一輪中(圖(h))的增廣流就是最大流，流量是|f|=23。另外，它對(duì)應(yīng)的最小割是(S,T)，其中S={s,v1,v2,v4}，T={v3,t}。2810sv1v2

v3

v4

54121813769t19(a)sv1v2

v3

v4

0/54/40/120/184/134/70/64/100/9t0/19(b)6sv1v2

v3

v4

5121893109t19(c)sv1v2

v3

v4

0/50/410/1210/184/134/76/64/100/9t10/19(d)444296sv1v2

v3

v4

52893109t9(e)sv1v2

v3

v4

0/50/410/1210/1810/134/76/610/100/9t16/19(f)444101010sv1v2

v3

v4

52833109t3(g)sv1v2

v3

v4

3/50/410/1213/1813/137/76/610/100/9t16/19(h)10104101016sv1v2

v3

v4

225109t3最大流見(jiàn)圖(h)，|f|=23。最小割是S={s,v1,v2,v4}，T={v3,t}13107101316330Edmonds-Karp算法(改進(jìn)的Ford-Fulkerson算法)通用的Ford-Fulkerson算法可能需要許多次增廣，甚至不收斂Edmond-Karp算法只需最多

mn/2

次增廣Ford-Fulkerson算法需要許多次增廣的例子1,000,000svut1,000,0001,000,0001,000,0001(a)初始流為零的剩余圖和增廣路徑(b)第一輪增廣流svut1/1,000,0000/1,000,000!0/1,000,0001/1,000,0001/1999,999svut999,9991,000,0001,000,0001(c)第一輪增廣流的剩余圖和增廣路徑11(d)第二輪增廣流svut1/1,000,0001/1,000,0001/1,000,0001/1,000,0000/131引理11.11假設(shè)f是網(wǎng)絡(luò)G

的一個(gè)流。又假設(shè)f*是由剩余網(wǎng)絡(luò)Gf中一條最短路徑而得的增廣流。那么，在f*的剩余網(wǎng)絡(luò)Gf*中，從源點(diǎn)s到任一頂點(diǎn)v

的距離，

f*(s,v)，以及v到匯點(diǎn)t的距離，

f*(v,t)，分別等于或大于它在剩余網(wǎng)絡(luò)Gf中的距離

f(s,v)和

f(v,t)。證明：因?yàn)?/p>

f*(v,t)

f(v,t)的證明類(lèi)似，我們只證明

f*(s,v)

f(s,v)。我們對(duì)

f*(s,v)的長(zhǎng)度k進(jìn)行歸納證明。歸納基礎(chǔ)：當(dāng)

f*(s,v)=k=0時(shí)，必有v=s，因?yàn)?/p>

f*(s,s)=

f(s,s)=0，所以

f*(s,v)

f(s,v)正確。歸納步驟：假設(shè)對(duì)任一頂點(diǎn)v，只要

f*(s,v)

k(k

0)，就有

f*(s,v)

f(s,v)。我們證明，當(dāng)

f*(s,v)=k+1時(shí)，也必定有

f*(s,v)

f(s,v)。設(shè)Gf*中對(duì)應(yīng)

f*(s,v)=k+1的路徑p的最后一條邊是(u,v)。(接下頁(yè))32如圖所示，那么p中從s到u的子路徑必是最短路徑，長(zhǎng)為

f*(s,u)=k。我們分兩種情況。(u,v)也出現(xiàn)在

Gf中，由歸納假設(shè)，

f*(s,u)

f(s,u)，那么在Gf中有一條從s經(jīng)過(guò)u到v的路徑。因此有

f(s,v)

f(s,u)+1，所以有

f*(s,v)=

f*(s,u)+1

f(s,u)+1

f(s,v)，歸納成功。(u,v)不出現(xiàn)在Gf中，那么(u,v)出現(xiàn)在Gf*中的唯一原因是增廣流f*所用的增廣路徑p’(

Gf)中含有邊(v,u)。(接下頁(yè))p:(在Gf*

中)usv

f*(s,u)=k

f*(s,v)=

f*(s,u)+1=k+1引理11.11證明(繼續(xù)1)33引理11.11證明(繼續(xù)2)因?yàn)槁窂絧’也提供了一條Gf中從s到v的最短路徑。下圖(11-10)顯示了這樣一條路徑，并同時(shí)顯示了一條在Gf*中從s到v的一條最短路徑以便比較。Gf*

中一條從s到u再到v的最短路徑pusv

f*(s,u)=k

f*(s,v)=k+1Gf

中一條從s到v再到u的最短路徑p’vsu

f(s,v)

f(s,u)=

f(s,v)+1t由歸納假設(shè)，

f*(s,u)

f(s,u)，所以有：

f*(s,v)=

f*(s,u)+1

f(s,u)+1=

f(s,v)+2，歸納成功。

34定理11.12

Edmonds-Karp算法最多需要

mn/2

次增廣流的計(jì)算。證明：在增廣路徑流中，關(guān)鍵邊上的流等于它的容量。因此，關(guān)鍵邊將不出現(xiàn)在剩余網(wǎng)絡(luò)中。如果關(guān)鍵邊(u,v)再次出現(xiàn)在一條增廣路徑上，那么這次的增廣路徑的長(zhǎng)度比上一次的路徑至少長(zhǎng)出2條邊。證明如下：假設(shè)(u,v)是剩余網(wǎng)絡(luò)Gf中增廣路徑p上的一條關(guān)鍵邊。|p|=

f(s,u)+1+

f(v,t)。如果邊(u,v)又出現(xiàn)在以后的某個(gè)剩余網(wǎng)絡(luò)Gf*的增廣路徑p*中，那么，必定有一個(gè)增廣流f’，|f|<|f’|<

|f*|,它在剩余網(wǎng)絡(luò)Gf’中使用的增廣路徑p’包含邊(v,u)。所以必有：

f’(s,u)=

f’(s,v)+1。(接下頁(yè))35定理11.12證明繼續(xù):

根據(jù)引理11.11，我們有：

f*(s,u)

f’(s,u)=

f’(s,v)+1

f(s,v)+1

f(s,u)+2;所以有|p*|=

f*(s,u)+

f*(u,t)

f(s,u)+2+

f(u,t)=|p|+2。所以，邊(u,v)成為關(guān)鍵邊的次數(shù)k不會(huì)超過(guò)

n/2。因?yàn)閳D中有m條邊，一共可以提供最多

mn/2

次關(guān)鍵邊，而每一輪增廣路徑都至少有一個(gè)關(guān)鍵邊，因此最多需要增廣

mn/2

次。

推論11.13Edmonds-Karp算法找到網(wǎng)絡(luò)G(V,E)的最大流所需時(shí)間為O(nm2)。證明：用廣度優(yōu)先在剩余圖中找一條從s到t的最短路徑需要O(m)時(shí)間。因?yàn)樽疃嘈枰?/p>

mn/2

次增廣，Edmonds-Karp算法的復(fù)雜度為O(nm2)。

36Dinic算法在Edmonds-Karp算法的基礎(chǔ)上作了改進(jìn)。主要思路:用剩余網(wǎng)絡(luò)Gf中一條最短路徑把流增廣后，不立即更新剩余網(wǎng)絡(luò)，而是繼續(xù)在當(dāng)前的Gf中找一條同樣短的增廣路徑直到不存在為止。這時(shí)，Dinic算法才構(gòu)造下一輪的剩余網(wǎng)絡(luò)。如何能找到所有的最短路徑？我們引入層次圖的概念。層次圖

假設(shè)s是有向圖G(V,E)的一個(gè)頂點(diǎn)。如果我們把從s到任一點(diǎn)v

V的(不加權(quán))最短距離記為

(s,v)，那么G的子圖LG(V,E’,s)稱(chēng)為以s為起點(diǎn)的層次圖(Level

Graph)，其中V

不變,E’={(u,v)

E|

(s,v)=

(s,u)+1}。層次圖包含了G中從s到任一點(diǎn)v的所有最短路徑。一個(gè)流網(wǎng)絡(luò)的層次圖也是一個(gè)流網(wǎng)絡(luò)。37構(gòu)造層次圖的算法計(jì)算s為起點(diǎn)的BFS樹(shù)。樹(shù)中路徑p(s,v)就是最短路徑，距離是

(s,v)。圖G中邊(u,v)，不論在不在BFS樹(shù)，都有

(s,v)

(s,u)+1。檢查每條邊(u,v)，如果

(s,v)=

(s,u)+1，則把(u,v)加入到

LG(V,E’,s)中，否則棄之。(a)

一個(gè)有向圖Gabcegfdabcegfd

=0

=1

=1

=2

=2

=2

=3(b)

以a為起點(diǎn)的層次圖和廣度優(yōu)先樹(shù)(標(biāo)以紅色)例層次圖中的邊保留原來(lái)的權(quán)(容量)。構(gòu)造層次圖的時(shí)間是O(m)，m=|E|。38阻塞流網(wǎng)絡(luò)G(V,E)中一個(gè)流f稱(chēng)為一個(gè)阻塞流，如果從源點(diǎn)s到匯點(diǎn)t的任何一條路徑都含有一條飽和邊。這里，邊

(u,v)

E稱(chēng)為飽和邊，如果f(u,v)=c(u,v)，即邊

(u,v)上的流量等于它的容量。例(a)

一個(gè)流網(wǎng)絡(luò)Gs1111111bctad(b)

流網(wǎng)絡(luò)

G的一個(gè)阻塞流s0/11/11/11/10/10/10/1bctad阻塞流不一定是最大流。Dinic算法在每一輪中，構(gòu)造當(dāng)前剩余網(wǎng)絡(luò)的層次圖，找出它的一個(gè)阻塞流并用來(lái)增廣原網(wǎng)絡(luò)中的流。39尋找層次圖的阻塞流的算法層次圖的初始流是零。然后，以s為起點(diǎn)對(duì)層次圖作DFS搜索。每次搜索會(huì)碰到下面兩種情況之一。這時(shí)，搜索停止并做相應(yīng)處理：匯點(diǎn)t被訪問(wèn)到。DFS的堆棧中的點(diǎn)，從底到頂，形成一條從s到t的增廣路徑。把層次圖

LG(V,E’,s)中流增廣，并把飽和邊標(biāo)以“阻塞”?！白枞边呍谝院蟮腄FS搜索中不再使用。然后，重新開(kāi)始以s為起點(diǎn)的DFS搜索。當(dāng)前訪問(wèn)的頂點(diǎn)v沒(méi)有出去的邊或者所有的出邊都已阻塞。這時(shí)，沒(méi)有任何路經(jīng)可以通過(guò)v而到達(dá)t。把v從堆棧彈出，回溯到v的父親u后繼續(xù)當(dāng)前的DFS搜索，并把(u,v)標(biāo)以“阻塞”。當(dāng)從s出去的邊都被阻塞時(shí)，阻塞流算法也停止。因?yàn)镺(n)時(shí)間至少有一邊會(huì)標(biāo)阻塞，一共O(m)條邊。算法復(fù)雜度為O(mn)。40Dinic算法偽碼Dinic(G(V,E),s,t)foreachedge(u,v)

E

f(u,v)

0 //初始流為零endforGf

G //G本身就是流量為零的剩余圖constructLGf(V,E’,s)forGf

//構(gòu)造Gf

的距離圖whilesinktisinLGf

//只要t出現(xiàn)在層次圖中就可增廣 findablockingflowf’inLGf//找阻塞流f’

f

f+f’

//將f增廣為f+f’ constructGf

forflowf

//為下一輪構(gòu)造剩余圖 constructLGf(V,E’,s)forGf

//構(gòu)造Gf的層次圖

endwhile

End41Dinic算法復(fù)雜度因?yàn)槊恳淮窝h(huán)(稱(chēng)為一輪)的主要工作是為層次圖找一個(gè)阻塞流，時(shí)間已知為O(mn)，所以我們需要對(duì)循環(huán)次數(shù)作出分析。引理11.14Dinic算法中每一輪循環(huán)后的層次圖中s到t的路徑長(zhǎng)度比前一輪層次圖中的長(zhǎng)度至少多一條邊。證明：假設(shè)f是某次循環(huán)前網(wǎng)絡(luò)G中的流，其層次圖是LGf。循環(huán)后得到阻塞流f’，并由此把G中流增廣為f*=f+f’。假設(shè)對(duì)應(yīng)于f*的層次圖是LGf*。用

f*(s,t)和

f(s,t)分別表示LGf*和LGf中從s到t的距離。我們證明

f*(s,t)

f(s,t)+1。假設(shè)p是LGf*中一條從s到t的路徑。因?yàn)長(zhǎng)Gf中飽和邊不在LGf*中，所以p中有邊不在LGf中，否則，p的每條邊都是LGf中非飽和邊而使p成為L(zhǎng)Gf中的增廣路徑，這與f’是阻塞流矛盾。(接下頁(yè))42引理11.14證明(繼續(xù))：設(shè)邊(u,v)

p

但不出現(xiàn)在LGf中。原因只有兩種：(a) (v,u)出現(xiàn)在LGf上并有f’(v,u)>0。這時(shí)，在LGf中必有從s到t的路徑經(jīng)過(guò)(v,u)。因阻塞流f’是由等長(zhǎng)的最短路徑增廣而得，由引理11.11，我們有

f*(s,t)=

f*(s,u)+1+

f*(v,t)

f(s,u)+1+

f(v,t)

=[

f(s,v)+1]+1+

f(v,t)]=

f(s,t)+2。(b) (u,v)不出現(xiàn)在LGf上但出現(xiàn)在剩余圖Gf中，是因?yàn)樗谟?jì)算LGf時(shí)被刪去，但在計(jì)算LGf*時(shí)被用上。那么必定有

f(s,v)

f(s,u)。由引理11.11，有

f*(s,t)=

f*(s,u)+1+

f*(v,t)

f(s,u)+1+

f(v,t)

f(s,v)+1+

f(v,t)=

f(s,t)+1。

43推論11.15Dinic算法最多需要計(jì)算n

-2次阻塞流。證明：假設(shè)計(jì)算第一次阻塞流時(shí)，層次圖中從s到t的距離為d，d

1。假設(shè)一共進(jìn)行了k輪阻塞流的計(jì)算。由引理11.14，在做完最后一輪阻塞流的計(jì)算時(shí)，剩余網(wǎng)絡(luò)中從s到t的距離至少為1+k。因?yàn)閺膕到t的簡(jiǎn)單路徑的長(zhǎng)度

(s,t)最多是n-1，所以有k+1

n–1。因而有k

n–2。

定理11.16Dinic算法的復(fù)雜度是O(mn2)證明：由推論11.15，Dinic算法最多需要計(jì)算n

–2輪阻塞流，而每一輪的復(fù)雜度是O(mn)，所以Dinic算法的復(fù)雜度是O(mn2)。

444.二部圖的匹配問(wèn)題定義11.13如果M

E是圖G(V,E)的一個(gè)邊的集合，并且M中任意兩條邊都不共享(即不尋關(guān)聯(lián))同一個(gè)頂點(diǎn)，則稱(chēng)為一個(gè)匹配。另外，如果邊(u,v)

M，則稱(chēng)頂點(diǎn)u和v相匹配。如果一個(gè)匹配M包含的邊的個(gè)數(shù)|M|是所有匹配中最多的，則稱(chēng)M為一個(gè)最大匹配。我們只討論二部圖的匹配問(wèn)題。大量的實(shí)際問(wèn)題可歸約為找一個(gè)二部圖的最大匹配問(wèn)題。例：集合T={t1,t2,…,tn}代表n個(gè)工作需要分配，而集合P={p1,p2,…,pm}代表m個(gè)工人需要申請(qǐng)工作。假設(shè)，任何一個(gè)工作最多只能錄取一個(gè)工人承擔(dān)，而每個(gè)申請(qǐng)工作的人也最多只能得到一個(gè)工作，我們?cè)鯓硬拍茏屪疃嗟纳暾?qǐng)者得到工作呢？我們可以把這個(gè)問(wèn)題建模為一個(gè)二部圖G(U,W,E)的最大匹配問(wèn)題如下。(接下頁(yè))45用

U={u1,u2,…,un}代表n個(gè)工作，ui

代表工作ti(1

i

n)。用

W={w1,w2,…,wm}代表m個(gè)工人，wj

代表pj(1

j

m)。U和W組成二部圖的頂點(diǎn)集合。如果申請(qǐng)工作ti的人中有pj，則構(gòu)造一條邊(ui,wj)。一個(gè)匹配對(duì)應(yīng)一個(gè)工作分配，一個(gè)最大匹配就是一個(gè)最佳解。UW(a)M={(a,w),(c,y)}abcdewxyzUW(b)M={(b,w),(c,x),(d,y)}abcdewxyz圖11-13

一個(gè)二部圖的匹配和最大匹配的例子460-1網(wǎng)絡(luò)的最大流問(wèn)題(預(yù)備知識(shí))如果任一條邊上的流都是整數(shù)，則稱(chēng)為整數(shù)流。如果每條邊的容量都是整數(shù)，則稱(chēng)為整數(shù)網(wǎng)絡(luò)。整數(shù)網(wǎng)絡(luò)的最大流是整數(shù)流。如果每條邊的容量不是1就是0，并且頂點(diǎn)u和v之間，有c(u,v)=0或c(v,u)=0

或都為0，則稱(chēng)為一個(gè)0-1網(wǎng)絡(luò)。許多應(yīng)用問(wèn)題可以建模為求解一個(gè)0-1網(wǎng)絡(luò)的最大流。如果f是0-1網(wǎng)絡(luò)G(V,E)上一個(gè)整數(shù)流，那么Gf也必定是一個(gè)0-1網(wǎng)絡(luò)并且|E|=|Ef|。解釋?zhuān)喝绻鹒(u,v)=1，那么Gf中，(u,v)

Ef

，但(v,u)

Ef且容量為1。否則，(u,v)

Ef，但(v,u)

Ef，所以，Gf是一個(gè)0-1網(wǎng)絡(luò)。并且，顯然有|E|=|Ef|。用Dinic算法找0-1網(wǎng)絡(luò)最大流可有很好的復(fù)雜度。47

48引理11.18

假設(shè)G(V,E)是一個(gè)0-1網(wǎng)絡(luò)，那么Dinic算法每次計(jì)算阻塞流的時(shí)間是O(m)。證明：當(dāng)Dinic算法用DFS搜索去找增廣路徑時(shí)，有以下兩種情況：匯點(diǎn)t被訪問(wèn)到。這時(shí)在DFS的堆棧中的點(diǎn)，從底到頂，形成一條從s到t的增廣路徑。把層次圖增廣后，因?yàn)槭?-1網(wǎng)絡(luò)，路徑上所有邊都是飽和邊而全部成為“阻塞”邊。然后，重新開(kāi)始一次DFS搜索。當(dāng)前訪問(wèn)的頂點(diǎn)v的出邊都已阻塞。這時(shí)算法把v彈出堆棧，回溯到v的父親u，把(u,v)標(biāo)以“阻塞”，然后，繼續(xù)DFS?？梢?jiàn)，層次圖中每條邊入棧(指箭頭端)最多一次，一旦彈出便被標(biāo)以“阻塞”，所以最多需要O(m)次堆棧操作就可找到阻塞流。因?yàn)槎褩２僮魇侵饕僮?，Dinic算法每次計(jì)算阻塞流的時(shí)間是O(m)。

49

50單分支網(wǎng)絡(luò)定義11.14如果一個(gè)0-1網(wǎng)絡(luò)中除了源點(diǎn)s和匯點(diǎn)t以外的任一頂點(diǎn)都只有一條出去的邊或者一條進(jìn)來(lái)的邊，則稱(chēng)為單分支0-1網(wǎng)絡(luò)。例(圖中邊容量都是1，略去)sacbdeft

51用網(wǎng)絡(luò)流求二部圖的最大匹配算法假設(shè)G(U,W,E)是一個(gè)二部圖，尋找G(U,W,E)的最大匹配問(wèn)題可以轉(zhuǎn)化為一個(gè)單分支0-1網(wǎng)絡(luò)的最大流問(wèn)題，具體做法如下：Bipartite-to-Single-Branch(G(U,W,E))V

U

W

{s,t} //圖的頂點(diǎn)加上源點(diǎn)s和匯點(diǎn)tE’

{(u,w)|(u,w)

E,u

U,w

W} //賦以從U到W的方向E’

E’

{(s,u)|u

U} //加上從s到U中點(diǎn)u的一條邊E’

E’

{(w,t)|v

W} //加上從W中點(diǎn)w到t的一條邊f(xié)oreachedge(x,y)

E’

c(x,y)

1 //E’中每條邊賦以容量1endforreturnG’(U,W,E’,s,t)End顯然，我們得到的是一個(gè)單分支0-1網(wǎng)絡(luò)，并且只需O(n+m)時(shí)間就可構(gòu)造好G’，這里n=|U|+|W|，m=|E|。52WUabcdewxyzst由圖11-13（ppt.45頁(yè)）構(gòu)造的單分支0-1網(wǎng)絡(luò)。每條邊容量都是1，略去不標(biāo)。定理11.21假設(shè)G’(U,W,E,s,t)是由二部圖G(U,W,E)得到的一個(gè)單分支0-1網(wǎng)絡(luò)，那么G(U,W,E)中存在一個(gè)有k條邊的匹配M，當(dāng)且僅當(dāng)G’(U,W，E,s,t)有一個(gè)整數(shù)流f使得|f|=k。證明：見(jiàn)下頁(yè)。53定理11.21證明：假設(shè)M是G(U,W,E)中一個(gè)匹配，構(gòu)造流f如下：如果(u,w)

M，則賦以f(s,u)=1,f(u,w)=1和f(w,t)=1，而其他的邊則賦以零。因?yàn)槠ヅ渲械倪叢还岔旤c(diǎn)，這顯然是一個(gè)合法的整數(shù)流，而且有|f|=|M|。下圖顯示了對(duì)應(yīng)于圖11-13(a)中匹配的流。WUabcdewxyzst1/11/11/11/11/11/10/10/10/10/10/10/10/10/10/10/10/1反之，如果0-1網(wǎng)絡(luò)G’有整數(shù)流f，那么可構(gòu)造匹配M如下：(接下頁(yè))圖11-13(a)中，M

={(a,w),(c,y)}54定理11.21證明(繼續(xù))(2)

如果邊(s,u)上有流f(s,u)=1，那么因?yàn)閱畏种ЬW(wǎng)絡(luò)的特點(diǎn)，必定存在頂點(diǎn)w

W使得f(u,w)=1和f(w,t)=1。我們把邊(u,w)選入匹配M。因選出的邊的個(gè)數(shù)等于從s流出的總流量，所以|M|=|f|。而且，如果f(u,w)=1，那么任何其他的從u出去的邊和任何指向w的邊上的流量必需是零以滿足流量守恒，這使得選進(jìn)M的邊都不共享頂點(diǎn)。所以M是二部圖G(U,W,E)的一個(gè)匹配并有|M|=|f|。

55PhilipHall婚配定理問(wèn)題簡(jiǎn)介：假設(shè)有n個(gè)未婚小伙子的集合U和m個(gè)未婚姑娘的集合W，每個(gè)小伙子希望在幾個(gè)中意的姑娘里選一個(gè)為妻，但每個(gè)姑娘只能嫁給最多一個(gè)小伙子。我們是否能找到一個(gè)婚配的方案使每個(gè)小伙子都能娶到他中意的姑娘之一？PhilipHall婚配問(wèn)題可建模為二部圖G(U,W,E)的最大匹配問(wèn)題。如果小伙子u中意姑娘w的話，那么E中就有邊(u,w)。如果二部圖G(U,W,E)的最大匹配M滿足|M|=|U|，則稱(chēng)為完全匹配。如果|U|=|W|，一個(gè)完全匹配亦稱(chēng)為一個(gè)完美匹配。PhilipHall婚配問(wèn)題是要找一個(gè)完全匹配。PhilipHall婚配定理給出有完全匹配的充要條件。56定理11.21

(Hall氏婚配定理)二部圖G(U,W,E)有完全匹配的充要條件是：對(duì)于U的任一子集B

U，均有|B|

|R(B)|。這里，R(B)

W

是B的映象集合，即W中所有與集合B中至少一個(gè)點(diǎn)相鄰的點(diǎn)的集合。證明：必要性：如果G有完全匹配M，那么，任一子集B中不同的點(diǎn)匹配于W中不同的點(diǎn)，因此，W中至少有|B|個(gè)不同的點(diǎn)與B中點(diǎn)相鄰，也就是|B|

|R(B)|，所以|B|

|R(B)|是必要條件。充分性：根據(jù)定理11.21，我們只須證明，在對(duì)應(yīng)的單分支0-1網(wǎng)絡(luò)G’(U,W，E’,s,t)中的最大流等于|U|。假設(shè)|U|=n，由最大流最小割定理，我們只需證明，網(wǎng)絡(luò)G’的任何一個(gè)割的容量大于等于n即可。(接下頁(yè))57k條s到A的邊都是穿越邊。如k

=n，定理得證。如k

<n，那么R(B)中每點(diǎn)w與B中一點(diǎn)b相鄰。如果w

T，則(b,w)是穿越邊；否則(w,t)是穿越邊。因此，R(B)中每個(gè)點(diǎn)關(guān)聯(lián)至少一條穿越邊，其總數(shù)

|R(B)|

|B|=n–k。加上k條s到A的穿越邊，割的容量至少為n。

s

t

STBAR(B)bwwk條穿越邊|B|=n-k定理11.21證明(續(xù)）

設(shè)(S,T)是G’的一個(gè)割，U中點(diǎn)可分為二部分，一部分屬于T，另一部分屬于S，分別記作A

=T

U和B

=S

U。假設(shè)|A|=k，|B|=n-k。下圖顯示了集合A、B、以及R(B)與割(S,T)的關(guān)系。|A|=kUW58Birkhoff-vonNeuman定理這是Hall氏定理的一個(gè)應(yīng)用。定義11.15一個(gè)矩陣中任一元素的值不是0就是1，則稱(chēng)為0-1矩陣。如果一個(gè)n

n的0-1矩陣中每一行和每一列中正好有一個(gè)元素為1，而其余為0，則稱(chēng)為排列矩陣。一個(gè)n

n的排列矩陣可用一個(gè)n維向量

(a1,a2,…,an)表示，其中ai

(1

i

n)表示第i行中的值為1的元素所在的列的位置。顯然，a1,a2,…,an

是1,2,…,n的一個(gè)排列。例

(2,4,5,3,1)表示下面的一個(gè)5

5的排列矩陣。59

定理11.24(Birkhoff-vonNeuman定理)

任一個(gè)雙隨機(jī)矩陣等于某些排列矩陣的線性組合。證明：假設(shè)n

n的整數(shù)矩陣A={aij}滿足定義11.16中三個(gè)條件。我們對(duì)整數(shù)k進(jìn)行歸納證明。歸納基礎(chǔ)：當(dāng)k=1時(shí)，矩陣A本身就是一個(gè)排列矩陣，定理正確。(接下頁(yè))60

61

1110102101210101011100121=+++0100000100100000000100010100000100000010001000000100001010001000000010001000010000001010001000000010例：62注評(píng)：如果用定理11.24的證明方法去找一個(gè)雙隨機(jī)矩陣的分解，在k值很大時(shí)，會(huì)需要很長(zhǎng)時(shí)間。我們可以設(shè)計(jì)一個(gè)與k無(wú)關(guān)的算法。主要思路是，當(dāng)我們找到一個(gè)完美匹配和矩陣C時(shí)，因?yàn)閏ij=1意味著aij>0，我們可以找出最小的aij，其對(duì)應(yīng)的cij=1，即找到h=min{aij|cij=1}。那么矩陣D=A

–hC仍然是一個(gè)雙隨機(jī)矩陣，但是D比A至少多了一個(gè)為零的元素。因?yàn)锳中最多有n2個(gè)元素，經(jīng)過(guò)最多n2-n次匹配就可完成分解。因?yàn)槎繄D匹配需時(shí)O(n2.5)，因此將一個(gè)雙隨機(jī)矩陣分解為排列矩陣的線性組合的復(fù)雜度為O(n4.5)。63主要思路：把網(wǎng)絡(luò)中每條邊看成管道，我們從源點(diǎn)灌水到網(wǎng)絡(luò)中并把源點(diǎn)抬高，那么水會(huì)一直流向匯點(diǎn)t。我們要求流過(guò)管道的流量不超過(guò)其對(duì)應(yīng)邊的容量，但水可以在除源點(diǎn)s外的頂點(diǎn)處溢出，即流入該點(diǎn)的總流量大于從這點(diǎn)流出的總量。我們假設(shè)在各頂點(diǎn)有足夠大的蓄水池暫時(shí)存留溢出部分。當(dāng)流入?yún)R點(diǎn)t的流量增加到不能再增加時(shí)，我們?cè)侔岩绯龅捻旤c(diǎn)抬高使其溢出部分流回源點(diǎn)。剩余網(wǎng)絡(luò)Gf的定義與前面相同。5.推進(jìn)-重標(biāo)號(hào)算法簡(jiǎn)介64預(yù)流和高度函數(shù)定義11.17網(wǎng)絡(luò)G=(V,E)上的一個(gè)預(yù)流f就是給V

V中每個(gè)邊(u,v)賦以一個(gè)非負(fù)實(shí)數(shù)f(u,v)并滿足:0

f(u,v)

c(u,v)；除源點(diǎn)s和匯點(diǎn)t之外任一頂點(diǎn)u

V–{s,t},有f(V,u)

f(u,V)。預(yù)流和流的唯一區(qū)別是不要求流量守恒，而要求入流和大於或等于出流和。流量守恒的流稱(chēng)為正常流，它是預(yù)流的一個(gè)特例。除源點(diǎn)s和匯點(diǎn)t以外，入流和大於出流和的點(diǎn)u稱(chēng)為一個(gè)溢流點(diǎn)，而兩者之差e(u)=f(V,u)-f(u,V)稱(chēng)為溢流量。匯點(diǎn)

t不算溢流點(diǎn)。推進(jìn)-重標(biāo)號(hào)算法：不斷地對(duì)溢流點(diǎn)進(jìn)行兩個(gè)操作，即”預(yù)流推進(jìn)”和”高度重標(biāo)”。當(dāng)不再有溢流點(diǎn)時(shí)，預(yù)流就變?yōu)檎Ａ髁?。作溢流推進(jìn)時(shí)，要對(duì)有關(guān)邊的剩余容量做更新。為簡(jiǎn)潔，偽碼省絡(luò)容量更新的表述，認(rèn)為是包含在預(yù)流推進(jìn)操作中。下面介紹高度函數(shù)。65定義11.18預(yù)流f的剩余網(wǎng)絡(luò)Gf=(V,Ef)上的一個(gè)高度函數(shù)h就是給V中每個(gè)點(diǎn)v一個(gè)非負(fù)整數(shù)h(v)并滿足:源點(diǎn)s的高度始終是h(s)=n，匯點(diǎn)t的高度始終為h(t)=0，對(duì)Ef中任一條邊(u,v)，滿足關(guān)系h(u)

h(v)+1。注意，如果h(u)>h(v)+1，則邊(u,v)必不出現(xiàn)在剩余網(wǎng)絡(luò)Gf中。如果希望溢流從邊(u,v)流過(guò)，必須有h(u)=

h(v)+1。如果h(u)

h(v)，如何讓流從邊(u,v)流過(guò)呢？答案是，用重標(biāo)號(hào)算法抬高u的高度，使?jié)M足h(u)=

h(v)+1。

剩余網(wǎng)絡(luò)Gf的定義與前面相同。下面介紹算法對(duì)網(wǎng)絡(luò)G中溢流點(diǎn)的兩個(gè)操作。66預(yù)流推進(jìn)，Push(u,v)，操作Push(u,v)操作的3條件：e(u)>0，cf(u,v)

>0，h(u)=h(v)+1。偽碼: Push(u,v)

f

min(e(u),cf(u,v)) //可以從u推到v的最大流量

(u,v)

(u,v)+

f

//邊(u,v)上相對(duì)預(yù)流增加

f

(v,u)

-

(u,v)

//提醒，包括更新cf(u,v)和cf(v,u)e(u)

e(u)-

f

//更新u和v的溢流量e(v)

e(v)+

f //如果v

s

和v

t，v成為溢流點(diǎn)End如果

f=cf(u,v)，稱(chēng)飽和推進(jìn)，

(u,v)在Gf中消失，(v,u)在Gf中出現(xiàn)。如果

f

<cf(u,v)，稱(chēng)非飽和推進(jìn)，

u成為非溢流點(diǎn)，(v,u)在Gf中出現(xiàn)。點(diǎn)v成為溢流點(diǎn)(也許原來(lái)就是)。預(yù)流仍然是合法預(yù)流。各點(diǎn)的高度未變，仍然滿足高度函數(shù)要求。流量的推進(jìn)是在網(wǎng)絡(luò)G中進(jìn)行。剩余容量的更新在Gf中進(jìn)行。67高度重標(biāo)操作高度重標(biāo)操作條件:頂點(diǎn)u是一個(gè)溢流點(diǎn)，e(u)>0。(2) Gf中頂點(diǎn)u的每個(gè)鄰居v，邊(u,v)只滿足h(u)

h(v)，不滿足 h(u)=h(v)+1。

偽碼：

Relabel(u)h(u)

1+min{h(v)|(u,v)

Ef} //鄰居中最低高度加1End溢流點(diǎn)u在Gf中一定有出去的邊，因?yàn)閑(u)>0，必有邊(v,u)

E使得f(v,u)>0，因而有cf(u,v)>0。高度函數(shù)在重標(biāo)后仍是高度函數(shù)。這因?yàn)?，從u出去的邊(u,v)仍有h(u)

h(v)+1，而進(jìn)入u的邊(w,u)更滿足h(w)

h(u)+1。68推進(jìn)-重標(biāo)號(hào)算法的初始化Initialize-Preflow(G(V,E),s)foreachu

V

//置每個(gè)點(diǎn)的高度為0，溢流為0

h(u)

e(u)

0endforforeach(u,v)

E

//置每條邊的預(yù)流為0(賦以相對(duì)流)

(u,v)

(v,u)

0，cf(u,v)

c(u,v) //分別在G和Gf中進(jìn)行endforh(s)

n

//改置源點(diǎn)高度為n=|V|foreachv

Adj(s) //更改s出去的邊上的預(yù)流

(s,v)

c(s,v)

//包括更新cf(c,v)

(v,s)

-c(s,v) //包括更新cf(v,s)

e(v)

c(s,v) //點(diǎn)v是溢流點(diǎn)

e(s)

e(s)-c(s,v) //

e(s)是負(fù)數(shù)，s是唯一虧流點(diǎn)endforEnd69推進(jìn)-重標(biāo)號(hào)的通用算法(1)

通用算法簡(jiǎn)介：初始化后，預(yù)流和高度函數(shù)均符合定義，可開(kāi)始兩個(gè)操作。以任何順序操作都可以得到最大流，故稱(chēng)為通用算法。通用算法的復(fù)雜度較高，為O(mn2)。(2) 通用算法的偽碼：Generic-Push-Relabel(G(V,E),s,t)Initialize-Preflow(G(V,E),s)while

usuchthate(u)>0

//只要有溢流點(diǎn)u

if

vsuchthat((u,v)

Gfandh(u)=h(v)+1)

thenPush(u,v) //u有鄰居v并有h(u)=h(v)+1

elseRelabel(u)

endifendwhileEnd70通用算法的正確性證明引理11.23假設(shè)f是通用算法運(yùn)算過(guò)程中G(V,E)的一個(gè)預(yù)流，而h是一個(gè)高度函數(shù)，那么在剩余網(wǎng)絡(luò)Gf中，不存在一條從s到t的路徑。證明：反證法證明。假設(shè)Gf中有一條從s到t的簡(jiǎn)單路徑，v0,v1,…,vk，這里v0

=s，vk=t。我們證明這會(huì)導(dǎo)致矛盾。因?yàn)槁窂缴先我粭l邊(vi,vi+1)

(i

=0,1,…,k-1)

必須滿足高度要求，即h(vi)

h(vi+1)+1,所以有h(s)

h(v1)+1

h(v2)+2

…

h(vk)+k=h(t)+k。又因?yàn)閔(s)=n

和h(t)=0，我們得到n

k。這說(shuō)明這條路徑至少含有k+1

n+1個(gè)不同頂點(diǎn)，這不可能，所以剩余圖Gf中不存在一條從s到t的路徑。

71由上面討論知，每次預(yù)流推進(jìn)或高度重標(biāo)的操作之后，高度函數(shù)仍然是合法的高度函數(shù)，所以，一旦在某次操作后網(wǎng)絡(luò)中沒(méi)有溢流點(diǎn)，那么預(yù)流f就變成了正常流f，而且是最大流。它是最大流的原因是，由引理12.25，剩余圖Gf中不存在一條從s到t的路徑，也就是沒(méi)有增廣路徑。因此，只要我們能證明溢流點(diǎn)一定會(huì)在某次操作后全部消失，那么算法Generic-Push-Relabel就是正確的。又