圖論算法-數(shù)學(xué)建模詳解

圖論概述圖論(Graph

Theory)是運(yùn)籌學(xué)中的一個(gè)重要分支，主要研究具有某種二元關(guān)系的離散系統(tǒng)的組合結(jié)構(gòu)和性質(zhì)。如，通信系統(tǒng)、交通系統(tǒng)、信息網(wǎng)絡(luò)系統(tǒng)、生產(chǎn)工藝流程以及軍事后勤保障系統(tǒng)等的問題常用圖論模型來描述。網(wǎng)絡(luò)規(guī)劃概述網(wǎng)絡(luò)規(guī)劃(Network

Programming)是圖論與線性規(guī)劃的交叉學(xué)科，具有廣泛的應(yīng)用背景，比如，最短路問題、最小樹問題、最大流問題、最優(yōu)匹配問題等。七橋問題七橋問題圖形ACBD圖論模型原理及方法七橋問題是圖論中的著名問題。1736年，Euler巧妙地將此問題化為圖的不重復(fù)一筆畫問題，并證明了該問題不存在肯定回答。原因在于該圖形有頂點(diǎn)連接奇數(shù)條邊?！?、1

圖的基本概念一個(gè)圖(Graph)

定義為三元有序組G=(V(G),E(G))，V(G)是圖的頂點(diǎn)集合，E(G)是圖的邊集合，n

E(G),

G的邊數(shù);m

V

(G),

G的頂點(diǎn)數(shù);記圖的端點(diǎn)設(shè)G是一個(gè)圖(Graph)G=(V(G),E(G))，e

E(G),u,

v

V

(G),G

(e)

uv則稱e連接u和v，稱u和v是e的端點(diǎn)。稱端點(diǎn)u，v與邊e是關(guān)聯(lián)的，稱兩個(gè)頂點(diǎn)u，v是鄰接的。若設(shè)G是一個(gè)圖，G

(V

(G),

E(G),G

)V

(G)

{v1,

v2

,

v3}E(G)

{e1,

e2

,

e3

,

e4

,

e5}1e2ee34e5ev1v2v3圖７－３G的幾何實(shí)現(xiàn)圖的幾何實(shí)現(xiàn)一個(gè)圖可用一個(gè)幾何圖形表示,稱為圖的幾何實(shí)現(xiàn)，其中每個(gè)頂點(diǎn)用點(diǎn)表示，每條邊用連接端點(diǎn)的線表示。圖的幾何實(shí)現(xiàn)有助與

直觀的了解圖的許多性質(zhì)。說明一個(gè)圖的幾何實(shí)現(xiàn)并不是唯一的；表示頂點(diǎn)的點(diǎn)和表示邊的線的相對(duì)位置并不重要，重要的是圖形描繪出邊與頂點(diǎn)之間保持的相互關(guān)系。常常把一個(gè)圖的圖形當(dāng)作這個(gè)抽象圖自身.并稱圖形的點(diǎn)為頂點(diǎn),圖形的線為邊，圖論中大多數(shù)概念是根據(jù)圖的表示形式

，例如：頂點(diǎn)、邊、多重邊、環(huán)、路、圈、樹等。幾何實(shí)現(xiàn)圖例在一個(gè)圖的幾何實(shí)現(xiàn)中，兩條邊的交點(diǎn)可能不是圖的頂點(diǎn)。例如圖7-4

中，它共有4個(gè)頂點(diǎn)，6條邊；而e

3

與e

4

的交點(diǎn)不是這個(gè)圖的頂點(diǎn)。e4e12ee3v1v45ee62vv34ve41ee2e3v4e5e61v2vv3v4平面圖一個(gè)圖稱為平面圖，如它有一個(gè)平面圖形，使得邊與邊僅在頂點(diǎn)相交。圖7-5就是一個(gè)平面圖，因?yàn)樗梢杂邢旅娴膱D形。1ee2e3e4e5e6v1v2v4圖７－５基本概念端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)。連接同一對(duì)頂點(diǎn)的多條邊稱為多重邊。在圖7-3中，e5

是一個(gè)環(huán)，e1

與e2

是多重邊，v1和e1,e2,e3是關(guān)聯(lián)的，v1與v2,v3是鄰接的。1e2ee34e5e1v2v3v圖７－３鄰接矩陣2e3ee46ev1v2v3v4e5

e1

