第1章圖論2教材

§1.6

偶圖、匹配及其應(yīng)用一．偶圖

定義1

若圖G=(V,E)的點集能劃分為兩個互不相交的非空子集V1與V2（V1∪V2=V），使任意的e∈E，e

的兩端點分屬于V1與V2，則稱

G為偶圖，記為G=(V1,V2,E)。

若偶圖G=(V1,V2,E)為簡單圖，且V1的每個點均與V2的每個點相鄰，則稱G為完全偶圖，記為Km,n

，其中

m,n分別為V1與V2的點數(shù)。

例

K3,3

K1,3

G1

G2

四個圖均為偶圖;

K1,3,K3,3為完全偶圖

定理11一個圖是偶圖當(dāng)且僅當(dāng)它不含長度為奇的圈。例偶圖不是偶圖又由定理11知至少兩個點的樹是偶圖。二．匹配

定義2設(shè)M是圖G的邊子集，若任意的e∈M，e

都不是環(huán)，且屬于M的邊互不相鄰，則稱M為

G的一個匹配。設(shè)M為

G的一個匹配，對v∈V(G)，若v是M中某邊的一個端點，則稱v為M飽和點，否則稱為M非飽和點。

匹配還可分為最大匹配（含邊數(shù)最多的匹配）和完美匹配（圖中的點均為M飽和點的匹配M）等類型。對M2，點v1是的飽和點，點v2是非飽和點。v1v2v3v4v8v5v7v6

例1中的M1

和M2既不是最大匹配，也不是完美匹配，而M3是最大匹配，也是完美匹配。例1設(shè)圖G為:G的匹配有：M1={v1v8}M2={v1v3，v8v4，v7v5}M3={v1v2，v8v3，v7v4，v6v5}等等

關(guān)系：

(1)

完美匹配必是最大匹配，而最大匹配不一定是完美匹配。(2)

一個圖的最大匹配必存在，但完美匹配不一定存在。(3)

圖G存在完美匹配的一個必要條件是G的點數(shù)為偶。

設(shè)M為圖G的一個匹配可看出：對Г3，若取Г3中非M的邊再連同

M的不在Г3中的邊組成M’，則M’的邊數(shù)比

M的邊數(shù)多，這表明

M不是該圖的最大匹配。M交替路：G中由M中的邊與非M中的邊交替組成的路。M可擴(kuò)路：起點與終點均為M非飽和點的M交替路。例如，取M={紅邊}Г1Г2Г3M交替路M可擴(kuò)路定理12

G的匹配M是最大匹配當(dāng)且僅當(dāng)G不含M可擴(kuò)路.三．偶圖的匹配取圖G的一個頂點子集S，令

N(S)={v|存在u∈S，且v與u相鄰}稱N(S)為S的鄰集。取S={v1,v2}，則N(S)={v8,v3,v1,v2}v1v2v3v4v8v5v7v6例如圖中1．偶圖存在最大或完美匹配的條件設(shè)偶圖G=(V1,V2,E)，則有下列必要或充分條件：①

G存在飽和

V1的每個點的匹配，當(dāng)且僅當(dāng)對任意的

S

V1，有|N(S)|≥|S|即

N(S)的點數(shù)不少于S的點數(shù)。í②

若存在正整數(shù)t，滿足任意的v∈V1，有

d(v)≥t，同時對任意的u∈V2，有d(u)≤t，則G存在飽和V1的每個點的匹配。③

若G為k正則偶圖，k>0，則G存在完美匹配。④若|

V1|>|V2|，則不存在飽和V1的每個點的匹配。

例2

判斷圖G1與圖G2（如下圖所示）是否存在飽和V1的每個點的匹配，其中V1={v1,v2,v3}。解

對G1，取S={v1,v2}，則

N(S)=

{u1}，有|N|(S)|<|S|。由條件①，G1不存在飽和V1的每個點的匹配。對G2，因?qū)θ我獾膙∈V1，有

d(v)≥3，對任意的u∈V2，有

