[邊覆蓋]

一個(gè)圖G=(V,E)，EE，若G的任一個(gè)頂點(diǎn)都與E

中的邊關(guān)聯(lián)，則稱E覆蓋G，或稱E

為G的一個(gè)邊覆蓋（集）。

E為G的一個(gè)邊覆蓋

EE(u)(uV(e)(e=(v,w)E(v=uw=u)))[極小邊覆蓋]

E是G的一個(gè)極小邊覆蓋

E為G的一個(gè)邊覆蓋(E1)(E1EE1不是G的邊覆蓋)8.1匹配的基本概念[邊覆蓋數(shù)]

設(shè)G的所有邊覆蓋為E1、E2、…、Ek，記稱為G的邊覆蓋數(shù)。[最小邊覆蓋]

Ei

稱為G的一個(gè)最小邊覆蓋若|Ei|=1。8.1匹配的基本概念[匹配]

G的一個(gè)任意兩邊不相鄰的邊集合M稱為G的一個(gè)邊獨(dú)立集或匹配。[極大匹配]

M是G的一個(gè)極大匹配

M為G的一個(gè)匹配(e)(eEMM{e}不是G的匹配)[匹配數(shù)]

設(shè)G的所有匹配為M1、M2、…、Mk，記稱為G的匹配數(shù)。[最大匹配]

Mi

稱為G的一個(gè)最大匹配若|Mi|=1。8.1匹配的基本概念[例][M-飽和頂點(diǎn)]

設(shè)M是G的一個(gè)匹配，e=(vi,vj)E。若有eM，則稱vi和vj

在M中飽和或是M飽和的。所有關(guān)聯(lián)邊都不在M中的頂點(diǎn)稱為非M-飽和頂點(diǎn)或是M-不飽和的。若G中的每一個(gè)頂點(diǎn)都是M飽和的，則稱M為G的一個(gè)完美匹配。e1e2e3e4e5e6e7極大匹配：{e1,e4}最大匹配：{e1,e5

,e6}匹配數(shù)：38.1匹配的基本概念[定理8-1-1]

設(shè)M是G=(V,E)的一個(gè)匹配，n=|V|，且G中無(wú)孤立點(diǎn)：

(1)設(shè)M為G的一個(gè)最大匹配，對(duì)G中每一個(gè)M不飽和頂點(diǎn)取一條關(guān)聯(lián)邊，組成邊集N，則W=MN為G的一個(gè)最小邊覆蓋。

(2)設(shè)W1為G的一個(gè)最小邊覆蓋，將W1中每相鄰的邊移去一條，設(shè)移去的邊構(gòu)成邊集N1，則M1=W1N1為G的一個(gè)最大匹配。

(3)1(G)+1(G)=n

。8.1匹配的基本概念[證明](1)G中的M-飽和頂點(diǎn)數(shù)=2|M|，故G中的M-不飽和頂點(diǎn)數(shù)=n2|M|。對(duì)任一M-不飽和頂點(diǎn)

u，由于G中無(wú)孤立點(diǎn)，必有vV

與u鄰接，e=(u,v)E

為構(gòu)成N的一條邊。此時(shí)eM，否則u

是M-飽和的。且v

必為M-飽和的，否則M{e}形成一個(gè)更大的匹配，與M是一個(gè)最大匹配矛盾?？梢?，G中的任一個(gè)M-不飽和頂點(diǎn)對(duì)應(yīng)了一條N中的邊，且MN=。故有：|N|=n2|M|，且

|W|=|MN|=|M|+|N|=|M|+n2|M|=n|M|

又M為一個(gè)最大匹配：|M|=1(G)

故有：|W|=n18.1匹配的基本概念

(2)考察N1和M1的構(gòu)造過(guò)程。易知M1中不存在相鄰邊，即M1是G的一個(gè)匹配。對(duì)任意的e=(u,v)W1：

①如果e在G中的任何相鄰邊都不屬于W1，則e與N1的形成無(wú)關(guān)。

②如果e在G中有兩條相鄰邊e=(r,v)和e=(u,t)如下圖，則

e和e不能同時(shí)屬于W1，否則

W1

{e}構(gòu)成G的一個(gè)更小的覆蓋，與W1是G的一個(gè)最小覆蓋矛盾。eeeruvtW18.1匹配的基本概念eeruvtW1{e}

③不失一般性，設(shè)eW1，eW1。此時(shí)作類似分析可知，e若存在相鄰邊e=(r,s)，必有

eW1。將e

或e移到N1中，可得到一個(gè)M1-不飽和頂點(diǎn)u

或r

?？梢?，一條N1中的邊對(duì)應(yīng)了一個(gè)M1-不飽和頂點(diǎn)，故有：|N1|=n2|M1|。因此：|W1|=|M1|+|N1|=|M1|+n2|M1|=n|M1|

又：W1為一個(gè)最小覆蓋，|W1|=1(G)

故：1=n|M1|8.1匹配的基本概念eeeruvtW1es

(3)M1是G的一個(gè)匹配，故有：|M1|1?；?|M1|

由(1)：|W|=n1n|M1|

由(2)：1=n|M1|

故|W|1。而W是G的一個(gè)覆蓋，|W|1。故|W|=1，即W是G的一個(gè)最小覆蓋?？紤]到|W|=n1，故有1=n1

即有1+1=n

考慮到1=n|M1|即|M1|=n1