e7設(shè)G是一個(gè)圖，G=(V(G),E(G))定義圖G的鄰接矩陣A(G)=(aij)為m×m矩陣,其中aij是頂點(diǎn)vi與邊vj相鄰接的邊數(shù)。

0

2

1

1

2

0

1

0

1

1

0

1

1

0

1

1A(G)

關(guān)聯(lián)矩陣0

0

0

1

1

2

0

0

0

1

1

0

0

1

M

(G)

1

1

1

0

0

0

0e23e4ee5e6e711

1

0

0

1

0

1

vv23v4ve1設(shè)G是一個(gè)圖，G=(V(G),E(G))定義圖G的關(guān)聯(lián)矩陣M=(mij)為m×n矩陣；其中mij是頂點(diǎn)vi與邊ej相關(guān)聯(lián)的次數(shù)，取值可能為0、1、2。注圖的鄰接矩陣比它的關(guān)聯(lián)矩陣小的多，因而圖常常以其鄰接矩陣的形式存貯與計(jì)算機(jī)中。關(guān)聯(lián)矩陣和鄰接矩陣統(tǒng)稱圖的矩陣表示。頂點(diǎn)的度設(shè)G是一個(gè)圖，G=(V(G),E(G))定義圖G的頂點(diǎn)v的度為與頂點(diǎn)v相關(guān)聯(lián)的邊數(shù)，記作d(v)2ee3e4e5e6e7v12vv3v4e12d(v

)

31d(v

)

4d

(v

)

33

4d(v

)

4例稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)；稱度為偶數(shù)的頂點(diǎn)為偶點(diǎn)；例010120011M

(G)

1001011000011000011222

222e2e3e4e5e6e71vv2v3v4e1d(v1)

4d(v2

)

33d

(v

)

34d(v

)

424+3+3+4=14=2×7關(guān)聯(lián)矩陣性質(zhì)圖G的關(guān)聯(lián)矩陣M=(mij)為m×n矩陣；則每行元每列元和等于相應(yīng)頂點(diǎn)的度；和等于2和因此，圖G的關(guān)聯(lián)矩陣M所有元既等于所有頂點(diǎn)的度之和，又等于邊數(shù)的2倍。定理 設(shè)G是一個(gè)圖，則d(v)

2vV

(G)推論

圖中奇點(diǎn)的數(shù)目為偶數(shù)。v

V1vV0vV

(G

)

vV1

d

(v)

0(mod

2);vV0

d

(v)

0(mod

2);vV1

d

(v)

1(mod

2),

V1

0(mod

2)證明

記V0

{v

V

(G),

d(v)

0(mod

2)};V1

{v

V

(G),d(v)

1(mod

2)};

d

(v)

d

(v)

d

(v)

0(mod

2);簡(jiǎn)單圖一個(gè)圖稱為簡(jiǎn)單圖，如果它既沒有環(huán)也沒有多重邊。下圖5是簡(jiǎn)單圖。本書只限于

有限簡(jiǎn)單圖，即頂點(diǎn)集與邊集都是有限集的圖。u1u2u3u4f6f3f1

f5

f2f4只有一個(gè)頂點(diǎn)的圖稱為平凡圖；邊集是空集的圖稱為空?qǐng)D。同構(gòu)給定兩個(gè)圖G

(V

(G),E(G),G

)與H

(V

(H),

E(H),H

)稱G和H是同構(gòu)的，記為G

H

，如果存在兩個(gè)一一對(duì)應(yīng)(

,

)

:V

(G)

V

(H

)

:

E(G)

E(H

)使的

G

(e)

uv

H

((e))

(u)

(v)同構(gòu)圖例圖G與圖H是同構(gòu)的。v1v2v3u1u2u3u4GHe6v4e4e2e1e3e5f12f6f3f

f5f4完全圖K

n完全圖是每一對(duì)不同頂點(diǎn)都恰有一邊的簡(jiǎn)單圖；具有n個(gè)頂點(diǎn)的完全圖記為K

n.K5二分圖二分圖是一個(gè)簡(jiǎn)單圖，其頂點(diǎn)集合可分劃成兩個(gè)子集X與Y，使得每條邊的一個(gè)端點(diǎn)在X，另一個(gè)端點(diǎn)在Y;(X,Y)也稱為圖的二分劃。x1x2x3y1y2y3完全二分圖完全二分圖是具有二分劃(X,Y)的二分圖，并且X的每個(gè)頂點(diǎn)與Y的每個(gè)頂點(diǎn)都相連；記為K