d(u)≤3。由條件②知V1存在飽和V1的每個點的匹配。實際上，匹配M={v1u1，v2u3，v3u4}即滿足要求。G1G2v1

v2

v3v1

v2

v3u1

u2u3

u4u1

u2u3

u4應(yīng)用—工作安排問題

問題：n個工人x1,x2,…,xn，n

件工作y1,y2,…,yn。已知xi

能勝任

ki

件工作，i=1，2，…,n。問能否存在一種工作安排方案，使每個人都能分配到他所能勝任的一件工作。假定每件工作只能一人做，若能，又如何安排？

建模：以工人和工作為點，當(dāng)且僅當(dāng)xi

能勝任工作

yj

時則連線，得偶圖G=(V1,V2,E)。于是一種符合要求的安排對應(yīng)G中一個完美匹配。所以此問題實際上是求偶圖的完美匹配問題.

進(jìn)一步：若不要求人數(shù)與工作數(shù)相等，則問題是求偶圖的飽和V1的每個點的匹配問題，其中V1是工人的集合；進(jìn)一步，若問：能否存在一種安排使盡可能多的人能分到他能勝任的工作或使盡可能多的工作被分配，則問題為求偶圖的最大匹配問題。求偶圖的最大匹配的方法，稱為匈牙利算法

算法思想：先任取一個匹配

M，然后尋找M可擴(kuò)路。若不存在M可擴(kuò)路，則M為最大匹配；若存在，則將可擴(kuò)路中M與非M的邊互換，得到一個比M多一條邊的匹配M

’，再對M

’

重復(fù)上面過程。算法是從V1的每個非飽和點出發(fā)尋找M可擴(kuò)路的。若從V1的每個非飽和點出發(fā)都無M可擴(kuò)路，則M必?zé)o可擴(kuò)路，從而M是最大匹配。這是因偶圖中不可能存在兩個端點均在V2中的M可擴(kuò)路。匈牙利算法

給定偶圖G=(V1,V2,E)。(1)任取一個匹配M。(3)

取V1的非飽和點

x0，令

X={x0}，Y=Φ。(5)若y為飽和點，則轉(zhuǎn)（6）；否則轉(zhuǎn)（7）。(6)

存在z∈V1，有yz∈M，令

X=

X∪{z}，Y

=

Y∪{y}，轉(zhuǎn)（4）。(7)

存在x0到

y的M可擴(kuò)路Γ，令

M=(M∪E(Γ))\

(M∩E(Γ))，轉(zhuǎn)（2）。(2)

若

V1中每個點均為

M飽和點，則停（輸出M）；否則繼續(xù)（3）。(4)

若N(X)=Y，則將x0也作為M飽和點對待，轉(zhuǎn)(2)；否則取

y∈N(X)\Y。例3求圖G（如圖（a）所示）的最大匹配，其中V1={v1,v2,v3,v4,v5}。（1）任取一個匹配M={v1u1，v3u3，v5u5}，如圖（a）的紅邊所示。(2)顯然V1中存在非飽和點，取其中一個

v2，令X={v2}，Y=Φ。①因N(X)={u1,u3}≠Y，故取u1∈N(X)\Y=N(X)={u1,u3}。②

u1為飽和點，且v1u1∈M，令X=X∪{v1}={v1,v2}，Y=Y∪{u1}=

{u1}。③因N(X)={u1,u2,u3}≠Y，故取u2∈N(X)\Y={u2,u3}。④u2為非飽和點，得M可擴(kuò)路Γ=v2u1v1u2v1u3u4u2u1v3v4v5u5v2(a)⑤取M=(M∪E(Γ))\

(M∩E(Γ))={v2u1,v1u2,v3u3,v5u5}，如圖（b）中的紅邊。(3)

取V1的非飽和點

v4。從v4出發(fā)重復(fù)（2）的過程得M可擴(kuò)路Γ=v4u5v5u4

(4)