故|M1|=1。即M1為G的一個(gè)最大匹配。8.1匹配的基本概念[推論]

設(shè)G=(V,E)無(wú)孤立點(diǎn)，M為G中匹配，W為G中邊覆蓋，則|M||W|。當(dāng)|M|=|W|時(shí)，W為G中的最小邊覆蓋，M為G中的完美匹配。[證明]設(shè)M是G的一個(gè)最大匹配，按照[定理8-1-1](1)構(gòu)造N，則W=MN是G的一個(gè)最小覆蓋。將|M|=1(G)，|W|=1(G)，代入上式得：

1=|W|=|MN|=|M|+|N|=1+|N|.

故11

。又|M|1

，|W|

1

故|M|11|W|

當(dāng)|M|=|W|時(shí)，上述等號(hào)成立，即|M|=

1=1=|W|G中M-非飽和頂點(diǎn)數(shù)=n2|M|=n21=n(1+1)=nn=0

即M是G的一個(gè)完美匹配。8.1匹配的基本概念[M交互道]

設(shè)G和M如上所述，G的一條M交互道指G中一條路，其中的邊在M和EM中交錯(cuò)出現(xiàn)。[M可增廣道]

設(shè)G和M如上所述，若G的一條M交互道的始點(diǎn)和終點(diǎn)都是M不飽和的，則稱該M交互道為一條M可增廣道。8.2最大匹配的基本定理[例]

圖中紅邊構(gòu)成匹配Ｍ。M-交互道8.2最大匹配的基本定理非M-可增廣道M-可增廣道M-交互道[定理8-2-1]

設(shè)G=(V,E)，M為G中匹配，則M為G的最大匹配當(dāng)且僅當(dāng)

G中不存在M可增廣道。(Berge)[證明]設(shè)G中存在一條M-可增廣道P=(v0v1…

v2k+1)，其中

P1={(v1,v2),(v3,v4),…,(v2k-1,v2k)}M，|P1|=kP2={(v0,v1),(v2,v3),…,(v2k,v2k+1)}EM，|P2|=k+1

對(duì)P中的任一M-飽和頂點(diǎn)vi

，其所有關(guān)聯(lián)邊中只有在P1中列明的才屬于M（M的獨(dú)立性）。故對(duì)于匹配(MP1)，P中頂點(diǎn)都是(MP1)-不飽和的。因此可以構(gòu)造M=(MP1)P2（或記為MP），此時(shí)M

是G的一個(gè)匹配，且|M|=|M+1，與M是G的一個(gè)最大匹配矛盾。8.2最大匹配的基本定理

設(shè)M不是G的一個(gè)最大匹配。設(shè)G中另有一個(gè)最大匹配M。構(gòu)造H=MM=NN，其中N=M(MM)，N=M(MM)。由|M|>|M|可得|N|>|N|。考察由H及其關(guān)聯(lián)頂點(diǎn)構(gòu)成的子圖G(H)，其任一頂點(diǎn)或只與N中的一條邊關(guān)聯(lián)，或只與N中的一條邊關(guān)聯(lián)，或同時(shí)與N和N中各一條邊關(guān)聯(lián)。故G(H)中的每一個(gè)連通分支都是在N和N中交錯(cuò)的路或回路，也是G中的一條M-交互道。

再由|N|>|N|得知，這些連通分支不能全部是回路，至少有一個(gè)連通分支是一條始于N的邊且終于N的邊的路。該路是G中的一條M-可增廣道，與條件矛盾。8.2最大匹配的基本定理[二部圖的完全匹配]

記二部圖為G=(X,Y,E)，|X||Y|，當(dāng)X中頂點(diǎn)在匹配M中全部飽和時(shí)，稱M為G的一個(gè)完全匹配。[定理8-2-2](Hall

婚姻定理)

二部圖G=(X,Y,E)，|X||Y|，存在完全匹配的充要條件是：對(duì)任意AX，有|(A)||A|。(A)為A在Y中的像：(A)={y|yYx(xA(x,y)E)}

（條件也稱為相異性條件）。[證明]設(shè)G存在完全匹配M，則X中所有頂點(diǎn)是M-飽和的。對(duì)任一xX，存在唯一的yY，使得(x,y)M。而且對(duì)此y，若有(x,y)M，則必x=x（M的獨(dú)立性）。故對(duì)任意AX，有|(A)||A|。8.2最大匹配的基本定理

設(shè)對(duì)任意AX，有|(A)||A|。欲證存在完全匹配。對(duì)n=|X|作歸納。

(1)n=1時(shí)，|A|=1，|(A)|1，結(jié)論顯然成立。

(2)設(shè)nk1時(shí)，結(jié)論成立。

(3)當(dāng)n=k時(shí)，分兩種情況討論：①G中對(duì)任意AX，有|A|<|(A)|。此時(shí)任取x0X，依條件有

|({x0})||{x0}|,或|({x0})|1,即有

(x0,y0)E。構(gòu)造G=(X,Y,E)，其中：

X=X{x0}，|X|=k1；

Y=Y{y0}；

E={(x,y)|xXyY(x,y)E}。8.2最大匹配的基本定理對(duì)任意AX,依①條件有|A|<|(A)|。由于Y=Y{y0},在G中，當(dāng)y0(A)時(shí)，有|(A)|=|(A)|（對(duì)應(yīng)G的映像）；否則