m,n，其中X

m,

Y

nK3,3特殊圖例K5K

3,3都是極小的非平面圖子圖稱圖H是圖G的子圖，H

G如果V

(H

)

V

(G)

H

GE(H

)

E(G)H表示關(guān)聯(lián)函數(shù)

GH

GH

G稱H是G的支撐子圖，如果H

G

V

(H

)

V

(G)圖G及其基本圖稱H是G的真子圖，若記為H

G在H的限制。設(shè)W是圖G的一個(gè)非空頂點(diǎn)子集,以W為頂點(diǎn)集，以二端點(diǎn)均在W中的邊的全體為邊集的子圖稱為由W導(dǎo)出的G的子圖，簡(jiǎn)稱導(dǎo)出子圖，記為G[W]。導(dǎo)出子圖G[V-w]記為G-W

，即G

W

G[(V

(G)

\

W

]它是從G中刪除W中頂點(diǎn)以及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖。如果W僅含一個(gè)頂點(diǎn)v，則把G

{v}簡(jiǎn)記為G

v

。頂點(diǎn)導(dǎo)出子圖邊導(dǎo)出子圖設(shè)F是圖G的非空邊子集，以F為邊集，以F中邊的端點(diǎn)全體為頂點(diǎn)集所構(gòu)成的子圖稱為由F導(dǎo)出的G的子圖，簡(jiǎn)稱G的邊導(dǎo)出子圖。記為G[F]。記G-F表示以E(G)\F為邊集的G的支撐子圖，它是從G中刪除F中的邊所得到的子圖。如F={

e}，則記

。G

e

G

{e}子圖圖例v1v2v3v4v5e1e3e2Gv1v2v3v4v5e1e2G的支撐子圖G-{e1

,e

2

,e

3}子圖圖例2v2v3v4e21

5G-{v

,v

}v1v2v51

2

5G[v

,v

,v

]v1v2v3e1e2e3G

[

e1

,e

2

,e

3]

v4徑圖G的一個(gè)有限的點(diǎn)邊交錯(cuò)序列稱為從v0到vk的徑；W

v0e1v1e2v2

ek

vk其中vi與v

i+1是邊ei的頂點(diǎn);

1

i

k頂點(diǎn)vk叫W的終點(diǎn)，頂點(diǎn)v0

稱為w的起點(diǎn)，頂點(diǎn)vi

叫W的 頂點(diǎn)，整數(shù)k稱為W的長度。在簡(jiǎn)單圖中，徑可由頂點(diǎn)序列表示。路、鏈如果徑W的邊不相同，則稱W為一條鏈，W

v0e1v1e2v2

ek

vk鏈長是W中邊的個(gè)數(shù)k。如果W頂點(diǎn)互不相同，則稱W是一條路。記路長d(v0

,vk

)

kuvwxyabdefgh路：xcwhyeuav鏈：wcxdyhwbvgyc圈(回路)如果徑W的起點(diǎn)和終點(diǎn)相同且有正長度，則稱它是一個(gè)閉徑；如果一條閉鏈的頂點(diǎn)互不相同，則稱它是一個(gè)圈（或回路）。稱一個(gè)圈是偶圈（奇圈），如果它的圈長是偶數(shù)（奇數(shù)）。vwxyabdeufgh圈：uavbwhyeuc定理一個(gè)圖是二分圖當(dāng)且僅當(dāng)圖中不存在奇圈。Euler圈Euler圈是指過所有邊一次且恰好一次的閉徑。Euler鏈?zhǔn)侵高^所有邊一次且恰好一次的鏈。vx

wyabdeufghEuler鏈:ydxcwheuavfygvbwc圖例下例給出了一個(gè)圖的徑，鏈和路。徑：uavfyfvgyhwbv鏈：wcxdyhwbvgy路：xcwhyeuav圈：uavbwhyeuEuler鏈:ydxcwheuavfygvbwuvwxyabcdefghEuler型定理定理2

設(shè)G是連通圈，則G是Euler型的充要條件是G沒有奇次數(shù)的頂點(diǎn)。推論1

設(shè)G是

