《图论》第8章 网络模型

[边覆盖]

一个图G=(V,E)，EE，若G的任一个顶点都与E

中的边关联，则称E覆盖G，或称E

为G的一个边覆盖（集）。

E为G的一个边覆盖

EE(u)(uV(e)(e=(v,w)E(v=uw=u)))[极小边覆盖]

E是G的一个极小边覆盖

E为G的一个边覆盖(E1)(E1EE1不是G的边覆盖)8.1匹配的基本概念[边覆盖数]

设G的所有边覆盖为E1、E2、…、Ek，记称为G的边覆盖数。[最小边覆盖]

Ei

称为G的一个最小边覆盖若|Ei|=1。8.1匹配的基本概念[匹配]

G的一个任意两边不相邻的边集合M称为G的一个边独立集或匹配。[极大匹配]

M是G的一个极大匹配

M为G的一个匹配(e)(eEMM{e}不是G的匹配)[匹配数]

设G的所有匹配为M1、M2、…、Mk，记称为G的匹配数。[最大匹配]

Mi

称为G的一个最大匹配若|Mi|=1。8.1匹配的基本概念[例][M-饱和顶点]

设M是G的一个匹配，e=(vi,vj)E。若有eM，则称vi和vj

在M中饱和或是M饱和的。所有关联边都不在M中的顶点称为非M-饱和顶点或是M-不饱和的。若G中的每一个顶点都是M饱和的，则称M为G的一个完美匹配。e1e2e3e4e5e6e7极大匹配：{e1,e4}最大匹配：{e1,e5

,e6}匹配数：38.1匹配的基本概念[定理8-1-1]

设M是G=(V,E)的一个匹配，n=|V|，且G中无孤立点：

(1)设M为G的一个最大匹配，对G中每一个M不饱和顶点取一条关联边，组成边集N，则W=MN为G的一个最小边覆盖。

(2)设W1为G的一个最小边覆盖，将W1中每相邻的边移去一条，设移去的边构成边集N1，则M1=W1N1为G的一个最大匹配。

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

。8.1匹配的基本概念[证明](1)G中的M-饱和顶点数=2|M|，故G中的M-不饱和顶点数=n2|M|。对任一M-不饱和顶点

u，由于G中无孤立点，必有vV

与u邻接，e=(u,v)E

为构成N的一条边。此时eM，否则u

是M-饱和的。且v

必为M-饱和的，否则M{e}形成一个更大的匹配，与M是一个最大匹配矛盾。可见，G中的任一个M-不饱和顶点对应了一条N中的边，且MN=。故有：|N|=n2|M|，且

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

又M为一个最大匹配：|M|=1(G)

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

(2)考察N1和M1的构造过程。易知M1中不存在相邻边，即M1是G的一个匹配。对任意的e=(u,v)W1：

①如果e在G中的任何相邻边都不属于W1，则e与N1的形成无关。

②如果e在G中有两条相邻边e=(r,v)和e=(u,t)如下图，则

e和e不能同时属于W1，否则

W1

{e}构成G的一个更小的覆盖，与W1是G的一个最小覆盖矛盾。eeeruvtW18.1匹配的基本概念eeruvtW1{e}

③不失一般性，设eW1，eW1。此时作类似分析可知，e若存在相邻边e=(r,s)，必有

eW1。将e

或e移到N1中，可得到一个M1-不饱和顶点u

或r

。可见，一条N1中的边对应了一个M1-不饱和顶点，故有：|N1|=n2|M1|。因此：|W1|=|M1|+|N1|=|M1|+n2|M1|=n|M1|

又：W1为一个最小覆盖，|W1|=1(G)

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

(3)M1是G的一个匹配，故有：|M1|1。或1|M1|

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

由(2)：1=n|M1|

故|W|1。而W是G的一个覆盖，|W|1。故|W|=1，即W是G的一个最小覆盖。考虑到|W|=n1，故有1=n1

即有1+1=n

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

故|M1|=1。即M1为G的一个最大匹配。8.1匹配的基本概念[推论]