|(A)|=|(A)|1。故|A||(A)|。綜上，G符合歸納假設(shè)的條件，即G中存在完全匹配M。構(gòu)造M{(x0,y0)}，形成G中的一個(gè)完全匹配。②G中存在A0X，使得|A0|=|(A0)|。 構(gòu)造G=(X,Y,E)，其中：X=A0，Y=(A0)，

E={(x,y)|xXyY(x,y)E}

構(gòu)造G=(X,Y,E)，其中：X=XA0，Y=Y(A0)，

E={(x,y)|xXyY(x,y)E}8.2最大匹配的基本定理對(duì)G： 給定任意的AX=A0X，依條件有|A||(A)|，由Y的定義，G中保持了原G中關(guān)于A0的映像。因此對(duì)于AA0，有

|(A)|=|(A)|。 故|A||(A)|。 又|X|=|A0|<|X|=k

或|X|k1，G符合歸納假設(shè)的條件。 即G中存在一個(gè)從A0到(A0)的完全匹配M1。8.2最大匹配的基本定理對(duì)G： 給定任意的AX=XA0，有AA0X，依條件有

|AA0||(AA0)|， 而 |AA0|=|A|+|A0|，

由Y的定義知：|(AA0)|=|(A)|+|(A0)|

故 |A|+|A0||(A)|+|(A0)|，但|A0|=|(A0)|

故 |A||(A)|。又|X|<|X|=k

或|X|k1，G符合歸納假設(shè)的條件。 即G中存在一個(gè)從XA0到Y(jié)(A0)的完全匹配M2。構(gòu)造M=M1M2，M即為

n=k

時(shí)G中的一個(gè)完全匹配。由歸納原理，結(jié)論成立。8.2最大匹配的基本定理[推論]

設(shè)有二部圖G=(X,Y,E)，若對(duì)每個(gè)結(jié)點(diǎn)

xX，都有deg(x)k；對(duì)每個(gè)結(jié)點(diǎn)yY，都有deg(y)k，則G中存在從X到Y(jié)的完全匹配。[證明]

任取AX，對(duì)每個(gè)結(jié)點(diǎn)xA，都有deg(x)k，且A中結(jié)點(diǎn)各不相鄰，故若設(shè)A與Y的聯(lián)接邊數(shù)為p，則有pk|A|。又對(duì)每個(gè)結(jié)點(diǎn)y(A)，都有deg(y)k，且(A)中結(jié)點(diǎn)各不相鄰，故若設(shè)(A)與X的聯(lián)接邊數(shù)為q，則有qk|(A)|。顯然p=q，故k|(A)|k|A|，即|(A)||A|。由[定理8.2.2]，G中存在一個(gè)從X到Y(jié)的完全匹配。8.2最大匹配的基本定理[討論]當(dāng)存在AX，使得

|A|>|(A)|時(shí)，不可能有A到(A)的完全匹配。定義A的缺數(shù)(A)=max{|A||(A)|,0}。定義(G)=max{(A)|AG}。Hall定理討論了(G)=0的情形。當(dāng)(G)>0時(shí)，有|M|

|X|(G)，即為匹配數(shù)的上限。Konig

證明了此上限也是二部圖的最大匹配數(shù)。8.2最大匹配的基本定理[算法]

尋求二部圖的可增廣道的匈牙利算法（Edmonds）設(shè)二部圖(X,Y,E)，標(biāo)志I、II分別表示飽和點(diǎn)和無(wú)法匹配點(diǎn)。初始化時(shí)所有頂點(diǎn)沒(méi)有標(biāo)志。

1.

任意給定一個(gè)初始匹配M，給所有M飽和頂點(diǎn)標(biāo)記I；

2.

判定X中各點(diǎn)已有標(biāo)志？

2.1是。M已經(jīng)是最大匹配，算法結(jié)束。

2.2否。找到一個(gè)未標(biāo)記點(diǎn)x0X,U{x0},V

。

8.3最大匹配算法3.判定(U)=V?3.1

是，無(wú)法擴(kuò)大匹配。x0標(biāo)記為II，轉(zhuǎn)[2]。

3.2

否。找到y(tǒng)(U)V，判定y

已標(biāo)記為I？

3.2.1

是。即有(z,y)M，令

UU{z}，VV{y}，轉(zhuǎn)[3]。

3.2.3

否。存在從x0y

的可增廣道P。給x0,y以標(biāo)志I，MMP,轉(zhuǎn)[2]。[計(jì)算復(fù)雜度分析]

算法最多找n條增廣路，每條增廣道最多處理m

條邊，故計(jì)算復(fù)雜度為O(mn)。8.3最大匹配算法[例]如圖，設(shè)初始匹配{(x1,y1),(x3,y4),(x4,y5)}8.3最大匹配算法

(1)U={x2}，V=。(U)={y4,y6} y6 (U)V，且無(wú)標(biāo)記。故存在從x2到y(tǒng)6的可增廣道。 找到一條可增廣道P=(x2,y6)。將x2、y6標(biāo)記I。

M={(x1,y1),(x3,y4),(x4,y5),(x2,y6)}。x1x2x3x4x5x6y1y2y3y4y5y6x1x2x3x4x5x6y1y2y3y4y5y6■未標(biāo)記■

標(biāo)記I■

標(biāo)記II8.3最大匹配算法