通圖，則G有Euler鏈當(dāng)且僅當(dāng)G最多有兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)。連通性圖G稱為連通的，如果在G的任意兩個(gè)頂點(diǎn)u和v中存在一條(u,v)路。兩點(diǎn)頂點(diǎn)u和v等價(jià)當(dāng)且僅當(dāng)u和v中存在一條(u,v)路不連通圖至少有兩個(gè)連通分支。w表示G的連通分支數(shù)。賦權(quán)圖對(duì)圖G的每條邊e，賦予一實(shí)數(shù)w(e),稱為邊e的權(quán)，可得一賦權(quán)圖。給定賦權(quán)圖的一個(gè)子圖H，定義H的權(quán)為H的所有邊權(quán)的總和。賦權(quán)圖中一條路的權(quán)稱為路長?！?.2

最短路問題賦權(quán)圖中一條路的權(quán)稱為路長。在一個(gè)賦權(quán)圖G上，給定兩個(gè)頂點(diǎn)u和v，所謂u和v最短路是指所有連接頂點(diǎn)u和v的路中路長最短的路；u和v最短路的路長也稱為u和v的距離。例

接11個(gè)城鎮(zhèn)的交通圖以及城市u與v之間的一條最短路。（粗線表示）222211113344566772899uvDijkstra算法Dijkstra算法的基本思想：。設(shè)S是V的真子集，u0

S,S

V

S如果P

u0

uv是從u

0到S

的最短路，則

u

S

，并且P的

(u0

,

u)

段是最短的(u0

,u)

路，所以d

(u0

,

u)

d

(u0

,

u)

w(u,

v)并且d

(u0

,

S)

min{d

(u0

,

u)

w(u,

v),u

S,

v

S}(1)uvu0SPPu1算法標(biāo)號(hào)公式（1）是Dijkstra算法的基礎(chǔ)。算法以標(biāo)號(hào)方式進(jìn)行，每進(jìn)行一次都增加一個(gè)標(biāo)號(hào)點(diǎn)，直至找到所求的最短路。

,

v

v

E(G)d令l

ij表示從頂點(diǎn)v

i到頂點(diǎn)v

j的距離；d

ij表示連接頂點(diǎn)v

I與頂點(diǎn)v

j邊長，即viv

j

E(G)

wij

,i

jijDijkstra算法步驟Step0

在點(diǎn)v

s上標(biāo)號(hào)l

ss=0;Step1

若v

t已標(biāo)號(hào)，轉(zhuǎn)Step4;否則轉(zhuǎn)Step2;Step3

令lskStep2

令S表示所有已標(biāo)號(hào)點(diǎn)，S

表示未標(biāo)號(hào)點(diǎn)，計(jì)算l

sj

，轉(zhuǎn)Step3

min{lsi

dij

,

vi

S,

v

j

S}S

S

{vk

},

S

S

{vk

}Step4

lst是所求的最短路長，f反向追蹤找出所求v

s-v

t最短路.計(jì)算實(shí)例TCEA227474

1

31S

5

B

5

D 5求連接S、T的最短路計(jì)算實(shí)例1求連接S、T的最短路TCEA2

27474

1

31S

5

B

5

D 502計(jì)算實(shí)例2SDBTCEA74

147312

2

5

5

5

求連接S、T的最短路02443計(jì)算實(shí)例求連接S、T的最短路SDBTCEA2

274

147310245

4

5

5

7計(jì)算實(shí)例4DTCEA2

24

147317S

5

B 55求連接S、T的最短路024478計(jì)算實(shí)例5TCEA2

27474

1

31S

5

B

5

D 5求連接S、T的最短路02447813L

ST

=13;S-T最短路為SABEDT實(shí)例評(píng)述Dijkstra算法不僅找到了所求最短路，而且找到了從S點(diǎn)到其他所有頂點(diǎn)的最短路；這些最短路構(gòu)成了圖的

通無圈的支撐子圖，即圖的一個(gè)支撐樹。選址問題設(shè)G表示一個(gè)礦區(qū)的交通

圖，礦一個(gè)礦區(qū)煤炭

站，把哪個(gè)礦井所在地才能使得離站設(shè)在站距井vi和v

j

之間的里程是

cij

；現(xiàn)在需建離最遠(yuǎn)的礦井可

里程最短。這就是最簡(jiǎn)單的選址問題。礦區(qū)的交通

圖是一個(gè)賦權(quán)圖，每個(gè)礦井是圖的一個(gè)頂點(diǎn)。在賦權(quán)圖G中，定義頂點(diǎn)u的離距為：d

(u)