设G=(V,E)无孤立点，M为G中匹配，W为G中边覆盖，则|M||W|。当|M|=|W|时，W为G中的最小边覆盖，M为G中的完美匹配。[证明]设M是G的一个最大匹配，按照[定理8-1-1](1)构造N，则W=MN是G的一个最小覆盖。将|M|=1(G)，|W|=1(G)，代入上式得：

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

故11

。又|M|1

，|W|

1

故|M|11|W|

当|M|=|W|时，上述等号成立，即|M|=

1=1=|W|G中M-非饱和顶点数=n2|M|=n21=n(1+1)=nn=0

即M是G的一个完美匹配。8.1匹配的基本概念[M交互道]

设G和M如上所述，G的一条M交互道指G中一条路，其中的边在M和EM中交错出现。[M可增广道]

设G和M如上所述，若G的一条M交互道的始点和终点都是M不饱和的，则称该M交互道为一条M可增广道。8.2最大匹配的基本定理[例]

图中红边构成匹配Ｍ。M-交互道8.2最大匹配的基本定理非M-可增广道M-可增广道M-交互道[定理8-2-1]

设G=(V,E)，M为G中匹配，则M为G的最大匹配当且仅当

G中不存在M可增广道。(Berge)[证明]设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

对P中的任一M-饱和顶点vi

，其所有关联边中只有在P1中列明的才属于M（M的独立性）。故对于匹配(MP1)，P中顶点都是(MP1)-不饱和的。因此可以构造M=(MP1)P2（或记为MP），此时M

是G的一个匹配，且|M|=|M+1，与M是G的一个最大匹配矛盾。8.2最大匹配的基本定理

设M不是G的一个最大匹配。设G中另有一个最大匹配M。构造H=MM=NN，其中N=M(MM)，N=M(MM)。由|M|>|M|可得|N|>|N|。考察由H及其关联顶点构成的子图G(H)，其任一顶点或只与N中的一条边关联，或只与N中的一条边关联，或同时与N和N中各一条边关联。故G(H)中的每一个连通分支都是在N和N中交错的路或回路，也是G中的一条M-交互道。

再由|N|>|N|得知，这些连通分支不能全部是回路，至少有一个连通分支是一条始于N的边且终于N的边的路。该路是G中的一条M-可增广道，与条件矛盾。8.2最大匹配的基本定理[二部图的完全匹配]

记二部图为G=(X,Y,E)，|X||Y|，当X中顶点在匹配M中全部饱和时，称M为G的一个完全匹配。[定理8-2-2](Hall

婚姻定理)

二部图G=(X,Y,E)，|X||Y|，存在完全匹配的充要条件是：对任意AX，有|(A)||A|。(A)为A在Y中的像：(A)={y|yYx(xA(x,y)E)}

（条件也称为相异性条件）。[证明]设G存在完全匹配M，则X中所有顶点是M-饱和的。对任一xX，存在唯一的yY，使得(x,y)M。而且对此y，若有(x,y)M，则必x=x（M的独立性）。故对任意AX，有|(A)||A|。8.2最大匹配的基本定理

设对任意AX，有|(A)||A|。欲证存在完全匹配。对n=|X|作归纳。

(1)n=1时，|A|=1，|(A)|1，结论显然成立。

(2)设nk1时，结论成立。

(3)当n=k时，分两种情况讨论：①G中对任意AX，有|A|<|(A)|。此时任取x0X，依条件有

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

(x0,y0)E。构造G=(X,Y,E)，其中：

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

Y=Y{y0}；

E={(x,y)|xXyY(x,y)E}。8.2最大匹配的基本定理对任意AX,依①条件有|A|<|(A)|。由于Y=Y{y0},在G中，当y0(A)时，有|(A)|=|(A)|（对应G的映像）；否则

|(A)|=|(A)|1。故|A||(A)|。综上，G符合归纳假设的条件，即G中存在完全匹配M。构造M{(x0,y0)}，形成G中的一个完全匹配。②G中存在A0X，使得|A0|=|(A0)|。 构造G=(X,Y,E)，其中：X=A0，Y=(A0)，

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