(2)U={x5}，V=。(U)={y5,y6} y5(U)V，且有標(biāo)記I：(x4,y5)M。

U={x5,x4}，V={y5}。(U)={y5,y6} y6(U)V，且有標(biāo)記I：(x2,y6)M。

U={x5,x4,x2}，V={y5,y6}。(U)={y5,y6,y4} y4(U)V，且有標(biāo)記I：(x3,y4)M。x1x2x3x4x5x6y1y2y3y4y5y68.3最大匹配算法

U={x5,x4,x2,x3}，V={y5,y6,y4}。(U)={y5,y6,y4,y2} y2(U)V，且無(wú)標(biāo)記。故存在從x5到y(tǒng)2的可增廣道。 找到一條可增廣道P=(x5,y6,x2,y4,x3,y2)。將x5、y2標(biāo)記I。

M={(x1,y1),(x4,y5),(x5,y6),(x2,y4),(x3,y2)}。x1x2x3x4x5x6y1y2y3y4y5y6x1x2x3x4x5x6y1y2y3y4y5y68.3最大匹配算法

(3)U={x6}，V=。(U)={y6} y6(U)V，且有標(biāo)記：(x5,y6)M。

U={x6,x5}，V={y6}。(U)={y6,y5} y5(U)V，且有標(biāo)記：(x4,y5)M。

U={x6,x5,x4}，V={y6,y5}。(U)={y6,y5}

(U)=V，給x6標(biāo)記II。x1x2x3x4x5x6y1y2y3y4y5y6x1x2x3x4x5x6y1y2y3y4y5y68.3最大匹配算法

(4)X中各點(diǎn)均已有標(biāo)志。M已經(jīng)是最大匹配，算法結(jié)束。x1x2x3x4x5x6y1y2y3y4y5y6[練習(xí)]如圖，設(shè)初始匹配{(x2,y2),(x3,y3),(x5,y5)}8.3最大匹配算法

(1)U={x1}，V=。(U)={y2,y3} y2(U)V，且有標(biāo)記：(x2,y2)M。

U={x1,x2}，V={y2}。(U)={y2,y3,y1,y4,y5} y1(U)V，且未標(biāo)記，故存在從x1到y(tǒng)1的可增廣道。 找到一條可增廣道P=(x1,y2,x2,y1)。將x1、y1標(biāo)記I。

M={(x1,y1),(x2,y2),(x3,y3),(x5,y5)}。■未標(biāo)記■

標(biāo)記I■

標(biāo)記IIx1x2x3x4x5y1y2y3y4y5[進(jìn)一步的討論]Konig

定理：對(duì)二部圖，最大匹配數(shù)=最小頂點(diǎn)覆蓋數(shù)。帶權(quán)完全二部圖Kn,n

的最佳匹配算法（Kuhn-Munkres

標(biāo)號(hào)法）。最小成本算法。8.3最大匹配算法[網(wǎng)絡(luò)]

設(shè)無(wú)回路有向連通圖N=(V,A)，在A上定義非負(fù)實(shí)函數(shù)C，使得：N中有且只有一個(gè)入度為0的點(diǎn)z和一個(gè)出度為0的點(diǎn)z，分別稱為源和匯；任意的邊aijA，都被賦以實(shí)權(quán)

cij

0，稱為aij

的容量。稱這樣的N為一個(gè)網(wǎng)絡(luò)（運(yùn)輸網(wǎng)絡(luò)）。8.4網(wǎng)絡(luò)流圖與最大流[例]

下圖是一個(gè)網(wǎng)絡(luò)。8.4網(wǎng)絡(luò)流圖與最大流這里的網(wǎng)絡(luò)也稱“網(wǎng)絡(luò)流圖”，是一個(gè)DAG。注意和“作業(yè)網(wǎng)絡(luò)”的區(qū)分。[容許流]

網(wǎng)絡(luò)N=(V,A)的容許流（簡(jiǎn)稱流）是A上的一個(gè)非負(fù)實(shí)函數(shù)f，滿足：網(wǎng)絡(luò)N中至少有一個(gè)流f=0（零流）8.4網(wǎng)絡(luò)流圖與最大流注意到無(wú)回路假設(shè)：當(dāng)圖中存在回路時(shí)，可能在回路中形成“渦流”，其流動(dòng)性不能在流量中體現(xiàn)。[定理8-4-1]

給定網(wǎng)絡(luò)N=(V,A)的一個(gè)流

f，源點(diǎn)z的流出量等于匯點(diǎn)z的流入量，即：[證明]

考察恒等式

記fij=0當(dāng)aijA，上述恒等式寫成：8.4網(wǎng)絡(luò)流圖與最大流

由源點(diǎn)z和匯點(diǎn)z的定義以及守恒條件得：故上式化簡(jiǎn)為即：8.4網(wǎng)絡(luò)流圖與最大流[流量]

設(shè)f是網(wǎng)絡(luò)N=(V,A)的一個(gè)流，其流量定義為：[最大流]記最大流量具有最大流量的流fmax稱為N的一個(gè)最大流。8.4網(wǎng)絡(luò)流圖與最大流[割切]

網(wǎng)絡(luò)N=(V,A)，z

和z

分別是網(wǎng)絡(luò)的源和匯，設(shè)SV，S=VS，滿足zS，zS。定義：

(S,S)={aij

|aij

=

(vi,

vj)A,viS,vjS}A