max{d

(u,

v),

v

V

{u}}中心問題網(wǎng)絡(luò)G的一個(gè)中心是滿足下列條件的G的頂點(diǎn)u選址問題可化為求G的中心問題。求圖的中心的算法過程：用Dijkstra算法求出G的任意兩點(diǎn)間的距離；求出每點(diǎn)的離距d(v)求滿足（2）的頂點(diǎn)v即是中心d

(u)

min{d

(v),v

V}（2）實(shí)圖例7-15給出了一個(gè)礦區(qū)的交通圖。應(yīng)把v3v4站建在哪個(gè)礦井才能滿足選址要求？v5v2v6v763221.53v11.81.52.5這個(gè)問題實(shí)際上只需求出G的一個(gè)中心即可。按上面的算法過程，首先利用Dijkstra算法得到圖7-15的距離表；再求出每個(gè)點(diǎn)的離距，最后找出離距的最小者v

6就是建站的礦井。4v1

v2

v3

v4

v5

v6

v7

d

(vi

)v1

0

3

5

6.3

9.3

4.5

6

9.3v2

3

0

2

3.3

6.3

1.5

3

6.3v3

5

2

0

2

5

2.5

4

5v4

6.3

3.3

2

0

3

1.8

3.3

6.3v5

9.3

6.3

2

0

3

1.8

3.3

6.3v6

4.5

1.5

2.5

1.8

4.8 0 1.5v7

6

3

4

3.3

6.3

1.5

0

6.34.8v*=注:Dijkstra算法只適用于所有ｗij≥0的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時(shí)，算法失效。如v1v2v3用Dijkstra算法可以得出從ｖ1到v2的最短路的權(quán)是1，但實(shí)際上從ｖ1到v2的最短路是（ｖ1，v3

，v2），權(quán)是-1。12-3下面介紹具有負(fù)權(quán)賦權(quán)有向圖D的最短路的算法。不妨假設(shè)從任一點(diǎn)vi到任一點(diǎn)vj都有一條?。ㄈ绻贒中，（

vi，vj

）

A，則添加弧（

vi，vj

）令wij=+∞）。顯然，從vs到任一點(diǎn)vj的最短路總是從vs出發(fā)到某個(gè)點(diǎn)

vi，再沿（vi，vj）到vj的，由前面的結(jié)論可知，從vs到vi的這條路必定是從vs到vi的最短路，所以d（vs，vj）必滿足如下方程：d

(v

,

v

)

w

s

i

ijid

(vs

,

v

j

)

minid

(vs

,

v

j

)

m為了求得這個(gè)方程的解d(vs

,v1

),d

(vs

,v2

),,d

(vs

,vn

),可用如下遞推公式：令s

j

sj（1）j

1，2，，n）d

(v

,

v

)

w（對(duì)t

2，3，，mins

i

ij(

j

1,2,,

n)d

(v

,

v

)

w

（t

1）is

jd

(v

,

v

)

（t）若進(jìn)行到某一步，例如第k步時(shí)，對(duì)所有j

1，2，，n，有d（k）(v

,

v

)

d（k

1）(v

,

v

)s

j

s

j則d（k）(v

,

v

（)

j

1，2，，n）既為v

D到各點(diǎn)的最短路的權(quán)。s

j

sv1v2v4v5v6v7v86-1-3v3-283-52-1例：求ｖ1到各點(diǎn)的最短路11-1217-3-5wijd（t）(v

,

v

)1

jv1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5--5v3-30-51-2-2-2-2v4023-7-7-7v5-101-3-3v610-17-1-1-1v7-1-305-5-5v8-5066對(duì)t

2，3，，mins

i

ij(

j

1,2,,

n)d

(v

,

v

)

w

（t

1）is

jd

(v

,

v

)

（t）§7.3最大流問題可行流設(shè)D=(V,A,W)

是一個(gè)有向網(wǎng)絡(luò)。v

s是網(wǎng)絡(luò)的源點(diǎn)v

t是網(wǎng)絡(luò)的匯點(diǎn)。設(shè)f是定義在弧集A上的一個(gè)整數(shù)函數(shù)，如果對(duì)所有弧a

成立0

f

(a)

w(a)并且對(duì)所有中間頂點(diǎn)v

成立f

(v)

f

(v)則稱f

是網(wǎng)絡(luò)D上的一個(gè)可行流。其中，f

+(v)是流出v

的流量，f