构造G=(X,Y,E)，其中：X=XA0，Y=Y(A0)，

E={(x,y)|xXyY(x,y)E}8.2最大匹配的基本定理对G： 给定任意的AX=A0X，依条件有|A||(A)|，由Y的定义，G中保持了原G中关于A0的映像。因此对于AA0，有

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

或|X|k1，G符合归纳假设的条件。 即G中存在一个从A0到(A0)的完全匹配M1。8.2最大匹配的基本定理对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符合归纳假设的条件。 即G中存在一个从XA0到Y(A0)的完全匹配M2。构造M=M1M2，M即为

n=k

时G中的一个完全匹配。由归纳原理，结论成立。8.2最大匹配的基本定理[推论]

设有二部图G=(X,Y,E)，若对每个结点

xX，都有deg(x)k；对每个结点yY，都有deg(y)k，则G中存在从X到Y的完全匹配。[证明]

任取AX，对每个结点xA，都有deg(x)k，且A中结点各不相邻，故若设A与Y的联接边数为p，则有pk|A|。又对每个结点y(A)，都有deg(y)k，且(A)中结点各不相邻，故若设(A)与X的联接边数为q，则有qk|(A)|。显然p=q，故k|(A)|k|A|，即|(A)||A|。由[定理8.2.2]，G中存在一个从X到Y的完全匹配。8.2最大匹配的基本定理[讨论]当存在AX，使得

|A|>|(A)|时，不可能有A到(A)的完全匹配。定义A的缺数(A)=max{|A||(A)|,0}。定义(G)=max{(A)|AG}。Hall定理讨论了(G)=0的情形。当(G)>0时，有|M|

|X|(G)，即为匹配数的上限。Konig

证明了此上限也是二部图的最大匹配数。8.2最大匹配的基本定理[算法]

寻求二部图的可增广道的匈牙利算法（Edmonds）设二部图(X,Y,E)，标志I、II分别表示饱和点和无法匹配点。初始化时所有顶点没有标志。

1.

任意给定一个初始匹配M，给所有M饱和顶点标记I；

2.

判定X中各点已有标志？

2.1是。M已经是最大匹配，算法结束。

2.2否。找到一个未标记点x0X,U{x0},V

。

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

是，无法扩大匹配。x0标记为II，转[2]。

3.2

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

已标记为I？

3.2.1

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

UU{z}，VV{y}，转[3]。

3.2.3

否。存在从x0y

的可增广道P。给x0,y以标志I，MMP,转[2]。[计算复杂度分析]

算法最多找n条增广路，每条增广道最多处理m

条边，故计算复杂度为O(mn)。8.3最大匹配算法[例]如图，设初始匹配{(x1,y1),(x3,y4),(x4,y5)}8.3最大匹配算法

(1)U={x2}，V=。(U)={y4,y6} y6 (U)V，且无标记。故存在从x2到y6的可增广道。 找到一条可增广道P=(x2,y6)。将x2、y6标记I。

M={(x1,y1),(x3,y4),(x4,y5),(x2,y6)}。x1x2x3x4x5x6y1y2y3y4y5y6x1x2x3x4x5x6y1y2y3y4y5y6■未标记■

标记I■

标记II8.3最大匹配算法

(2)U={x5}，V=。(U)={y5,y6} y5(U)V，且有标记I：(x4,y5)M。

U={x5,x4}，V={y5}。(U)={y5,y6} y6(U)V，且有标记I：(x2,y6)M。

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

U={x5,x4,x2,x3}，V={y5,y6,y4}。(U)={y5,y6,y4,y2} y2(U)V，且无标记。故存在从x5到y2的可增广道。 找到一条可增广道P=(x5,y6,x2,y4,x3,y2)。将x5、y2标记I。

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

(3)U={x6}，V=。(U)={y6} y6(U)V，且有标记：(x5,y6)M。

U={x6,x5}，V={y6}。(U)={y6,y5} y5(U)V，且有标记：(x4,y5)M。

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