稱為N的一個(gè)割切。割切的容量c(S,S)=cij,對(duì)所有的aij(S,S)

割切的流量f(S,S)=fij,對(duì)所有的aij(S,S)顯然有f(S,S)c(S,S)8.5割切[定理8-5-1]

設(shè)網(wǎng)絡(luò)N中一個(gè)從z到z

的流f的流量為w,(S,S)為任意一個(gè)割切，則w=f(S,S)

f(S,S)由和[證明]記fij=0當(dāng)aij=A，則：得8.5割切對(duì)割切(S,S)又兩式相減得8.5割切[推論1]

對(duì)網(wǎng)絡(luò)N中任意流量w和割切(S,S)，有

wc(S,S)。[證明]w=f(S,S)

f(S,S)f(S,S)c(S,S)[推論2]

最大流量不大于最小割切容量，即：

wmaxmin{c(S,S)}。[證明]由推論1直接得到。8.5割切[定義]

網(wǎng)絡(luò)N=(V,A)，設(shè)有弱連通初等道路

P=(v1,v2,…,vk)，viA，i=1..k

對(duì)1ik1，若<vi

,vi+1>A，i=1..(k1)，則稱<vi,vi+1>為前向弧，否則（即<vi+1,vi>A）稱之為后向弧。對(duì)N的一個(gè)流f，若<vi,vi+1>

為前向弧，則定義i,i+1(P)=ci,i+1

–fi,i+1；若<vi,vi+1>

為后向弧，則定義i,i+1(P)=fi,i+1。并令

(P)=min{ij(P)}。(P)=0時(shí)，稱P是f-飽和的，否則稱P是f-非飽和的。(P)為在滿足流f的容許條件下沿P

增加的流量的最大值。增量的方法是將P上的前向弧+

，后向弧，則當(dāng)P為zz

時(shí)，增量后的流量w=

fzi=fzi

+=w+8.6最大流最小割定理[f可增路]

設(shè)N、f

、P如上所述，一條從z

到z

的f-非飽和路P，稱為N中的一條f可增路。[定理8-6-1]

網(wǎng)絡(luò)N中的流f

是最大流當(dāng)且僅當(dāng)N中不包含任何f可增路。[證明]

若N中有一條f-可增路P，則P為一條f-非飽和路，(P)>0。按照上述增量的方法構(gòu)造新的流f，其流量為w=w+(P)>w，與f為一個(gè)最大流矛盾。8.6最大流最小割定理

設(shè)N中不含任何f-可增路，欲證f為一個(gè)最大流。構(gòu)造S為N中從源z出發(fā)經(jīng)過(guò)某一條f-非飽和路可達(dá)的所有結(jié)點(diǎn)的集合，zS。由于N中不含任何f-可增路，故zS。令S=VS，則(S,S)為N中的一個(gè)割切。

(1)考察f(S,S)。對(duì)任一<u,v>A，uS，vS，必有fuv=cuv。否則，設(shè)fuv<cuv。由S的定義，從z

至u

存在一條f-非飽和路P，(P)>0。將P擴(kuò)展至v點(diǎn)，按的定義有

(P+v)=min{(P),cuvfuv}>0。故P+v

是一條從z

至v

的f-非飽和路，與vS矛盾。因此，f(S,S)=c(S,S)。8.6最大流最小割定理

(2)考察f(S,S)。對(duì)任一<p,q>A，pS，qS，必有fpq=0。否則，設(shè)fpq

>0。由S的定義，從z

至q

存在一條f-非飽和路L，(L)>0。將L

擴(kuò)展至p

點(diǎn)，有

(L+p)=min{(L),fpq}>0。故L+p

是一條從z至p

的f-非飽和路，與

pS矛盾。因此，f(S,S)=0。8.6最大流最小割定理

(3)由[定理8-5-1]，流量

w=f(S,S)f(S,S)=c(S,S)0=c(S,S) （I） 由推論2 wmaxmin{c(S,S)}

又 wwmax

，min{c(S,S)}c(S,S)

故wwmaxmin{c(S,S)}c(S,S) （II） 由（I）（II）得

w=wmax=min{c(S,S)}=

c(S,S)

即此時(shí)w為最大流量，即f為最大流。與此同時(shí)割切(S,S)具有最小割切容量c(S,S)）8.6最大流最小割定理[定理8-6-2]

在任何運(yùn)輸網(wǎng)絡(luò)中，流的最大值等于最小的割切容量，即wmax=min{c(S,S)}(Ford-Fulkerson)[證明]設(shè)網(wǎng)絡(luò)的一個(gè)流f已經(jīng)取得最大流量。構(gòu)造集合如下：

(1)zS；

(2)若xS，<x,y>A且fxy<cxy，則yS；

(3)若xS，<y,x>A且fyx

>0，則yS。此時(shí)必有zS，否則從z到z可構(gòu)造一條f-可增路，與f是最大流矛盾。令S=VS，則(S,S)是一個(gè)割切。由S的定義，若<x,y>(S,S)則必有fxy=cxy，否則yS；若<y,x>(S,S)則必有fyx=0，否則yS。因此，f(S,S)=c(S,S)且f(S,S)=0。重復(fù)[定理8-6-1]證明(3)過(guò)程得證。8.6最大流最小割定理[Ford-Fulkerson標(biāo)號(hào)法]

