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

1第11章

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

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

11Ford-Fulkerson方法

24Ford-Fulkerson通用方法

24Edmonds-Karp算法

30Dinic算法

36二部圖的匹配問題

44推進-重標號算法簡介

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

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

E

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

E當且僅當c(u,v)=0。另外，圖中有兩個指定的頂點，分別稱為源點和匯點，通常標記為s

和t。例11.1v115124916582637sv2v3v4t3

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

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

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

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

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

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

。

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

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

分別表示流和相對流。6

7

8

9

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

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

f計算對應(yīng)于

f的相對流

:

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

計算對應(yīng)于

的規(guī)范流f:

f(u,v)=max{0,

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

中所有

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

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

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

(u,v)

f(u,v)

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

我們可類似地定義最大相對流問題，并且等價于最大流問題。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)的一個流，

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

邊(u,v)

V

V

的容量為

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

(u,v)，稱為對應(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)生的(相對)容量。16v110/154/45/80/3sv25/120/99/165/50/25/64/7v3v4t(a)

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

對應(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)的時間是O(|V|+|E|)。17定理11.7

設(shè)f和

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

的一個流及相對流，而f’和

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

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

*(u,v)=

(u,v)+

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

=f+f’。

18

流f*可以通過

*=

+

’來計算。但是，f*也可以從f