(U)=V，给x6标记II。x1x2x3x4x5x6y1y2y3y4y5y6x1x2x3x4x5x6y1y2y3y4y5y68.3最大匹配算法

(4)X中各点均已有标志。M已经是最大匹配，算法结束。x1x2x3x4x5x6y1y2y3y4y5y6[练习]如图，设初始匹配{(x2,y2),(x3,y3),(x5,y5)}8.3最大匹配算法

(1)U={x1}，V=。(U)={y2,y3} y2(U)V，且有标记：(x2,y2)M。

U={x1,x2}，V={y2}。(U)={y2,y3,y1,y4,y5} y1(U)V，且未标记，故存在从x1到y1的可增广道。 找到一条可增广道P=(x1,y2,x2,y1)。将x1、y1标记I。

M={(x1,y1),(x2,y2),(x3,y3),(x5,y5)}。■未标记■

标记I■

标记IIx1x2x3x4x5y1y2y3y4y5[进一步的讨论]Konig

定理：对二部图，最大匹配数=最小顶点覆盖数。带权完全二部图Kn,n

的最佳匹配算法（Kuhn-Munkres

标号法）。最小成本算法。8.3最大匹配算法[网络]

设无回路有向连通图N=(V,A)，在A上定义非负实函数C，使得：N中有且只有一个入度为0的点z和一个出度为0的点z，分别称为源和汇；任意的边aijA，都被赋以实权

cij

0，称为aij

的容量。称这样的N为一个网络（运输网络）。8.4网络流图与最大流[例]

下图是一个网络。8.4网络流图与最大流这里的网络也称“网络流图”，是一个DAG。注意和“作业网络”的区分。[容许流]

网络N=(V,A)的容许流（简称流）是A上的一个非负实函数f，满足：网络N中至少有一个流f=0（零流）8.4网络流图与最大流注意到无回路假设：当图中存在回路时，可能在回路中形成“涡流”，其流动性不能在流量中体现。[定理8-4-1]

给定网络N=(V,A)的一个流

f，源点z的流出量等于汇点z的流入量，即：[证明]

考察恒等式

记fij=0当aijA，上述恒等式写成：8.4网络流图与最大流

由源点z和汇点z的定义以及守恒条件得：故上式化简为即：8.4网络流图与最大流[流量]

设f是网络N=(V,A)的一个流，其流量定义为：[最大流]记最大流量具有最大流量的流fmax称为N的一个最大流。8.4网络流图与最大流[割切]

网络N=(V,A)，z

和z

分别是网络的源和汇，设SV，S=VS，满足zS，zS。定义：

(S,S)={aij

|aij

=

(vi,

vj)A,viS,vjS}A

称为N的一个割切。割切的容量c(S,S)=cij,对所有的aij(S,S)

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

设网络N中一个从z到z

的流f的流量为w,(S,S)为任意一个割切，则w=f(S,S)

f(S,S)由和[证明]记fij=0当aij=A，则：得8.5割切对割切(S,S)又两式相减得8.5割切[推论1]

对网络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割切[定义]

网络N=(V,A)，设有弱连通初等道路

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

对1ik1，若<vi

,vi+1>A，i=1..(k1)，则称<vi,vi+1>为前向弧，否则（即<vi+1,vi>A）称之为后向弧。对N的一个流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时，称P是f-饱和的，否则称P是f-非饱和的。(P)为在满足流f的容许条件下沿P

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

，后向弧，则当P为zz

时，增量后的流量w=

fzi=fzi

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

设N、f

、P如上所述，一条从z

到z

的f-非饱和路P，称为N中的一条f可增路。[定理8-6-1]

网络N中的流f

是最大流当且仅当N中不包含任何f可增路。[证明]

若N中有一条f-可增路P，则P为一条f-非饱和路，(P)>0。按照上述增量的方法构造新的流f，其流量为w=w+(P)>w，与f为一个最大流矛盾。8.6最大流最小割定理

设N中不含任何f-可增路，欲证f为一个最大流。构造S为N中从源z出发经过某一条f-非饱和路可达的所有结点的集合，zS。由于N中不含任何f-可增路，故zS。令S=VS，则(S,S)为N中的一个割切。