求運(yùn)輸網(wǎng)絡(luò)的最大流。基本思想：從一個(gè)已知流出發(fā)，構(gòu)造一個(gè)流量不斷增加的流序列，最后終止于最大流。序列中的每一個(gè)流通過(guò)探求網(wǎng)絡(luò)中關(guān)于其前繼流的f-可增路并沿f-可增路實(shí)施增流過(guò)程得到。當(dāng)網(wǎng)絡(luò)中不再存在任何f-可增路時(shí)，就獲得了一個(gè)最大流。[主控流程] 0.初始化。賦0流，w=0。

I.標(biāo)號(hào)：用標(biāo)號(hào)法求增流路徑，若不存在，過(guò)程結(jié)束。

II.增流：沿增流路徑修改路徑中各弧流量，獲得新的流。刪去所有標(biāo)號(hào)，轉(zhuǎn)I。8.7Ford-Fulkerson標(biāo)號(hào)法[標(biāo)號(hào)原理](1)N中的樹T=(V(T),A(T))稱為一棵

f-非飽和樹若 ①zV(T) ②對(duì)T中任一頂點(diǎn)v，T中由

z

到v

的路是f-非飽和的。

(2)f-非飽和樹的生長(zhǎng)：設(shè)T是一棵f-非飽和樹，令S=V(T)。 ①若(S,S)中存在f<c的弧，則將該弧及其終點(diǎn)加入T； ②若(S,S)中存在f>0的弧，則將該弧及其始點(diǎn)加入T。

(3)若T生長(zhǎng)達(dá)到z

，則T中的由z

到

z的路為一條f-可增廣道。若T在達(dá)到z之前停止生長(zhǎng)，則f為一個(gè)最大流。8.7Ford-Fulkerson標(biāo)號(hào)法I.標(biāo)號(hào)過(guò)程：給源

z標(biāo)號(hào)(+z,)任選一已標(biāo)號(hào)頂點(diǎn)

x，對(duì)其任一未標(biāo)號(hào)鄰接點(diǎn)y若<x,y>A且fxy<cxy，令y=min(x,cxyfxy)，給y

標(biāo)號(hào)(+x,y)；若<y,x>A且fyx>0，令y=min(x,fyx)，給y

標(biāo)號(hào)(x,y)；若z還未得到標(biāo)號(hào)若還有可標(biāo)記的未標(biāo)頂點(diǎn)，轉(zhuǎn)(2)否則，無(wú)法增流，算法結(jié)束。若z得到標(biāo)號(hào)，轉(zhuǎn)II

增流過(guò)程。8.7Ford-Fulkerson標(biāo)號(hào)法II.增流過(guò)程：令u=z若u

標(biāo)號(hào)為(+v,u)，則fvu=fvu+

z

若u

標(biāo)號(hào)為(v,u)，則fuv=fuv

z

uv，若uz

轉(zhuǎn)(2)否則，w

w+z

，刪去全部標(biāo)號(hào)，轉(zhuǎn)I標(biāo)號(hào)。[討論]當(dāng)各弧容量為非負(fù)整數(shù)時(shí)，增流的

為整數(shù)，問(wèn)題可在有限步驟內(nèi)求解，也即網(wǎng)絡(luò)存在一個(gè)整數(shù)最大流。實(shí)際上非負(fù)有理數(shù)也可以滿足要求。8.7Ford-Fulkerson標(biāo)號(hào)法[例]

(1)網(wǎng)絡(luò)及流的初始化

容量

流量8.7Ford-Fulkerson標(biāo)號(hào)法abdczz3,04,04,01,05,01,02,02,06,03,0(2)按廣度優(yōu)先標(biāo)記頂點(diǎn)。處理邊的次序?yàn)?/p>

{z,a}，{z,c}，{a,b}，{a,d}，{b,z}

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法(+z,3)(+z,)(+z,4)(+a,3)(+a,1)(+b,2)abdczz3,04,04,01,05,01,02,02,06,03,0(3)z=2，增流。

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法(+z,3)(+z,)(+z,4)(+a,3)(+a,1)(+b,2)abdczz3,24,04,21,05,01,02,02,26,03,0(4)刪除所有標(biāo)號(hào)。

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法abdczz3,24,04,21,05,01,02,02,26,03,0(5)按廣度優(yōu)先標(biāo)記頂點(diǎn)。處理邊的次序?yàn)?/p>

{z,a}，{z,c}，{a,b}，{a,d}，{d,z}

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法(+z,1)(+z,)(+z,4)(+a,1)(+a,1)(+d,1)abdczz3,24,04,21,05,01,02,02,26,03,0(6)z=1，增流。

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法(+z,1)(+z,)(+z,4)(+a,1)(+a,1)(+d,1)abdczz3,34,04,21,15,01,02,02,26,13,0(7)刪除所有標(biāo)號(hào)。

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法abdczz3,34,04,21,15,01,02,02,26,13,0(8)按廣度優(yōu)先標(biāo)記頂點(diǎn)。處理邊的次序?yàn)?/p>