V1已無非飽和點，故結(jié)束。v1u3u4u2u1v3v4v5u5v2(b)v1u3u4u2u1v3v4v5u5v2(c)取M={v1u2，v2u1，v3u3，v4u5，v5u4}，如圖（c）中紅邊。工作安排問題未考慮每人做某項工作的效率。若要求考慮效率，并問“如何安排使效率最大”，這稱為最優(yōu)安排問題。最優(yōu)安排的圖論模型是在賦權(quán)偶圖中尋找具有最大權(quán)的匹配。鑒于課時，此問題的求解不作介紹?！?.7圖的著色一、邊著色設(shè)A,B是兩個集合，φ是A到B的一個映射，記為φ：A→B，對í￠ABBAí￠,記φ()()}{AaaA￠?=￠fφ-1，()}{BxxB￠?=￠)(f特別地當(dāng)

B’＝時，φ

也記為φ(b)。-1-1()B￠定義

給定圖G=(V,E),稱映射

φ：E

→{1,2,…,k}為G的一個k-邊著色，簡稱邊著色，稱{1,2,…,k}為色集。若φ為G的邊著色且

e’,e’’

?E,當(dāng)e’

與e’’相鄰時，φ(e’)≠φ(e’’)，則稱該著色是正常的。圖G的正常k-邊著色的最小k值稱為G的邊色數(shù)，記為c’

(G),簡記為c’

.

若圖G存在一個正常k-邊著色，則稱G是k-邊可著色的。

若φ為圖G的邊著色，e為G的邊，我們也稱φ(e)為邊e的著色或邊e著φ(e)色。圖(a)和圖(b)表達(dá)了同一個圖的兩個3-邊著色。其中(b)為正常3-邊著色。(a)(b)'c易知該圖有=3任何正常邊著色中和任一頂點關(guān)聯(lián)的各邊必須著不同色，由此推知c′≥Δ

定理定理對任意的二部圖G，c

′(G)=Δ(G)。解

設(shè)Km,n的互補(bǔ)頂點子集為X={x0,x1,…,xm-1}，Y={y0,y1,…,yn-1}。例

給出Km,n

的一個正常Δ-邊著色。假定m≤n,此時Δ＝n。()nmjiKEyx,?"記為＝使,φ(xiyj)=(i+j)(modn)i＋nj令

φ：E(Km,n)→{0,2,…,n-1}任取Km,n中兩條鄰邊xiyj

和xiyk,

j≠k。從而，c′

(Km,n)≤n≤Δ所以，c′

(Km,n)=Δ同理，對鄰邊xiyj

和xkyj,也有φ(xiyj)≠φ(xkyj)。若φ(xiyj)=φ(xiyk),則i＋nj=

i＋nk,從而

j＝k，矛盾。所以φ(xiyj)≠φ(xiyk)。以上表明φ是正常邊著色。定理(Vizing)①若G是簡單圖，則c′(G)=D或D+1。②設(shè)無環(huán)圖G

的最大重數(shù)為m，則c’

≤Δ+m。例下圖是一個邊色數(shù)達(dá)到Δ+μ

的圖，其中Δ=4,μ=2。簡單圖的邊色數(shù)僅兩種情況，或為Δ，或為Δ＋1。我們將c’=Δ的簡單圖稱為第一類圖，否則為第二類圖。易知，路、樹、簡單偶圖為第一類圖；奇圈、n為奇時的Kn為第二類圖。盡管簡單圖的邊色數(shù)僅兩類，但判斷一個什么樣的簡單圖是第一類圖，這個問題還未完全解決。邊著色的應(yīng)用—排課表問題問題：設(shè)有m位教師x1,x2,…,

xm

和n個班級y1,y2,…,

yn。已知在一周內(nèi)xi需給

yj

上

kij

節(jié)課，若將上一節(jié)課所用的時間稱為一個課時。問如何制訂一張課時數(shù)盡可能少的課表？假定在同一課時內(nèi)一位教師只能上一個班，一個班只能一個教師上。建模：將教師與班級作為點，若教師xi需給

yj

上

kij節(jié)課，則在xi與

yj

間連

kij

條邊，得偶圖G。這樣，一個課時1－1對應(yīng)G中－個匹配，而一個匹配又1－1對應(yīng)一種正常邊著色的著同色的一組邊。例如，取n=2，m=3，并假定x1需給

y1上兩節(jié)課；x1,x2需給

y2,y3各上一節(jié)課的偶圖模型如圖所示。此圖的邊色數(shù)為4，這對應(yīng)一個四課時的課表。x2x1y1y2y3

因偶圖G的邊色數(shù)為△(G)，所以排課表問題可歸納為：對給定的偶圖G=(V1,V2,E)，如何對G用△(G)種色進(jìn)行正常邊著色？求解方法如下：(1)

假定|V1|≥|V2|,加點擴(kuò)充V2為V2*,使|V1|=|V2*|。(2)找出V1中最小度點與V2中最小度點，然后連成邊。如此直至各點的度均等于△(G)，記所得之圖為G*。由前面的章節(jié)的討論知G*存在完美匹配。(3)用匈牙利算法找出G*的一個完美匹配M1，再找G*-M1

的完美匹配M2，如此繼續(xù)可求得G*的一組互不相交的完美匹配M1，M2，…,M△

。(4)取M1，M2，…,M△

中原來圖的邊即為所求。例4

求下圖G

的一個顏色數(shù)達(dá)到最小的正常邊著色。解c’（G）=△(G)=3擴(kuò)充G為G*，見圖(a)。G*的一個正常邊著色也見(a)。x1x2x3x4y1y2y3G:(a)x1x2x3x4y1y2y3y4x1x2x3x4y1y2y3G的著色

二、頂點著色定義

給定圖G=(V,E)，稱映射

φ：V→{1,2,…,k}為G的一個k–點著色，簡稱著色，稱{1,2,…,k}為色集。若對G中任意兩個相鄰頂點u和v均滿足φ(u)≠φ(v),則稱該著色為正常的。圖G的正常k–著色的最小k值稱為G的色數(shù)，記為c(G),簡記為c

。

若圖G存在一個正常k-著色，則稱G是k-可著色的。設(shè)是G的一個著色，u為G中的點，我們也稱φ(u)為u的著色或u著φ(u)色。上圖的(a),(b)表達(dá)了一個圖的兩個3-著色，其中(b)為正常的，易知該圖有c＝3。(a)(b)

定理對任意的圖G均有：≤Δ+1c證明

對圖G的點數(shù)n用歸納法。當(dāng)n＝1時，c

=1，Δ≥0，滿足c

≤Δ+1。

對n≥2的圖G,取u∈V(G),設(shè)G’＝G-u。由歸納假設(shè)c(G’)≤Δ(G’)+1，從而存在G’的(Δ(G’)+1)-著色φ。因Δ(G’)≤Δ(G),所以φ也是G’的(Δ(G)+1)-著色。(G)≤Δ(G)+1c設(shè)

dG(u)=k,G中與u相鄰的點為v1,v2,…,vk。因|{φ(v1),…,φ(vk)}|≤k＜Δ(G)+1,所以存在j∈{1,2,…,Δ(G)+1}滿足j

{φ(v1),…,φ(vk)},令φ(u)=j,則φ被擴(kuò)充為G的一個(Δ(G)+1)-著色，所以定理

設(shè)G是連通圖。假定G既不是完全圖又不是奇圈，則≤Δc一個著色算法：

給定圖G=(V，E)，設(shè)V={v1,v2,…,

vn}，著色函數(shù)為φ

，色集C={1,2,…,Δ+1}。(i)令φ(v1)=1,i=1。(ii)

若i=n,則停；否則令

C(vi＋1)

={φ

(vj)|j≤i并且vj

與vi＋1相鄰}設(shè)k為C\C(v

i＋1)

中的最小正整數(shù)，令

φ

(vi＋1)=k。(iii)令i=i+1,轉(zhuǎn)(ii)

例試用算法給圖中的圖著色。

解

設(shè)φ

為著色函數(shù)，C={1,2,…,5},著色過程如下:V1V6V5V2V3V4(1)φ

(v1)=1,C(v2)={1},C\C(v2)={2,…,5}(2)φ(v2)=

2,C(v3)={1,2},C\C(v3)={3,…,5}(3)φ(v3)=3,C(v4)={3},C\C(v4)={1,2,4,5}(4)φ(v4)=1,C(v5)={1},C\C(v5)={2,…,5}(5)φ

(v5)=2,C(v6)={1,2,3},C\C(v6)={4,5}(6)φ

(v6)=

4§1.8

平面圖

問題：假定有三個倉庫x1，x2，x3和三個車站y1，y2，y3。為了便于貨物運(yùn)輸，準(zhǔn)備在倉庫與車站間修筑鐵路，如圖(a)所示,其中邊代表鐵路。問是否存在一種使鐵路不交叉的路線設(shè)計方案，以避免修建立交橋。

問題的解答但如果在x3與y1之間也要修一條鐵路，則可驗證滿足要求的方案不存在。

x1

x2x3y1

y2y3(a)

x1

x2x3

y1

y2y3?

定義1

若圖G可畫在一個平面上使除頂點外邊不交叉，則稱G可嵌入平面，或稱G為可平面圖?？善矫鎴DG的邊不交叉的一種畫法稱為G的一個平面嵌入，G的平面嵌入表示的圖稱為平面圖。例1=平面圖可平面圖可平面圖不可平面圖=不可平面圖

=可平面圖==可平面圖

定義：設(shè)G是一個平面圖，G將所嵌入的平面劃分為若干個區(qū)域，每個區(qū)域的內(nèi)部連同邊界稱為G的面，無界的區(qū)域稱為外部面或無限面。每個平面圖有且僅有一個外部面。設(shè)f是G的一個面，構(gòu)成f的邊界的邊數(shù)（割邊計算兩次）稱為f的次數(shù)，記為deg(f

)。例2

有5個面：f1，f2，f3，f4，f5（f5為外部面）圖不連通，其外部面的次數(shù)為5f1f2f3f5f4deg(f1)=1deg(f2)=2deg(f3)=3deg(f4)=6deg(f5)=10相加為22，正好是邊數(shù)11的2倍定理19

設(shè)具有m條邊的平面圖G的所有面的集合為Ψ,則m2)deg(=?Y?ff（8.1）證明

任取G的一條邊e。若e是兩個面的公共邊，則在計算面的次數(shù)時，e被計算兩次。若e不是公共邊，則e是G的割邊，由面的次數(shù)的定義，e也被計算兩次。所以所有面的次數(shù)之和是邊數(shù)的2倍，即（8.1）式成立。證明

對r用歸納法。設(shè)r=k時，（8.2）式成立。定理20（Euler公式）設(shè)G是具有n個點m條邊r個面的連通平面圖，則有

n–m+r=2（8.2）當(dāng)r=1時，G無圈又連通，從而是樹，有n=m+1于是n-m+r

=（m+1）-m+1=2同時n’

=n，m’=m-1，r’=r-1代人（8.3）式得

n-（m-1）+（r-1）=2即n–m+r=2

當(dāng)r=k+1時，此時G至少兩個面，從而有圈C。刪去C中一條邊，記所得之圖為G’。并設(shè)G’的點數(shù)、邊數(shù)和面數(shù)依次為n’,m’和r’,易知G’仍連通，但只有k個面，由歸納假設(shè)有

n’-m’+r’=2（8.3）定理21

設(shè)G是具有n

個點m條邊的連通平面圖,Ψ是G中所有面的集合，若對任意的f∈Ψ均有deg(f)≥l≥3，則

)2(2--￡nmll(8.4)證明

設(shè)G有r個面，因每個面均有deg（f）≥l

，故?F?=￡fflmr2)deg()1.8(mrl2￡T將上式代入Euler公式

n–m+r=2得223+-mmnlT)2(2--￡nmll推論22設(shè)簡單可平面圖G有n

個點m條邊,且n≥3，則

m≤3n-6

（8.5）證明

先假定G連通。因G至少有三個點又連通且為簡單圖，故對G相應(yīng)的平面圖中每個面的次數(shù)至少是3。由定理21，取l=3得m≤)2(233--n=3-6n

設(shè)G不連通。若G存在至少有三個點的連通分支，因?qū)的這些分支均滿足（8.5）式，將各不等式相加也得類似不等式，設(shè)為m1≤3n1-6。