(1)考察f(S,S)。对任一<u,v>A，uS，vS，必有fuv=cuv。否则，设fuv<cuv。由S的定义，从z

至u

存在一条f-非饱和路P，(P)>0。将P扩展至v点，按的定义有

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

是一条从z

至v

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

(2)考察f(S,S)。对任一<p,q>A，pS，qS，必有fpq=0。否则，设fpq

>0。由S的定义，从z

至q

存在一条f-非饱和路L，(L)>0。将L

扩展至p

点，有

(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)

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

在任何运输网络中，流的最大值等于最小的割切容量，即wmax=min{c(S,S)}(Ford-Fulkerson)[证明]设网络的一个流f已经取得最大流量。构造集合如下：

(1)zS；

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

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

>0，则yS。此时必有zS，否则从z到z可构造一条f-可增路，与f是最大流矛盾。令S=VS，则(S,S)是一个割切。由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。重复[定理8-6-1]证明(3)过程得证。8.6最大流最小割定理[Ford-Fulkerson标号法]

求运输网络的最大流。基本思想：从一个已知流出发，构造一个流量不断增加的流序列，最后终止于最大流。序列中的每一个流通过探求网络中关于其前继流的f-可增路并沿f-可增路实施增流过程得到。当网络中不再存在任何f-可增路时，就获得了一个最大流。[主控流程] 0.初始化。赋0流，w=0。

I.标号：用标号法求增流路径，若不存在，过程结束。

II.增流：沿增流路径修改路径中各弧流量，获得新的流。删去所有标号，转I。8.7Ford-Fulkerson标号法[标号原理](1)N中的树T=(V(T),A(T))称为一棵

f-非饱和树若 ①zV(T) ②对T中任一顶点v，T中由

z

到v

的路是f-非饱和的。

(2)f-非饱和树的生长：设T是一棵f-非饱和树，令S=V(T)。 ①若(S,S)中存在f<c的弧，则将该弧及其终点加入T； ②若(S,S)中存在f>0的弧，则将该弧及其始点加入T。

(3)若T生长达到z

，则T中的由z

到

z的路为一条f-可增广道。若T在达到z之前停止生长，则f为一个最大流。8.7Ford-Fulkerson标号法I.标号过程：给源

z标号(+z,)任选一已标号顶点

x，对其任一未标号邻接点y若<x,y>A且fxy<cxy，令y=min(x,cxyfxy)，给y

标号(+x,y)；若<y,x>A且fyx>0，令y=min(x,fyx)，给y

标号(x,y)；若z还未得到标号若还有可标记的未标顶点，转(2)否则，无法增流，算法结束。若z得到标号，转II

增流过程。8.7Ford-Fulkerson标号法II.增流过程：令u=z若u

标号为(+v,u)，则fvu=fvu+

z

若u

标号为(v,u)，则fuv=fuv

z

uv，若uz

转(2)否则，w

w+z

，删去全部标号，转I标号。[讨论]当各弧容量为非负整数时，增流的

为整数，问题可在有限步骤内求解，也即网络存在一个整数最大流。实际上非负有理数也可以满足要求。8.7Ford-Fulkerson标号法[例]

(1)网络及流的初始化

容量

流量8.7Ford-Fulkerson标号法abdczz3,04,04,01,05,01,02,02,06,03,0(2)按广度优先标记顶点。处理边的次序为

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

容量

流量标记