{z,c}，{c,a}，{c,b}，{c,d}，{d,z}

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法(+c,4)(+z,)(+z,4)(+c,1)(+c,2)(+d,2)abdczz3,34,04,21,15,01,02,02,26,13,0(8)z=2，增流。

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法(+c,4)(+z,)(+z,4)(+c,1)(+c,2)(+d,2)abdczz3,34,24,21,15,01,02,22,26,33,0(9)刪除所有標(biāo)號(hào)。

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法abdczz3,34,24,21,15,01,02,22,26,33,0(10)按廣度優(yōu)先標(biāo)記頂點(diǎn)。處理邊的次序?yàn)閧z,c},{c,a},{c,b}。z得不到標(biāo)號(hào)，算法結(jié)束。最大流wmax=5。

容量

流量標(biāo)記

8.7Ford-Fulkerson標(biāo)號(hào)法(+c,2)(+z,)(+z,2)(+c,1)abdczz3,34,24,21,15,01,02,22,26,33,0[進(jìn)一步的討論]Ford-Fulkerson算法的I(2)步對(duì)下一個(gè)標(biāo)號(hào)頂點(diǎn)的選擇不作任何限制時(shí)，存在某些缺陷。zkkkk1zab[例]

如圖。交替選擇z-a-b-z和z-b-a-z增流，每次z=1，經(jīng)過(guò)2k+1次才達(dá)到最大流。算法的時(shí)間按復(fù)雜度不僅僅與網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)，而且與邊的容量有關(guān)，這使得對(duì)算法的分析十分困難。Ford-Fulkerson還指出，當(dāng)容量是無(wú)理數(shù)時(shí)算法可能失敗。8.7Ford-Fulkerson標(biāo)號(hào)法[Edmonds-Karp的改進(jìn)算法][定理8-7-1Edmonds-Karp

算法]

在Ford-Fulkerson

算法中，如果每次增流都沿一條最短路徑進(jìn)行，則獲得最大流的增流次數(shù)最多不超過(guò)m(n+2)/2次。這里n

和m

分別是網(wǎng)絡(luò)的頂點(diǎn)數(shù)和邊數(shù)，“最短”指的是包含了最少的邊數(shù)。(Edmonds-Karp)[證明]略。采用廣度優(yōu)先探測(cè)得到的可增廣道是最短的增流路徑，符合

Edmonds-Karp的要求。[定理8-7-2]

Edmonds-Karp算法的計(jì)算復(fù)雜度是O(m2n)。8.7Ford-Fulkerson標(biāo)號(hào)法[討論](1)多發(fā)多收問(wèn)題：增加一個(gè)虛擬的源點(diǎn)，從源點(diǎn)向所有發(fā)點(diǎn)分別引出有向邊，容量為；增加一個(gè)虛擬的匯點(diǎn)，從所有收點(diǎn)分別向匯點(diǎn)引出有向邊，容量也為。問(wèn)題轉(zhuǎn)化成為單源單匯。8.7Ford-Fulkerson標(biāo)號(hào)法z1zzz2z1z2[討論](2)頂點(diǎn)有容量問(wèn)題：運(yùn)輸網(wǎng)絡(luò)中，如果將頂點(diǎn)視為轉(zhuǎn)儲(chǔ)站，其倉(cāng)庫(kù)容量即為頂點(diǎn)的容量。此時(shí)，需要增加關(guān)于頂點(diǎn)的容量約束條件：輸入頂點(diǎn)的總流量不能超過(guò)頂點(diǎn)的容量；同樣，從頂點(diǎn)輸出的總流量也不能超出頂點(diǎn)的容量。例：如圖，

f(x1,u)+f(x1,u)+f(x1,u)c(u)，

f(u,y1)+f(u,y2)c(u)8.7Ford-Fulkerson標(biāo)號(hào)法ux3y1x1x2y2將頂點(diǎn)u

分解為兩個(gè)無(wú)容量頂點(diǎn)u+和u，增加有向邊(u+,u)，令其容量c(u+,u)=c(u)，如圖。問(wèn)題轉(zhuǎn)化為頂點(diǎn)無(wú)容量的情形。8.7Ford-Fulkerson標(biāo)號(hào)法ux3y1x1x2y2u+[練習(xí)]

容量abdczz5325135348.7Ford-Fulkerson標(biāo)號(hào)法[解]按廣度優(yōu)先標(biāo)記頂點(diǎn)。

容量abdczz5325135340000000(+z,3)(+z,)(+z,4)(+a,3)(+c,3)(+b,3)008.7Ford-Fulkerson標(biāo)號(hào)法[解]z=3，增流。

容量abdczz5325135343000330(+z,3)(+z,)(+z,4)(+a,3)(+c,3)(+b,3)008.7Ford-Fulkerson標(biāo)號(hào)法[解]刪除所有標(biāo)號(hào)。

容量abdczz5325135343000330008.7Ford-Fulkerson標(biāo)號(hào)法[解]按廣度優(yōu)先標(biāo)記頂點(diǎn)。

容量abdczz5325135343000330(+c,4)(+z,)(+z,4)(+a,2)(+c,3)(+d,3)008.7Ford-Fulkerson標(biāo)號(hào)法[解]z=3，增流。

容量abdczz5325135343000333(+c,4)(+z,)(+z,4)(+a,2)(+c,3)(+d,3)338.7Ford-Fulkerson標(biāo)號(hào)法[解]刪除所有標(biāo)號(hào)。

容量abdczz5325135343000333338.7Ford-Fulkerson標(biāo)號(hào)法[解]按廣度優(yōu)先標(biāo)記頂點(diǎn)。