-(v)是流入v的流量。流量條件（1）稱為容量限制；即過弧的流量不超過該弧的容量。條件（2）稱為守恒條件，即對(duì)于中間點(diǎn)v

，流入v的流量等于流出v的流量。對(duì)于源點(diǎn)v

s和匯點(diǎn)v

t

，流出源點(diǎn)v

s的流量等于流入?yún)R點(diǎn)v

t的流量，稱之為流

f

的值，記為val

f.即流值s

(vs

,u

)Avalf

f

(v

)

ttsf

(uv

)

f

(v

)

(u,vt

)Af

(v)

f

(vu),(v,u

)Af

(v)

f

(uv)(u

,v)Af

(v

u)網(wǎng)絡(luò)D及其一個(gè)流量3的可行流例（弧上第一個(gè)數(shù)字是流量，第二個(gè)數(shù)字是容量）vsv1v3v4v2vt1,31,22,22,21,22,31,00,1

1,1圖4.1Val

f

=

3最大流網(wǎng)絡(luò)最大流是指給定網(wǎng)絡(luò)上的流值最大的一個(gè)可行流。尋找給定網(wǎng)絡(luò)的最大流及其有效算法是網(wǎng)絡(luò)規(guī)劃的一個(gè)重要問題。Ford與Fulkerson在1957年提出一個(gè)求解網(wǎng)絡(luò)最大流問題的算法，成為Ford

—Fulkerson

算法。Ford

—Fulkerson

算法Ford

—Fulkerson

算法的基本思想是從任意一個(gè)可行流出發(fā)，尋找流的增廣鏈，并在這條增廣鏈上調(diào)整流值，進(jìn)而得到一個(gè)新可行流，依次進(jìn)行下去，直到一個(gè)最大流為止。鏈設(shè)P是網(wǎng)絡(luò)D的一條連接源點(diǎn)v

s和匯點(diǎn)v

t的鏈，則P中的弧可分為兩類：正向弧—弧的方向與P的反向弧—弧的方向與P的一致；記為P+.相反;記為P-.注、鏈不是有向路，鏈的每一邊去掉方向是一條路增廣鏈設(shè)P是網(wǎng)絡(luò)D的一條連接源點(diǎn)v

s和匯點(diǎn)vt的鏈，f

是網(wǎng)絡(luò)D上的一個(gè)可行流.如果P的每一正向弧都是不飽和?。?/p>

f

(a)

w(a）)，而P的每一反向弧的流量都為正（

f

(a)）

0；則稱P是網(wǎng)絡(luò)D的關(guān)于可行流f

的一條增廣鏈。簡(jiǎn)稱增廣鏈。割集設(shè)S、T是網(wǎng)絡(luò)D的兩個(gè)頂點(diǎn)子集，且vs

S,vt

T定義D的一個(gè)割集，簡(jiǎn)稱割為E(S,T

)

{a

A,

a

(u,

v),u

S,

v

T}割集的割量定義為最小割是指割量最小的割w(a)aE

(S

,T

)cap(S,T

)

定理c對(duì)于網(wǎng)絡(luò)的任意流

f

和割E(S,S)成立valf

f

(S)

f

(S)證明由定義可知v

vss

0,

v

vf

(v)

f

(v)

valf

,valf

(

f

(v)

f

(v))

f

(S)

f

(S)vS推論推論1

對(duì)于網(wǎng)絡(luò)的任意流

f

和割E(S,Sc)，成立valf

capK推論2

設(shè)

f

是網(wǎng)絡(luò)的一個(gè)可行流，K是網(wǎng)絡(luò)的一個(gè)割，如果成立

valf

capK則f

是最大流，K是最小割。注：推論2的逆命題也成立，稱為最大流最小割定理，是網(wǎng)絡(luò)理論的一個(gè)重要定理。例可行流f

與增廣鏈PP=

v

s

v1

v2

v

tvsv1v3v4v2vt1,31,22.22,21,22,30,10,1

1,1圖4.1Val

f

=

3定理設(shè)f

是網(wǎng)絡(luò)D上的一個(gè)可行流，則f

是一個(gè)最大流當(dāng)且僅當(dāng)網(wǎng)絡(luò)D不存在f

的增廣鏈。證明（必要性）

設(shè)f

是一個(gè)最大流，假如D中存在f

的增廣鏈P,則可以得到一個(gè)流值更大的流f