8.7Ford-Fulkerson标号法(+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，增流。

容量

流量标记

8.7Ford-Fulkerson标号法(+z,3)(+z,)(+z,4)(+a,3)(+a,1)(+b,2)abdczz3,24,04,21,05,01,02,02,26,03,0(4)删除所有标号。

容量

流量标记

8.7Ford-Fulkerson标号法abdczz3,24,04,21,05,01,02,02,26,03,0(5)按广度优先标记顶点。处理边的次序为

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

容量

流量标记

8.7Ford-Fulkerson标号法(+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，增流。

容量

流量标记

8.7Ford-Fulkerson标号法(+z,1)(+z,)(+z,4)(+a,1)(+a,1)(+d,1)abdczz3,34,04,21,15,01,02,02,26,13,0(7)删除所有标号。

容量

流量标记

8.7Ford-Fulkerson标号法abdczz3,34,04,21,15,01,02,02,26,13,0(8)按广度优先标记顶点。处理边的次序为

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

容量

流量标记

8.7Ford-Fulkerson标号法(+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，增流。

容量

流量标记

8.7Ford-Fulkerson标号法(+c,4)(+z,)(+z,4)(+c,1)(+c,2)(+d,2)abdczz3,34,24,21,15,01,02,22,26,33,0(9)删除所有标号。

容量

流量标记

8.7Ford-Fulkerson标号法abdczz3,34,24,21,15,01,02,22,26,33,0(10)按广度优先标记顶点。处理边的次序为{z,c},{c,a},{c,b}。z得不到标号，算法结束。最大流wmax=5。

容量

流量标记

8.7Ford-Fulkerson标号法(+c,2)(+z,)(+z,2)(+c,1)abdczz3,34,24,21,15,01,02,22,26,33,0[进一步的讨论]Ford-Fulkerson算法的I(2)步对下一个标号顶点的选择不作任何限制时，存在某些缺陷。zkkkk1zab[例]

如图。交替选择z-a-b-z和z-b-a-z增流，每次z=1，经过2k+1次才达到最大流。算法的时间按复杂度不仅仅与网络结构有关，而且与边的容量有关，这使得对算法的分析十分困难。Ford-Fulkerson还指出，当容量是无理数时算法可能失败。8.7Ford-Fulkerson标号法[Edmonds-Karp的改进算法][定理8-7-1Edmonds-Karp

算法]

在Ford-Fulkerson

算法中，如果每次增流都沿一条最短路径进行，则获得最大流的增流次数最多不超过m(n+2)/2次。这里n

和m

分别是网络的顶点数和边数，“最短”指的是包含了最少的边数。(Edmonds-Karp)[证明]略。采用广度优先探测得到的可增广道是最短的增流路径，符合

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

Edmonds-Karp算法的计算复杂度是O(m2n)。8.7Ford-Fulkerson标号法[讨论](1)多发多收问题：增加一个虚拟的源点，从源点向所有发点分别引出有向边，容量为；增加一个虚拟的汇点，从所有收点分别向汇点引出有向边，容量也为。问题转化成为单源单汇。8.7Ford-Fulkerson标号法z1zzz2z1z2[讨论](2)顶点有容量问题：运输网络中，如果将顶点视为转储站，其仓库容量即为顶点的容量。此时，需要增加关于顶点的容量约束条件：输入顶点的总流量不能超过顶点的容量；同样，从顶点输出的总流量也不能超出顶点的容量。例：如图，

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

f(u,y1)+f(u,y2)c(u)8.7Ford-Fulkerson标号法ux3y1x1x2y2将顶点u

分解为两个无容量顶点u+和u，增加有向边(u+,u)，令其容量c(u+,u)=c(u)，如图。问题转化为顶点无容量的情形。8.7Ford-Fulkerson标号法ux3y1x1x2y2u+[练习]

容量abdczz5325135348.7Ford-Fulkerson标号法[解]按广度优先标记顶点。

容量abdczz5325135340000000(+z,3)(+z,)(+z,4)(+a,3)(+c,3)(+b,3)008.7Ford-Fulkerson标号法[解]z=3，增流。

容量abdczz5325135343000330(+z,3)(+z,)(+z,4)(+a,3)(+c,3)(+b,3)008.7Ford-Fulkerson标号法[解]删除所有标号。

容量abdczz5325135343000330008.7Ford-Fulkerson标号法[解]按广度优先标记顶点。

容量abdczz5325135343000330(+c,4)(+z,)(+z,4)(+a,2)(+c,3)(+d,3)008.7Ford-Fulkerson标号法[解]z=3，增流。

容量abdczz5325135343000333(+c,4)(+z,)(+z,4)(+a,2)(+c,3)(+d,3)338.7Ford-Fulkerson标号法[解]删除所有标号。

容量abdczz5325135343000333338.7Ford-Fulkerson标号法[解]按广度优先标记顶点。

容量abdczz5325135343000333(+c,1)(+z,)(+z,1)(+a,1)(+b,1)(+d,1)338.7Ford-Fulkerson标号法[解]z=1，增流。

容量abdczz5325135344011334(+c,1)(+z,)(+z,1)(+a,1)(+b,1)(+d,1)348.7Ford-Fulkerson标号法[解]删除所有标号。z

之后的顶点不能标记，算法结束，w=7。

容量abdczz5325135344011334348.7Ford-Fulkerson标号法[练习]

容量

流量8.7Ford-Fulkerson标号法abdczz15,04,012,05,03,010,07,010,0

结果：

容量

流量8.7Ford-Fulkerson标号法abdczz15,104,412,105,03,310,77,710,71.判定问题与坏算法问题：任给n,mN,问n+m=?

实例：1+1=? 7+8=?…[判定问题]

对问题的每个实例，答案为“是”或“否”之一的一类问题。[例]任意给定一个图G，问G是否是Hamilton图？ 实例：K3是否是一个Hamilton图？8.8图论中的NPC问题通过构造判定问题可以完成某些求解。[例]7+8=？ 构造判定：

7+8是否大于1？

7+8是否大于2？

… 7+8是否大于14？

7+8是否大于15？

由于7+8是整数解，故经过有限次的判定之后，可以获得7+8=15的解。8.8图论中的NPC问题[例]给定图G=(V,E)，求(G)=？ 构造判定： (G)=是否大于1？ (G)=是否大于2？

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

由于(G)|V|<+，故经过有限次的判定之后，可以获得(G)的值。8.8图论中的NPC问题8.8图论中的NPC问题一些判定问题难以用类似的穷举法完成求解。[例]给定图G=(V,E)，问G是否是一个Hamilton图？ 对G的一个实例，考察其顶点的任意一种排列是否在G中形成一个Hamilton回路。n

个顶点的排列数是n!。由Sterling公式（n!估计式）

当n

足够大（>60）时，n!>3n

。可见此时使用穷举法由于计算量太大已失去实际意义。8.8图论中的NPC问题[Edmonds]

当一个判定问题D给定之后，若存在一个多项式P(t)，使得对于D的任何输入长为n

的实例，可以在O(P(n))时间内对这个实例给出答案，则称这种解答的算法的时间复杂度是合理的，称这种算法为有效算法或好算法；否则称之为无效算法或坏的算法。显然，上述通过穷举法判定G是否是一个Hamilton图的算法是一个坏算法。2.Turing机和NPC[Turing机]

称五元组(,S,h,f,C)为一部Turing机。

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

)：状态集，s0是初态，sY

和sN

分别称为yes态和no态。C：双向无穷且可由读写头阅读与改写的“纸带”。C划分成双向无穷地址序列…,C(2),C(1),C(0),C(1),C(2),…h

=h(t)：读写头的头位置函数，t=0,1,2,…。读写头的每个单位时间指着一个地址，若第

t

时间指着C(i)，则记成h(t)=i。规定h(0)=1。8.8图论中的NPC问题8.8图论中的NPC问题初始化

=若输入符号为{x1,x2,…,xn

}，用(i,t)表示第

t

时间C(i)地址上写的带符，规定f

：读写变换。

f

：(S{sY,sN

})S{1,1}8.8图论中的NPC问题f

：读写变换。

f

：(S{sY,sN

})S{1,1}

当s(t)(S{sY,sN

})，t{0,1,2,…}时，规定

f(s(t),(h(t),t))=(p,q,d)结束：出现状态sY

或sN

时，即得到了Turing机的运算结论yes或no。此时停机。

[P问题集合]

若对判定问题D，存在一个多项式P(t)，对于D的任意给定的实例，若此时实例的输入符号为{x1,x2,…,xn

}，其答案是