容量abdczz5325135343000333(+c,1)(+z,)(+z,1)(+a,1)(+b,1)(+d,1)338.7Ford-Fulkerson標(biāo)號(hào)法[解]z=1，增流。

容量abdczz5325135344011334(+c,1)(+z,)(+z,1)(+a,1)(+b,1)(+d,1)348.7Ford-Fulkerson標(biāo)號(hào)法[解]刪除所有標(biāo)號(hào)。z

之后的頂點(diǎn)不能標(biāo)記，算法結(jié)束，w=7。

容量abdczz5325135344011334348.7Ford-Fulkerson標(biāo)號(hào)法[練習(xí)]

容量

流量8.7Ford-Fulkerson標(biāo)號(hào)法abdczz15,04,012,05,03,010,07,010,0

結(jié)果：

容量

流量8.7Ford-Fulkerson標(biāo)號(hào)法abdczz15,104,412,105,03,310,77,710,71.判定問(wèn)題與壞算法問(wèn)題：任給n,mN,問(wèn)n+m=?

實(shí)例：1+1=? 7+8=?…[判定問(wèn)題]

對(duì)問(wèn)題的每個(gè)實(shí)例，答案為“是”或“否”之一的一類問(wèn)題。[例]任意給定一個(gè)圖G，問(wèn)G是否是Hamilton圖？ 實(shí)例：K3是否是一個(gè)Hamilton圖？8.8圖論中的NPC問(wèn)題通過(guò)構(gòu)造判定問(wèn)題可以完成某些求解。[例]7+8=？ 構(gòu)造判定：

7+8是否大于1？

7+8是否大于2？

… 7+8是否大于14？

7+8是否大于15？

由于7+8是整數(shù)解，故經(jīng)過(guò)有限次的判定之后，可以獲得7+8=15的解。8.8圖論中的NPC問(wèn)題[例]給定圖G=(V,E)，求(G)=？ 構(gòu)造判定： (G)=是否大于1？ (G)=是否大于2？

… (G)=是否大于|V|1？

由于(G)|V|<+，故經(jīng)過(guò)有限次的判定之后，可以獲得(G)的值。8.8圖論中的NPC問(wèn)題8.8圖論中的NPC問(wèn)題一些判定問(wèn)題難以用類似的窮舉法完成求解。[例]給定圖G=(V,E)，問(wèn)G是否是一個(gè)Hamilton圖？ 對(duì)G的一個(gè)實(shí)例，考察其頂點(diǎn)的任意一種排列是否在G中形成一個(gè)Hamilton回路。n

個(gè)頂點(diǎn)的排列數(shù)是n!。由Sterling公式（n!估計(jì)式）

當(dāng)n

足夠大（>60）時(shí)，n!>3n

。可見此時(shí)使用窮舉法由于計(jì)算量太大已失去實(shí)際意義。8.8圖論中的NPC問(wèn)題[Edmonds]

當(dāng)一個(gè)判定問(wèn)題D給定之后，若存在一個(gè)多項(xiàng)式P(t)，使得對(duì)于D的任何輸入長(zhǎng)為n

的實(shí)例，可以在O(P(n))時(shí)間內(nèi)對(duì)這個(gè)實(shí)例給出答案，則稱這種解答的算法的時(shí)間復(fù)雜度是合理的，稱這種算法為有效算法或好算法；否則稱之為無(wú)效算法或壞的算法。顯然，上述通過(guò)窮舉法判定G是否是一個(gè)Hamilton圖的算法是一個(gè)壞算法。2.Turing機(jī)和NPC[Turing機(jī)]

稱五元組(,S,h,f,C)為一部Turing機(jī)。

=(1,2,…,k,b)：帶符集，b是空白符。S=(s0,s1,s2,…,sn,sY,sN

)：狀態(tài)集，s0是初態(tài)，sY

和sN

分別稱為yes態(tài)和no態(tài)。C：雙向無(wú)窮且可由讀寫頭閱讀與改寫的“紙帶”。C劃分成雙向無(wú)窮地址序列…,C(2),C(1),C(0),C(1),C(2),…h(huán)

=h(t)：讀寫頭的頭位置函數(shù)，t=0,1,2,…。讀寫頭的每個(gè)單位時(shí)間指著一個(gè)地址，若第

t

時(shí)間指著C(i)，則記成h(t)=i。規(guī)定h(0)=1。8.8圖論中的NPC問(wèn)題8.8圖論中的NPC問(wèn)題初始化

=若輸入符號(hào)為{x1,x2,…,xn

}，用(i,t)表示第

t

時(shí)間C(i)地址上寫的帶符，規(guī)定f

：讀寫變換。

f

：(S{sY,sN

})S{1,1}8.8圖論中的NPC問(wèn)題f

：讀寫變換。

f

：(S{sY,sN

})S{1,1}

當(dāng)s(t)(S{sY,sN

})，t{0,1,2,…}時(shí)，規(guī)定

f(s(t),(h(t),t))=(p,q,d)結(jié)束：出現(xiàn)狀態(tài)sY

或sN

時(shí)，即得到了Turing機(jī)的運(yùn)算結(jié)論yes或no。此時(shí)停機(jī)。

[P問(wèn)題集合]

若對(duì)判定問(wèn)題D，存在一個(gè)多項(xiàng)式P(t)，對(duì)于D的任意給定的實(shí)例，若此時(shí)實(shí)例的輸入符號(hào)為{x1,x2,…,xn

}，其答案是