1,使得valf1

valf

,

0構(gòu)造過程如下：證明

min{1,2}

02

min{

f

(a),

a

P

},1

min{

w(a)

f

(a),

a

P

},f

(a),1f

f

(a)

,

f

(a)

,

a

Pa

P

a

P其中證明充分性設(shè)網(wǎng)絡(luò)D不存在f

的增廣鏈，令S表示D中可通過用不飽和路把源點(diǎn)與之相連的所有頂點(diǎn)集合，Sc表示S的余集。則從而K=(S,

Sc)是D的割集，進(jìn)而可得K=(S,

Sc)中的弧都是飽和弧，而

K1=(Sc,S)中的弧都是0流弧，否則將產(chǎn)生網(wǎng)絡(luò)D

的一條增廣鏈。因此，f

的流值等于割集K的割量，所以，f是一個(gè)最大流。cs

tx

S,

x

S算例求下面網(wǎng)絡(luò)的最大流vsv1v3v4v2vt852796658圖4.23定理的證明過程蘊(yùn)涵著最大流算法初始流0先給網(wǎng)絡(luò)賦一個(gè)初始0流f

0vsv1v3v4v2vt0,80,50,20,70,90,60,60,8圖4.2-10,50,3尋找增廣鏈1利用標(biāo)號(hào)法尋找流f

0

的增廣鏈P0v3v4v2vt0,80,50,20,70,90,60,60,50,3(-,

∞)vs(+vs,

8)v10,8(+vs,2)圖4.2-1尋找增廣鏈2利用標(biāo)號(hào)法尋找流f

0

的增廣鏈P0v3v2vt0,80,50,20,80,70,90,60,6圖4.2-10,50,3(-,

∞)vs(+vs,

8)v1(+vs,

2)(+v1,5)v4(+v3,

2)尋找增廣鏈3利用標(biāo)號(hào)法尋找流f

0

的增廣鏈v3v20,80,50,20,80,70,90,60,6圖4.2-10,50,3(-,

∞)vs(+vs,

8)v1(+vs,

2)(+v1,5)(+v2,

5)vtv4(+v3,

2)尋找增廣鏈4找到流f0的增廣鏈P0

=v

s

v1

v2

v

t，v30,80,50,20,80,70,90,60,6圖4.2-10,50,3(-,

∞)vs(+vs,

8)v1(+v1,

5)v2(+v2,

5)vtv4(+v3,

2)(+vs,2)調(diào)增量r=5.調(diào)整流值2調(diào)整流值得流值為5的新可行流f

1

，vsv1v3v4v2vt5,85,50,20,75,90,60,60,8圖4.2-20,50,3尋找增廣鏈5利用標(biāo)號(hào)法尋找流f

1

的增廣鏈v3v4v2vt5,85,50,20,75,90,60,60,50,3(-,

∞)vs(+vs,

3)v10,8(+vs,

2)圖4.2-1尋找增廣鏈6利用標(biāo)號(hào)法尋找流f

1

的增廣鏈P1v3v2vt5,85,50,20,80,75,90,60,6圖4.2-10,50,3(-,

∞)vs(+vs,

3)v1(+vs,2)(+v3,

2)v4(+v3,

2)尋找增廣鏈7利用標(biāo)號(hào)法尋找流f1的增廣鏈P1v3v25,85,50,20,80,75,90,60,6圖4.2-10,50,3(-,

∞)vs(+vs,

3)v1(+vs,2)(+v3,

2)(+v4,

2)vtv4(+v3,

2)尋找增廣鏈8找到流f

1

的增廣鏈P1

=v

s

v3

v4

v

t，v1v3v25,85,50,20,80,75,90,60,6圖4.2-10,50,3(-,

∞)vs(+v4,

2)vtv4(+v3,2)調(diào)增量r=2.(+vs,3)(+vs,

2)(+v3,

2)調(diào)整流值3調(diào)整流值得流值為7的新可行流f

2

，vsv1v3v4v2vt5,85,52,22,75,90,60,62,8圖4.2-30,50,3尋找流增廣鏈9利用標(biāo)號(hào)法尋找流f

2

的增廣鏈v3v4v2vt5,85,52,22,75,90,60,62,8圖4.2-10,50,3(-,

∞)vs(+vs,

3)v1尋找流增廣鏈10利用標(biāo)號(hào)法尋找流f

2

的增廣鏈P2v3v4v2v