和f’直接計算，增廣流f*的計算規(guī)則：(設(shè)f,f’都是規(guī)范流，容易驗證)(A) f(u,v)>0，f(v,u)=0 (對稱情況：(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的一個流。剩余網(wǎng)絡(luò)Gf

中一條從源點s到匯點t的簡單路徑p稱為一條增廣路徑(augmentingpath)。這條路徑上剩余容量最小的邊稱為關(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怎樣計算f*(u,v)和f*(v,u)前面，在定理11.7之后，我們介紹過從

f和

fp直接計算增廣流f*的規(guī)則。為方便對后面?zhèn)未a的理解，針對增廣路徑流，我們給出從f和cf(p)直接計算增廣流f*的規(guī)則如下，并給出簡單解釋。假定網(wǎng)絡(luò)G上的流f是規(guī)范流。(見下頁)21基于路徑p的增廣流f*的計算規(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。這是因為:

(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。這是因為

(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)。(解釋：要增加u到v的流cf

(p)，就相當于減少從v到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)。(解釋：要增加u到v的流cf

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

定理11.9

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

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

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

=V–S。因為Gf中不存在從s到t的路徑，s

S

而t

T。顯然，Gf

中沒有從S中任一點到T中任一點的邊。這說明，網(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|小于等于任何一個割的容量，因此c(S,T)也小于等于任何一個割的容量。所以，c(S,T)的容量是最小的。

23

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

先給每條邊(u,v)

E

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

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

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

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

foreachedge(u,v)

E；f(u,v)0endfor //初始流為0(接下頁)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我們稱上面的算法為通用算法是因為它沒有指定用什么方法去找增廣路徑p，只要找到一條就行。讓我們看一個例子。27例11.7用Ford-Fulkerson方法找出下面網(wǎng)絡(luò)的一個最大流。請圖示每輪中的剩余網(wǎng)絡(luò)，所用增廣路徑，以及對應(yīng)的增廣流。sv1v2v3v45412181376109t19解：下面圖(11-7)中每一對小圖對應(yīng)一輪計算。左邊顯示的是對應(yīng)于上一輪增廣流(第一對是初始流)的剩余網(wǎng)絡(luò)及它的一條增廣路徑。右邊顯示的是基于這條路徑的增廣流。最后一輪中的剩余網(wǎng)絡(luò)中沒有增廣路徑，因而只有一個小圖，計算結(jié)束。這時，前一輪中(圖(h))的增廣流就是最大流，流量是|f|=23。另外，它對應(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最大流見圖(h)，|f|=23。最小割是S={s,v1,v2,v4}，T={v3,t}13107101316330Edmonds-Karp算法(改進的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

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

的距離，

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

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

f(s,v)和

f(v,t)。證明：因為

f*(v,t)

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

f*(s,v)

f(s,v)。我們對

f*(s,v)的長度k進行歸納證明。歸納基礎(chǔ)：當

f*(s,v)=k=0時，必有v=s，因為

f*(s,s)=

f(s,s)=0，所以

f*(s,v)

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

f*(s,v)

k(k

0)，就有

f*(s,v)

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

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

f*(s,v)

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

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

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

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

f*(s,u)

f(s,u)，那么在Gf中有一條從s經(jīng)過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)。(接下頁)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)因為路徑p’也提供了一條Gf中從s到v的最短路徑。下圖(11-10)顯示了這樣一條路徑，并同時顯示了一條在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

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

f(s,u)+1+

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

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

f’(s,u)=

f’(s,v)+1。(接下頁)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不會超過

n/2。因為圖中有m條邊，一共可以提供最多

mn/2

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

mn/2

次。

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

mn/2

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

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

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

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

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

Graph)，其中V

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

E|

(s,v)=

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

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

(s,v)

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

(s,v)=

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

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

一個有向圖Gabcegfdabcegfd

=0

=1

=1

=2

=2

=2

=3(b)

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

(u,v)

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

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

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

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

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

LG(V,E’,s)中流增廣，并把飽和邊標以“阻塞”?！白枞边呍谝院蟮腄FS搜索中不再使用。然后，重新開始以s為起點的DFS搜索。當前訪問的頂點v沒有出去的邊或者所有的出邊都已阻塞。這時，沒有任何路經(jīng)可以通過v而到達t。把v從堆棧彈出，回溯到v的父親u后繼續(xù)當前的DFS搜索，并把(u,v)標以“阻塞”。當從s出去的邊都被阻塞時，阻塞流算法也停止。因為O(n)時間至少有一邊會標阻塞，一共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ù)雜度因為每一次循環(huán)(稱為一輪)的主要工作是為層次圖找一個阻塞流，時間已知為O(mn)，所以我們需要對循環(huán)次數(shù)作出分析。引理11.14Dinic算法中每一輪循環(huán)后的層次圖中s到t的路徑長度比前一輪層次圖中的長度至少多一條邊。證明：假設(shè)f是某次循環(huán)前網(wǎng)絡(luò)G中的流，其層次圖是LGf。循環(huán)后得到阻塞流f’，并由此把G中流增廣為f*=f+f’。假設(shè)對應(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的路徑。因為LGf中飽和邊不在LGf*中，所以p中有邊不在LGf中，否則，p的每條邊都是LGf中非飽和邊而使p成為LGf中的增廣路徑，這與f’是阻塞流矛盾。(接下頁)42引理11.14證明(繼續(xù))：設(shè)邊(u,v)

p

但不出現(xiàn)在LGf中。原因只有兩種：(a) (v,u)出現(xiàn)在LGf上并有f’(v,u)>0。這時，在LGf中必有從s到t的路徑經(jīng)過(v,u)。因阻塞流f’是由等長的最短路徑增廣而得，由引理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中，是因為它在計算LGf時被刪去，但在計算LGf*時被用上。那么必定有

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算法最多需要計算n

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

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

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

n–1。因而有k

n–2。

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

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

444.二部圖的匹配問題定義11.13如果M

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

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

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

代表工作ti(1

i

n)。用

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

代表pj(1

j

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

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

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

Ef

，但(v,u)

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

Ef，但(v,u)

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

48引理11.18

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

49

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

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

U

W

{s,t} //圖的頂點加上源點s和匯點tE’

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

E,u

U,w

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

E’

{(s,u)|u

U} //加上從s到U中點u的一條邊E’

E’

{(w,t)|v

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

E’

c(x,y)

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

M，則賦以f(s,u)=1,f(u,w)=1和f(w,t)=1，而其他的邊則賦以零。因為匹配中的邊不共頂點，這顯然是一個合法的整數(shù)流，而且有|f|=|M|。下圖顯示了對應(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如下：(接下頁)圖11-13(a)中，M

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

如果邊(s,u)上有流f(s,u)=1，那么因為單分支網(wǎng)絡(luò)的特點，必定存在頂點w

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

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

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

U，均有|B|

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

W

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

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

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

=n，定理得證。如k

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

T，則(b,w)是穿越邊；否則(w,t)是穿越邊。因此，R(B)中每個點關(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’的一個割，U中點可分為二部分，一部分屬于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氏定理的一個應(yīng)用。定義11.15一個矩陣中任一元素的值不是0就是1，則稱為0-1矩陣。如果一個n

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

n的排列矩陣可用一個n維向量

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

(1

i

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

是1,2,…,n的一個排列。例

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

5的排列矩陣。59

定理11.24(Birkhoff-vonNeuman定理)

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

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

61

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

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

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

f(u,v)

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

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

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

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

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

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

h(v)+1。

剩余網(wǎng)絡(luò)Gf的定義與前面相同。下面介紹算法對網(wǎng)絡(luò)G中溢流點的兩個操作。66預(yù)流推進，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)上相對預(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成為溢流點End如果

f=cf(u,v)，稱飽和推進，

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

f

<cf(u,v)，稱非飽和推進，

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

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

偽碼：

Relabel(u)h(u)

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

Ef} //鄰居中最低高度加1End溢流點u在Gf中一定有出去的邊，因為e(u)>0，必有邊(v,u)

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

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

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

V

//置每個點的高度為0，溢流為0

h(u)

e(u)

0endforforeach(u,v)

E

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

(u,v)

(v,u)

0，cf(u,v)

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

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) //點v是溢流點

e(s)

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

e(s)是負數(shù)，s是唯一虧流點endforEnd69推進-重標號的通用算法(1)

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

usuchthate(u)>0

//只要有溢流點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是通用算法運算過程中G(V,E)的一個預(yù)流，而h是一個高度函數(shù)，那么在剩余網(wǎng)絡(luò)Gf中，不存在一條從s到t的路徑。證明：反證法證明。假設(shè)Gf中有一條從s到t的簡單路徑，v0,v1,…,vk，這里v0

=s，vk=t。我們證明這會導(dǎo)致矛盾。因為路徑上任一條邊(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。又因為h(s)=n

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

k。這說明這條路徑至少含有k+1

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

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