設(shè)G沒有大于兩個點的連通分支。此時m≤n。因n≥3時，n≤3n-6，所以有m≤3n-6。再設(shè)G的所有少于3個點的連通分支的總邊數(shù)為m2，總點數(shù)為n

2。此時有m2≤n

2≤3n

2，于是m1+m2≤3(n

1+n

2)-6，從而有m≤3n-6。例3

證明K5和K3,3是不可平面圖。證明

若K5是可平面圖，則因K5是至少三個點的簡單圖，由推論22，K5應(yīng)滿足m≤3n-6。而K5中m=10，n=5，代入不等式(8.5)得10≤3×5–6=9矛盾，所以K5是不可平面圖。對K3,3，因K3,3沒有長小于4的圈，所以若K3,3是可平面圖，則對其相應(yīng)的平面圖中每個面的次數(shù)至少為4。由定理21，K3,3應(yīng)滿足l=4的不等式（8.4）即m≤（-2）=2-4244-nn而K3,3中m=9，n=6，代入上式得:9≤2×6-4=8矛盾，所以K3,3是不可平面圖。

定理23若G是簡單平面圖，則δ≤5.證明

對點數(shù)n=1，2，直接驗證可知結(jié)論成立。設(shè)n≥3，若δ≥6，則??=￡)(2)(6GVvdnm

n

m＞3n-6T這與推論22矛盾。所以δ≤5?！?.9

網(wǎng)絡(luò)流一運(yùn)輸網(wǎng)絡(luò)與最大流

現(xiàn)實生活中，人們經(jīng)常見到一些網(wǎng)絡(luò)，如鐵路網(wǎng)、公路網(wǎng)、通信網(wǎng)、煤氣管網(wǎng)等。這些網(wǎng)絡(luò)有一個共同的特點，就是在網(wǎng)絡(luò)中都有諸如物資、人或信息等某種量從一個地方流向另一個地方。因而如何安排這些量的流動以便取得最大效益將是一個很有意義的課題。

本節(jié)將涉及有向圖，其定義只須將無向圖的定義中的無序點對改為有序點對即可。我們將有向圖中以x為起點y為終點的有向邊記為〈x,y〉。有向圖中點v的出度定義為圖中以點v為起點的邊的條數(shù)，記為d+(v)；點v的入度定義為圖中以v為終點的邊的條數(shù)，記為d-(v)；度定義為出度加上入度，仍記為d(v)。例1圖1-46表示的圖是一個有向圖，其中

d+(u1)=2，d-(u1)=1，d(u1)=3；d+(u4)=1，d-(u4)=2，d(u4)=3u1u3u4u2圖1-46

定義1一個連通的且無環(huán)的有向圖G=〈V,E〉，若滿足下列條件：

(1)恰有一個入度為零的點s（稱為發(fā)點）；(2)恰有一個出度為零的點t（稱為收點）；(3)每條邊上都帶有一個非負(fù)的權(quán)（稱為邊容量），則稱G為運(yùn)輸網(wǎng)絡(luò)，簡稱為網(wǎng)絡(luò)。網(wǎng)絡(luò)中，邊〈x,y〉的容量記為c(x,y)，既非發(fā)點又非收點的點稱為中間點。例圖1-47就是一個網(wǎng)絡(luò)。

sbdcta782546534圖1-47定義2

給定網(wǎng)絡(luò)G=〈V,E〉，若定義在E上的實值函數(shù)f

滿足：（1）對任意的(x,y)∈E，有0≤f(x,y)≤c(x,y),

f(x,y)稱為邊〈x,y〉的流量；（2）所有中間點v，恒有

f-(v)=f+(v)其中f-(v)表示所有以v為終點的邊上的流量之和，f+(v)表示所有以v為起點的邊上的流量之和。則稱f為G的流函數(shù)，簡稱流。定義2中的（1）表示通過邊的流量不能超出該邊的容量，稱為容量約束；（2）表示流進(jìn)中間點的流量的總和等于流出該點的流量的總和，稱為守恒條件。abcst圖1-485,25,47,14,33,34,43,2例下圖是一個網(wǎng)絡(luò)流的例子，其中各邊的第一個數(shù)字表示該邊的容量，第二個數(shù)字表示該邊的流量。

設(shè)f是網(wǎng)絡(luò)G的流，稱發(fā)點s流出的流量之和為f的值，記為fv，即fv

=f+(s)。

例如圖1-48所示的網(wǎng)絡(luò)流f，有fv=6。割的概念：

設(shè)f是G的流，若G中不存在其他流f’，滿足f’v

＞fv，則稱f為G的最大流。

給定網(wǎng)絡(luò)G=〈V,E〉，取SV，記=V\S，滿足發(fā)點s∈S，收點t∈，令（S,）={<x,y>|<x,y>∈E，x∈S，y

∈}稱（S,）為G的割。令

c(S,)=稱c(S,)為割(S,)的割容量，割容量最小的割稱為最小割。ìSSSSSS??),(),(),(SsyxyxcSS例abcst圖1-485,25,47,14,33,34,43,2圖1-48中取S={s,a,c}，則S={b,t}，(S,S)={<a,b>，<c,t>}（圖中虛線所通過的兩條邊）。有

c(S,S)=

c(a,b)+

c(c,t)=5+4=9定理25

在任一運(yùn)輸網(wǎng)絡(luò)中，從發(fā)點流出的總量等于收點流進(jìn)的總量。定理24

網(wǎng)絡(luò)G中任一流的值不超過該網(wǎng)絡(luò)的任一割的容量。設(shè)f是網(wǎng)絡(luò)G的一個流，將G視為無向圖，Γ為從發(fā)點s到收點t的一條路，若Γ中的所有前向邊<x,y>（即方向與路中從s到t的方向一致的邊）有f(x,y)<

c(x,y)，所有后向邊<u,v>有f(u,v)＞0，則稱Γ為關(guān)于f的可增路。s9,4tdcba10,58,37,26,3上圖是將某網(wǎng)絡(luò)視為無向圖時從s到t的一條路，其中邊上的第一個數(shù)字表示該邊的容量，第二個數(shù)字表示該邊的流量，邊<s,a>，<c,d>與<d,t>為前向邊，邊<b,a>與<c,b>為后向邊，并且此路為可增路。設(shè)Γ為G的一條可增路，對Γ中的任一條邊〈i,j〉，令

δij

=?íì><><-為后向邊為前向邊jijifjijifjic,),,(,),,(),(

,δ=

min{δij

}例如對上圖中的可增路

δ=

min{6-3，2，3，10-5，9-4}=2定理28給定網(wǎng)絡(luò)G，f

是G的最大流當(dāng)且僅當(dāng)G中不存在關(guān)于f的可增路。網(wǎng)絡(luò)最大流的一個算法，稱為標(biāo)號法算法的思想:

對流f（初始時，取f為零流）尋找可增路，若存在，則通過調(diào)整路上的值使f增大，再對f重復(fù)此過程，直到不存在可增路。定理26

在任一運(yùn)輸網(wǎng)絡(luò)中，最大流的值等于最小割的容量。算法（1）對任意的<x,y>∈E,置f(x,y)=0，標(biāo)發(fā)點為（s+,∞），令δs

=∞。(2)

若點x已標(biāo)號，則對與x相鄰的未標(biāo)號的點y，按下法標(biāo)號：

①<x,y>∈E。當(dāng)f(x,y)＜c(x,y)時，令

δy

=min{c(x,y)-f(x,y)，δx

}給y標(biāo)號(x+,δy)；當(dāng)f(x,y)=c(x,y)時，不給y標(biāo)號；

②<y,x>∈E。當(dāng)f(y,x)＞0時，令

δy=min{f(y,

x)，δx}給y標(biāo)(x