第九章 网络流理论
流
什么是流？
流就是永恒。
当生命停止，呼吸不再,
流，并未结束。
因为一个生命的终止是另一个生命的开始,
因为地球仍在运转,
太阳还在发光,
时间还在奔流。
个体的生命有限,
宇宙的生命无穷,
流,
与时光共存,
和无限相伴。
流是风，流是雨,
流是奔腾的江河,
流是起伏的山川。
流是婀娜的小草,
在微风中摇曳。
流是我缥缈的思绪,
在缥缈的地方遨游。
§ 9.1 网络与网络流的基本概念
定义 9.1.1 一个 网络 N=(V,A)是指一个连通无环弧且满足下列条件的有向图,
(1) 有一个顶点子集 X，其每个顶点的入度都为 0；
(2) 有一个与 X 不相交的顶点子集 Y，其每个顶点的出度都为 0；
(3) 每条弧都有一个非负的权，称为弧的容量。
注,上述网络 N 可写作 N=(V,X,Y,A,C),X 称为网络的发点集或源点集,Y 称为网络的收点集或汇点集,C 称为网络的容量函数。
例,
定义 9.1.2 网络 N=(V,X,Y,A,C)中的一个 (可行 )流 是指定义在 A 上的一个整值函数 f,
使得,
(1) 对,0 () ()aA fa ca?∈ ≤ ≤,(容量约束 );
(2) 对 (),()()vV X Y f v f v
+
∈? =∪,(流量守恒 )。
其中 ()f v
表示点 v 处入弧上的流量之和,()f v
+
表示点 v 处出弧上的流量之和。
注,(1) 可行流总是存在的，比如 0f ≡ 。
(2) 现实问题中有许多关于网络和流的实例。
比如：产销物资输送网络；输油管线网络；通信数据传输网络等。
定义 9.1.3 设 f 是网络 N=(V,X,Y,A,C)中的一个可行流，则必有 () ()f XfY
+?
= 。
()f X
+
(或 ()f Y
)称为流 f 的 流量,记为 Val f 。
网络最大流问题,给定网络 N=(V,X,Y,A,C)，求 N 中流量最大的可行流 (称为最大流 )。
注,如果一个网络中的源点集和汇点集都只含一个顶点，则称该网络为单源单汇网络。任一网络 N=(V,X,Y,A,C)都可导出一个单源单汇网络。方法如下,
(1) 给 N 添加两个新顶点 s 和 t；
(2) 对 x X?∈,从 s 向 x 连一条弧，其容量为 ∞ (或
()
(,)
vN s
csv
+
∈
∑
);
(3) 对 yY?∈,从 y 向 t 连一条弧，其容量为 ∞ (或
()
(,)
uN t
cut
∈
∑
)。
新添的顶点 s 和 t 分别称为 人工源 和 人工汇,所得的新网络为 (,,,,)NV stAC′ ′′′。
y
1
x
2
x
1
v
2
y
3
v
1
x
3
y
2
v
3
v
4
4
4
4
2
2 2
2
2
22
2
22
2
2
1 1
3
v
1
y
v
3
v
2
v
4
x
2
x
1
3 6
5
2
3 4
1
2 5
2
3
此后的讨论中主要考虑单源单汇网络。
定义 9.1.4 设 N=(V,x,y,A,C)是一个单源单汇网络。 SV?,SVS=? 。用 (,)SS表示尾在 S 中而头在 S 中的所有弧的集合 (即从 S 中的点指向 S 之外点的所有弧之集 )。若 x S∈,
而 y S∈,则称弧集 (,)SS为网络 N 的一个 割 。一个割 (,)SS的 容量 是指 (,)SS中各条弧的容量之和，记为 Cap (,)SS。
例,对网络
令
1235
{,,,,}Sxvvvv=,则割 (,)SS
14 34 54 56
{,,,}vv vv vv vv= 。
注,一个网络 N 可能有多个割，各个割的容量不一定相等。其中容量最小的割称为 N 的
最小割 。
引理 9.1.1 对网络 N 中任一流 f 和任一割 (,)SS，均有
() ()Val f f S f S
+?
=?,
证明：设 f 是网络 N=(V,x,y,A,C)中的流,(,)SS是 N 的一个割，由流的定义,
(),() 0,() () 0,( {})f xValffx fv fv vSx
+?+?
== =?∈?。
故
{}
() () [ () ()] [ () ()]
[(,) (,)] (,) (,)
(,) (,) (,) (,).
vS x vS
vS u u vS u vS u
vSuS vSuS vSuS vSuS
Valf fx fx fv fv fv fv
fvu fuv fvu fuv
f vu f vu f uv f uv
+? +? +?
∈? ∈
∈∈
∈∈ ∈? ∈∈ ∈?
=?+?=?
=?=?
=+
∑ ∑
∑∑ ∑ ∑∑ ∑∑
∑∑ ∑∑ ∑∑ ∑∑
上式中第一式和第三式都表示 S 内部弧上流量之和，故相等；第二式表示从 S 的顶点指向
S 之外点的所有弧上流量之和，因此它等于 ()f S
+；第四式表示从 S 之外的顶点指向 S 中点的所有弧上的流量之和，因此等于 ()f S
。从而 () ()Val f f S f S
+?
=?。 证毕。
定义 9.1.5,对弧 a，若 () 0fa=,则称 a 是 f 零的；
若 () 0fa>,则称 a 是 f 正的；
若 () ()f aca=,则称 a 是 f 饱和的；
若 () ()f aca<,则称 a 是 f 非饱和的。
v
7v
1
v
4
v
3 v6
v
8
v
5
4
1
3
3
42
1
3
23
2
2 2
2
5
6
5
5
x
y
v
2
定理 9.1.1,对网络 N 中任一可行流 f 和任一割 K= (,)SS，均有 Val f CapK≤ 。其中等式成立当且仅当 (,)SS中每条弧都是 f 饱和的而且 (,)SS中每条弧都是 f 零的。
证明：因 f 是可行流，故
() () ()
aK aK
f S f a c a CapK
+
∈∈
=≤=
∑∑
，并且
(,)
() () 0
aSS
fS fa
∈
= ≥
∑
。
由引理 9.1.1,( ) ( )Val f f S f S CapK
+?
=?≤,可见第
一个结论成立。另外注意到 ()f S CapK
+
= 当且仅当
(,)SS中每条弧都是 f 饱和的；而 () 0fS
= 当且仅当
(,)SS 中每条弧都是 f 零的，故定理的第二个结论也成立。证毕。
注,网络 N 的一个割 K 称为 最小割,如果网络 N 中不存在割 K′使得 CapK CapK′< 。
推论 9.1.1 设
*
f 是网络 N 的一个最大流,K
*
是 N 的一个最小割，则
**
Val f CapK≤,
证明显然。
推论 9.1.2 设 f 是 N 的一个可行流,K 是 N 的一个割，若 Val f CapK=,则 f 是最大流而
K 是最小割。
证明：由推论 9.1.1，
**
Val f Val f CapK CapK≤≤ ≤，因 Val f CapK=,故由上式知,
*
Val f Val f=,
*
CapK CapK= 。
证毕。
S S
K
§ 9.2 最大流最小割定理及求最大流的标号算法
一、最大流最小割定理
问题：给定网络 (,,,,)NVxyAC=,如何求 N 中的最大流？
定义 9.2.1 设
1 k
Pxv vy= … 是网络 (,,,,)NVxyAC= 中一条 x-y 路 (无向 )，若弧
1
(,)
ii
vv A
+
∈,则称此弧为路 P 的一条 正向弧 (或称前向弧，顺向弧 )，若弧
1
(,)
ii
vv A
+
∈,则称此弧为路 P 的一条 反向弧
(或称后向弧，逆向弧 )。
例如,在右图所示的路 P 上，所有弧都是正向弧；
在路 Q 上，弧 (v
1
,v
3
)和 (v
2
,v
6
)是正向弧，而 (v
2
,v
4
)和
(v
4
,v
3
)是反向弧。 可见，一条弧是正向弧还是反向弧
与路有关。
定义 9.2.2 设 f 是网络 (,,,,)NVxyAC= 中的一可行流,P 是 N 中一条 x-y 路。如果对于 P 上任一条弧
a
null
，都有
(1) 若弧 a
null
是 P 的正向弧，则 () () () 0fa ca faΔ?>
nullnullnull
null ；
(2) 若弧 a
null
是 P 的反向弧，则 () () 0fa faΔ>
nullnull
null,
则称 P 是流 f 的一条 可增路 。沿路 P 可增加的流量为 () min ()
aP
f Pfa
∈
Δ =Δ
null
，称为路 P 上流的增量或可增量。
例如,在下图中，每条弧上括号内的数字表示弧的容量，括号外的数字是当前流的流量。图（ 1）中虚线所示的路 P 是一条可增路。因
13
(,) 61 5fvvΔ =?=，
34
(,) 2fv vΔ =,
42
(,) 5fv vΔ=，
26
(,) 40 4fv vΔ=?=，故路 P 上的可增量 ( ) min{5,2,5,4} 2fPΔ ==。沿 P 增流后的流网络如图 (2)
所示。
图 (1) 图 (2)
由此可见，如果能找到 N 中一条 f 可增路，则可沿着 P 修改流的值，得到一个流值更大的新流
f,修改办法如下,
() ()
() () ()
(),
aP
aP
P
fa fP
fa fa fP
fa a
+Δ
=?Δ
null
null
null
nullnull
nullnull
若是的正向弧若是的反向弧不在上
，
,(*)
修改后的流值为：
()Val f Val f f P=+Δ。
这给出了求网络 N 的最大流的一个途径：反复找 N 中的可增路，沿可增路将流量扩大，直到找不出可增路为止。直观上想，此时应该已达到最大流。下面的定理证实了这一点。
P
Q
v
2
v
5
x
y
v
3
v
4
v
1
v
6
v
2
v
5
(x)
(y)
v
3
v
4
v
1
v
6
4(4)
3(6)
1(1)
0(3)
2(3)
3(5)
3(5)
0(1)
2(4)
5(5)
v
2
v
5
(x)
(y)
v
3
v
4
v
1
v
6
4(4)
1(6)
1(1)
2(3)
2(3)
5(5)
3(5)
0(1)
0(4)
5(5)
P
定理 9.2.1 (,,,,)NV x yAC 中的流 f 是 N 的最大流当且仅当 N 中不存在 f 可增路。
证明,：必要性：若 N 有 f 可增路，则 f 不是最大流，因为沿 P 按 (*)式修改流可得流值更大的流
f 。
充分性：设 N 中不存在 f 可增路，我们来证明 f 是最大流。令
{|SvV=∈从源 x 到 v 有可增路 }{}x∪,
则 y S?,而 x S∈,从而 (,)KSS= 是 N 中的一个割 (见割定义 )。
对 (,)SS 中的任一条弧 (,)auv=,必定 () ()f aca=,(否则，若 () ()f aca<,因 uS∈,从 x
到 u 有可增路 P,Pa+ 是 S 到 v 的可增路，故 vS∈,矛盾 )；同理，对于 (,)SS中任一条弧
(,)avu=,必定 () 0fa= 。这说明 (,)SS 中每条弧都是 f 饱和的而 (,)SS中每条弧都是 f 零的。由定理 9.1.1,Val f CapK=,再由推论 9.1.2 便知 f 是最大流 (而且当前的 K 是最小割 )。
由定理 9.2.1 的证明立即可知,
推论 9.2.1 (最大流最小割定理,Ford,Fulkerson,1956) 任一个网络 N 中，最大流的流量等于最小割的容量。
由推论 9.2.1 又知,
推论 9.2.2 (整值最大流定理 )，任一网络中，若所有弧的容量都是整数，则最大流的流值也必为整数。
二、求最大流的 Ford－ Fulkerson 标号法
前面已得到求网络 N 中最大流的一种思想：从一个已知流 (例如零流 )开始，递推地构作流值严格增加的流序列。在每一个新的流 f 得出之后，若能找到一条 f 可增路 P，则沿 P 修改流的值，得到一个更大的流
f,作为这个序列中的下一个流；若不存在
f 可增路，则由定理 9.1.1,f 就是最大流，算法终止。
问题,对一个流 f,如何找 f 可增路或判断 f 可增路不存在？
解答,Ford－ Fulkerson 标号法,
标号过程描述,
设当前可行流为 f。
从源点 x 开始。首先给 x 标上∞,即 l(x)＝∞，[ x 称为已标未查顶点，其它顶点称为未标未查顶点]。
任选一已标未查顶点 u，检查其所有尚未标号的邻点。
(1) 对 u 的尚未标号的出邻点 v (即 ()u,v A∈ )，若 (,) (,)cuv f uv>,则给 v 标号,
{ }() min (),(,) (,)lv lu cuv f uv=?，[ v 称为已标未查顶点]；
否则，不给 v 标号。
(2) 对 u 的尚未标号的入邻点 v (即 ()v,u A∈ )，若 (,) 0fvu>,则将 v 标号,
{ }() min (),(,)lv lu f vu=,[ v 称为已标未查顶点]；
否则，不给 v 标号。
当检查完 u 的所有邻点之后,u 称为已标已查顶点。
反复进行上述标、查过程，最终必出现两种结果之一,
(i) 汇点 y 获得标号，此时已得到 f 可增路。沿该路增流。
(ii) y 点未获得标号，但已没有已标未查顶点 (所有已标顶点都已被查，没有更多的新标号顶点 )。
此时当前的流 f 即为最大流 [设当前已标已查的顶点之集为 S，则 (,)SS 为最小割 ]
例如：网络 N(V,x,y,A,C)及其上一个流 f,（括号内数字是弧容量）。
情况 (i)：获得一条 f 可增路 情况 (ii)：已得到最大流和最小割
求网络最大流的 Ford－ Fulkerson 标号算法,
输入：网络 (,,,,)NV x yAC
输出：网络 N 中一个最大流。
第 0 步 (初始化 )：对 aA?∈,令 () 0fa= ；
第 1 步：给源点 x 标号 (,)x ∞ 。,{},LxS==Φ。其中 L 表示已标未查集,S 表示已标已查集。
第 2 步：任取 uL∈,检查 u 的每个尚未标号的邻点 v。
(1) 若 ()vNu
+
∈,v 尚未标号且 (,) (,)Cuv f uv>,则给 v 标号 (,,())ulv+,其中
() min{(),(,) (,)}lv lu Cuv f uv=?。令,{}LLv= ∪ 。
(2) 若 ()vNu
∈,v 尚未标号且 (,) 0fvu>,则给 v 标号 (,,())ulv?,其中
() min{(),(,)}lv lu f vu= 。令,{}LLv= ∪ 。
第 3 步：重复第 2 步，直到汇点 y 被标号，或 y 未被标号但 L =Φ为止。
若是后者，算法结束，当前流是最大流；
若是前者，转下步。
第 4 步：令 zy= 。
第 5 步：若 z 的标号为 (,,()wlz+,则令 (,) (,) ()f wz f wz ly= + ；
若 z 的标号为 (,,()wlz?,则令 (,) (,) ( )f zw f zw ly=? 。
注,不论 z 是哪个点，此处总是 l (y)，因 l (y)是最大的可增量 (沿可增路 )。
第 6 步：若 wx≠,则令 zw=,转第 5 步；
否则，去掉所有的顶点标号，转第 1 步。
v
4
v
1
v
3
x
y
v
2
7(7)
7(9)
5(8)
0(5)
5(9)
0(2)
0(6)
7(10)
5(5)
2
2
3
3
3
∞
v
4
v
1
v
3
x
y
v
2
7(7)
9(9)
7(8)
2(5)
5(9)
0(2)
0(6)
9(10)
5(5)
1
1 1
∞
例,
定理 9.2.2 标号算法结束时所得的流是最大流。
证明：算法结束时,L =Φ,所有已标顶点都已查,S 是所有已标已查顶点的集合。 S ≠Φ (因
y S∈ )。 按照标号规则，对 (,),() ()aSSfaCa?∈ = ；对 (,),() 0aSSfa? ∈=,(否则可得到新的标号顶点，算法不会终止 )。从而
(,) (,) (,) (,)
() () () () (,)
aSS aSS aSS aSS
Valf fa fa fa Ca CapSS
∈∈∈∈
=?===
∑∑∑∑
由推论 9.1.2,f 是最大流，而 (,)SS 是最小割。证毕。
三,Edmends－ Karp 修改标号法,
Ford－ Fulkerson 标号法的缺陷,
(1) 当弧容量为无理数时，可以构造出例子说明算法不能在有限步终止。
见 C.H.Papadimitry 等著，,Combinatorial Optimization－ Algorithms & Complexity》§ 6.3,
或谢政著，《网络算法与复杂性理论》，国防科技大学出版社,2003 年。
(2) 即使弧容量都是有理数或整数，标号算法也不是一个有效算法。
例,
可见，标号算法的计算量并不完全依赖于问题的规模 ν 和 ε,还依赖于容量函数。它不是多项式时间算法。
v
4
v
1
v
5
v
3
x y
v
2
v
6
m
m
mm
mm
m
m
1
v
4
v
1
v
3
x
y
v
2
0(7)
0(9)
0(8)
0(5)
0(9)
0(2)
0(6)
0(10)
0(5)
(v
2
,+,7)(x,+,7)
(x,+,8)
(x,+,∞)
(v
4
,+,7)
(v
1
,+,8)
v
4
v
1
v
3
x
y
v
2
7(7)
7(9)
0(8)
0(5)
0(9)
0(2)
0(6)
7(10)
0(5)
(v
1
,+,5)
(x,+,8)
(x,+,∞)
(v
3
,+,5)
(v
1
,+,8)
增流
v
4
v
1
v
3
x
y
v
2
7(7)
7(9)
5(8)
0(5)
5(9)
0(2)
0(6)
7(10)
5(5)
(v
2
,+,2)(v1,+,3)
(x,+,3)
(x,+,∞)
(v
4
,+,2)
(v
1
,+,3)
v
4
v
1
v
3
x
y
v
2
7(7)
9(9)
7(8)
2(5)
5(9)
0(2)
0(6)
9(10)
5(5)
(v
1
,+,1)
(x,+,1)
(x,+,∞)
(v
1
,+,1)
增流 增流
Edmends－ Karp 修改标号法,
在 Ford－ Fulkerson 标号算法的第 2 步检查已标顶点时，采用“先标先查”规则。
例,
注,
① 先标先查规则，相当于执行广探法；
② 先标先查规则执行的结果相当于求 x 到 y 的最短可增路(层层推进策略)；
③ Edmends－ Karp 修改标号法是有效算法 (弧容量是有理数时 )，其计算复杂性为
2
()O ν ε? 。
§ 9.3 求最大流的 Dinic 算法
一、增量网络
定义 9.3.1 对于网络 N = (V,x,y,A,C)和 N 上的一个可行流 f，构造一个新的网络 N ( f )= (V,x,y,A( f ),
C′ )，其中 A( f )及容量函数 C′ 定义如下,
(1) 若 ()u,v A∈ 且 (,) (,)f uv Cuv<,则 (,) ( )uv A f∈,且 (,) (,) (,)Cuv Cuv fuv′ =? ；
(2) 若 ()u,v A∈ 且 (,) 0fuv>,则 (,) ( )vu A f∈,且 (,) (,)Cvu fuv′ = 。
这样构造的网络 N ( f )称为网络 N 关于流 f 的 增量网络 。
例,
注,
(1) 对应于 N 的每条饱和弧 (u,v),N ( f )中只有一条弧 (v,u),(,) (,) (,)cvu cuv fuv′ = = ；
对应于 N 的每条零流弧 (u,v),N ( f )中只有一条弧 (u,v),(,) (,) (,) (,)cuv cuv cuv fuv′ = =?；
对应于 N 的每条非零流非饱和弧 (u,v),N ( f )中有两条弧 (u,v)和 (v,u),(,) (,) (,)cuv cuv fuv′ =?,
(,) (,)cvu fuv′ = 。
(2) N ( f )中每条弧的容量恰为 N 中相应弧的流可增量。
(3) 严格来讲，增量网络不符合前述网络的定义 (无出度为 0 的点 (源 )和入度为 0 的点 (汇 ))，但因它是在原网络 N 基础上定义的，有明显的源和汇的痕迹，因此我们仍将其看作网络，其中 x 和 y 分别为源和汇，该网络上的一个可行流 f 定义为满足
网络 N 及其一个可行流 f,弧上括号外数字为流量，括号内数字为容量。
2(2)
1(2)
2(3)
0(1)
2(3)
0(2)
1(3)
x
y
增量网络 N(f)。
2
1
1
1
1
2
2
x
y
1
1
2
2
v
3
v
4
v
2
v
1
1000
1000
1000
1000
v
5
x y
v
6
1000 1000
1000 1000
1
() () () 0
() () () 0
() () () 0
fx f x f x
fy f y f y
fu f u f u
+?
+?
+?
=?≥
=?≤
=?=
的流。
定理 9.3.1 设 f 是网络 N 中的一个可行流。则
(1) N 中 f 可增路与 N ( f )中的 x y? 有向路一一对应。
(2) N 中 f 可增路 P 的可增流值 ()f PΔ 等于 N ( f )中对应的 x y? 有向路 P
null
上最小的弧容量。
证明：显然。
定理 9.3..2 设
*
f 是网络 N 中的最大流,f 是 N 中的一个可行流，则增量网络 N ( f )中的最大流的流值为
*
Val f Val f? 。
证明：考虑 N ( f )中的任一个割 (,)SS,对 (,) (,)uv SS?∈,要么 (,) (,)cuv fvu′ = ；要么
(,) (,) (,)cuv cuv fuv′ =?【见注 (1)】。
令,{(,) (,) | (,) (,)}
1
A uv SS c uv f vu′=∈ =,
{(,) (,)| (,) (,) (,)}
2
A uv SS c uv cuv f uv′=∈ =?
则
12
AAφ=∩ 且 ()
12
AAAf=∪ 。
故
(,)(,)
(,) (,)
uv SS
Cap S S c u v
∈
′′=
∑
=
(,) (,)
(,) (,)
12
uv A uv A
cuv cuv
∈∈
′′+
∑∑
(,) (,)
(,) ((,) (,))
12
uv A uv A
f vu cuv f uv
∈∈
=+?
∑∑
(,) (,) (,)
(,) (,) (,)
21 2
uv A uv A uv A
cuv f vu f uv
∈∈ ∈
=+?
∑∑∑
(,Cap S S=）() ()f SfS
+
+? (,)Cap S S Val f=?。
当 f 给定后 min (,) min (,)Cap S S Cap S S Valf′ =?。由最大流最小割定理，
**
Val f Val f Val f=?
null
,
其中
*
f
null
表示 ()Nf中的最大流。
二、网络顶点的分层,
设网络 N = (V,x,y,A,C)，令,{|
i
VvV=∈x 到 v 的最短有向路的长为 i}。设 x 到 y 的最短有向路的长为 n，则 (1),
0 n
x VyV∈∈； (2)
ij
VV=∩ φ,()ji≠ 。
i
V 中的顶点称为网络 N 的第 i 层顶点。
注,这里有向路的长指有向路上有向边的数目。最短有向路指含有向边数最少的有向路。
例,
{},{,},{,,,}
01122345
VxVvvVvvvy= ==
S S
u v
u v
u v
u v
N
N(f)
非零非饱和弧饱和弧零流弧非零非饱和弧
S S
u v
u v
u v
u v
∈A
1
∈A
1
∈A
2
∈A
2
网络 N 网络 N 的分层。
v
1
x
y
v
3
v
2
v
4
v
5
v
1
x
y
v
3
v
2
v
4
v
5
注,(1) 网络顶点分层后，弧有三种可能的情况,
z 从第 i 层顶点指向第 i +1 层顶点；
z 从第 i 层顶点指向第 i 层顶点；
z 从第 i 层顶点指向第 j 层顶点 (j < i )；
(2) 不存在从第 i 层顶点指向第 i+k 层顶点的弧 ()2k ≥ 。
(3) 并非所有网络都能分层。例如，下列网络不能分层。
网络顶点分层的算法 (广探法，广度优先搜索法 ),
给定 N = (V,x,y,A,C),
算法描述 1,
第 0 步：令 {},:
0
0Vxi==,
第 1 步：令,
0
i
ii
k
SV
=
=
∪
若
i
SV=,分层完毕；否则转下步。
第 2 步：令 () {
1iii
VNS S
+
+
==的所有出邻点 }。若
1i
V φ
+
=,则停，网络不能继续分层；否则，转下步。
第 3 步：令,1ii=+，转第 1 步。
算法描述 2,
第 0 步：给 x 标上 0，令
0
{}Vx=,,,:
000
0UVVTVi=? = =。
第 1 步：在 T 中任取顶点 v，找出 v 的所有尚未标号的出邻点，给它们标上 i+1,
第 2 步：令 {}TT v=?,若 T ≠Φ，转第 1 步；否则转下步。
第 3 步：令
1
{
i
V
+
= 标号为 1i + 的所有顶点 }，
11iii
UUV
+ +
=?,
若
11
,
ii
VU
++
≠Φ ≠Φ，则令
1
,,1
i
TV i i
+
= =+，转第 1 步。
若
1i
V
+
≠Φ，但
1i
U
+
=Φ，则停止，分层完毕。
若
1i
V
+
=Φ，但
1i
U
+
≠Φ，则停止，网络不能继续分层。
注,分层算法的复杂性为 O(A)。
三、辅助网络,
定义 9.3.2 设 f 是网络 (,,,,)NV xyAc 的可行流,()Nf是 N 的关于 f 的增量网络，对 ()Nf的顶点按最短有向路分层后，删去比 y 层数高的顶点及与 y 同层的顶点 (保留 y)；再删去从高层指向低层的弧及同层顶点间的弧。所剩的各条弧上的容量与 ()Nf中相同。这样所得的网络是 ()Nf的子网络，称为 N
的关于流 f 的 辅助网络,记为 ()ANf。
x
y
例,
四,Dinic 算法 (1970)
1,基本思想,从任一可行流 f 开始，反复进行如下过程,
(1) 构造增量网络 ()Nf； (2) 对 ()Nf分层并构造辅助网络 ()ANf； (3) 求 ()ANf中一条 x-y 路 P；
(4) 沿 x-y 路 P 增流得到更大的流，并去掉所有的饱和弧。若此时 ()ANf中仍存在 x-y 路，则再沿新的
x-y 路增流，直到剩余网络中没有 x-y 路为止。反复执行上述四步直到新流 f 的增量网络 ()Nf不能分层为止，此时 N 中不再有 f 可增路，因而得到最大流。
更详细地说,Dinic 算法从网络 N 的任一可行流
0
f 开始，构造增量网络
0
()Nf,对
0
()Nf 分层并构造辅助网络
0
()AN f 。在
0
()AN f 中找一条 x-y 路 P，沿 P 增加流，得到可行流
1
0
f,并去掉增流所导致的饱和弧。若此时
0
()AN f 中仍有 x-y 路，再沿新的 x-y 路增加流，得到可行流
2
0
f,并去掉增流所导致的饱和弧。反复执行这个过程，直到剩余网络中没有 x-y 路为止。此时所得的流记为
0
1
f 。
然后对
0
1
f 继续上述过程。经有限次循环后，得一可行流
0
k
f,此时 AN(
0
k
f )中不再有任何 x-y 路，
即 N 中不存在
0
k
f 可增路，从而
0
k
f 便是最大流。
注,构造增量网络的目的：将求 N 中可增路问题化为求 ()Nf中有向 x-y 路；
对 ()Nf分层并作辅助网络的目的：简化 ()Nf，求 ()Nf中最短有向 x-y 路。
2,Dinic 算法步骤,
Step0,在网络 (,,,,)NV x yAC 中任取一个可行流
0
f,令,,
0
00
q
p
pq ff= ==;
Step1,构造增量网络
q
p
()Nf 。
Step2,对增量网络
q
p
()Nf 分层并构造辅助网络
q
p
()AN f 。如果在分层时汇点 y 得不到标号（即不能分层），则结束，当前的
q
p
f 就是 N 的最大流；否则，转 Step3 。
Step3,(找
q
p
()AN f 中的 x-y 路 ) 在辅助网络
q
p
()AN f 中执行如下步骤,
3.0,将源点 x 标号为 (,)1? ∞,令 i,= 0，
i
v = x；
3.1,若
i
v 在
q
p
()ANf 中没有出弧，转 3.4；否则在
q
p
()ANf 任取
i
v 的一条出弧 (,)
ij
vv,转 3.2；
3.2,设
i
v 的标号为 (,)
i
k δ,令 min{,}
jiij
cδ δ=,(其中
ij
c 是
q
p
()ANf 中弧 (i,j)当前的容量 )，将
j
v
标号为 (,)
j
i δ ；
3.3,若
j
v = y，转 Step4；否则令 i = j，转 3.1；
v
4
v
1
v
3
x
y
v
2
7(7)
7(9)
5(8)
0(5)
5(9)
0(2)
0(6)
7(10)
5(5)
v
4
v
1
v
3
x
y
v
2
网络 N 增量网络 N ( f )
v
4
v
1
v
3
x
y
v
2
v
4
v
1
v
3
x
y
v
2
N ( f )的分层网络
辅助网络 AN ( f )
3.4,设
i
v 的标号为 (,)
i
k δ 。若 1k ≠?,在
q
p
()AN f 中删去
i
v 的所有入弧，所得网络仍记为
q
p
()ANf,令 i = k，转 3.1；否则，令,
0
1
q
pp
f f
+
=,p,= p +1,:,0q = 转 Step1。
Step4,(增流 ) 从顶点
y
v 出发按第一个标号反向追踪，求出
q
p
()AN f 的 x-y 路 P，将 P 上每条弧的容量
ij
c 改为
ij y
c δ?,删去容量为 0 的弧，同时把流
q
p
f 增加为流
1q
p
f
+
。将所得网络记为
q+1
p
()AN f,并令
q,= q +1。去掉网络
q
p
()ANf 中所有的标号，转 Step3。
例,
网络 N 及其中一个流 f
0
。图例,f
0
,(c) 增量网络 N ( f
0
)
v
6
v
2
v
5
(x)
(y)
v
3
3(10)
3(3)
3(4)
1(1)
2(7)
1(1)
0(5)
4(6)
2(9)
1(5)
0(2)
0(6)
v
1
v
4
v
7
v
6
v
2
v
5
(x)
(y)
v
3
7
3
1
1
5
4
2
2
6
v
1
v
4
v
7
3
1
3
1
4
2
5
2
7
v
6
v
2
v
5
(x)
(y)
v
3
3(10)
3(3)
4(4)
1(1)
3(7)
1(1)
0(5)
4(6)
3(9)
1(5)
0(2)
0(6)
v
1
v
4
v
7
v
2
v
5
(x)
(y)
v
3
7
2
v
1
v
4
v
7
1
4
5
7
辅助网络 AN ( f
0
)及一条 x-y 路 P 沿 P 增流后的网络流 f
1
v
6
v
2
v
5
(x)
(y)
v
3
7
3
1
1
5
4
3
2
6
v
1
v
4
v
7
3
4
1
4
3
4
2
6
v
2
v
5
(x)
(y)
v
3
1
4
6
6
v
1
v
4
v
7
7
4
增量网络 N ( f
1
) 辅助网络 AN ( f1 )及一条 x-y 路 P
v
6
v
2
v
5
(x)
(y)
v
3
4(10)
3(3)
4(4)
0(1)
4(7)
1(1)
0(5)
4(6)
4(9)
1(5)
0(2)
0(6)
v
1
v
4
v
7
v
6
v
2
v
5
(x)
(y)
v
3
6
3
1
1
5
4
4
2
6
v
1
v
4
v
7
4
4
1
4
4
3
2
5
增量网络 N ( f
1
0
) 沿 P 增流后的网络流 f
1
0
v
6
v
2
v
5
(x)
(y)
v
3
8(10)
3(3)
4(4)
0(1)
4(7)
1(1)
0(5)
4(6)
8(9)
5(5)
0(2)
4(6)
v
1
v
4
v
7
v
2
v
5
(x)
(y)
v
3
3
5
6
v
1
v
4
v
7
6
4
辅助网络 AN ( f
1
0
)及一条 x-y 路 P 沿 P 增流后的网络流 f
1
1
=f
2
v
6
v
2
v
5
(x)
(y)
v
3
2
3
1
1
5
4
8
2 2
v
1
v
4
v
7
8
4
4
5
4
3
2
1
(x)
v
3
v
1
2
辅助网络 AN ( f
2
) AN ( f
2
)无 x-y 路
§ 9.4 最小费用流问题
一、概念
1,费用网络,对网络 (,,,,)NVxyAC=,给其每条弧 (,)uv 赋以一个非负实数 (权 ) (,)wuv,称为弧 (,)uv 的单位费用。这种每条弧都带有单位费用的网络，称为 费用网络,记为
(,,,,,)NVxyACw= 或 (,,,)NVACw=,其中 w 为费用函数。
2,费用网络 (,,,,,)NVxyACw= 中 流 f 的费用,
(,)
() [(,) (,)]
uv A
wf wuv fuv
∈
=?
∑
。
3,最小费用流问题,对于网络 (,,,,,)NVxyACw= 和一个给定的数
0
0v ≥,求 N 中流值为
0
v
且费用最小的可行流。
二、求最小费用流的负费用圈算法
定义 9.4.1 费用网络的增量网络,
设 f 是网络 (,,,,,)NVxyACw= 上的一个可行流,N 关于 f 的 增量网络 为
(,,,(),,)NVxyAfCw′ ′=,
其中 (),,Af C w′′及如下,
(1) 若,)uv A∈（且 (,) (,)f uv Cuv<,则 (,) ( )uv A f∈,且
(,) (,) (,),(,) (,);C uv Cuv f uv w uv wuv′′=?=
(2) 若,)uv A∈（且 (,) 0fuv>,则 (,) ( )vu A f∈,且
(,) (,),(,) (,);C vu f uv w vu wuv′′==?
例,
定义 9.4.2 设 f 是 N 的一个可行流,f ′是 ()Nf的一个可行流，则可得 N 中一个新的可行流
*
f,对
(,)uv A?∈,
*
(,) (,) (,) (,)f uv f uv f uv f vu′′=+?
称
*
f 是 f ′在 f 上的叠加，记为,f f ′+
null
。
引理 9.4.1 设 f 是 N 的可行流,f ′是 ()Nf的一个可行流，则
(),
()()().
Val f f Val f Val f
wf f wf w f
′ ′=+
′ ′′=+
+
+
null
null
网络 N 及其一个可行流 f,每条弧
上的三元数组分别表示 f,(c,w)。
2,(2,2)
1,(3,3)
2,(3,4)
0,(1,1)
2,(3,1)
0,(2,5)
1,(3,2)
x
y
增量网络 N(f),每条弧上的二元数组分别表示 (c′,w′ )。
(2,?2)
(2,3)
(1,4)
(1,1)
(1,1)
(2,5)
(2,2)
x
y
(1,?3)
(1,?2)
(2,?1)
(2,?4)
证明：令
*
f ff′=+
null
。对 N 的任何割 (,)SS,
** * * *
(,)(,) (,)(,)
(,)(,) (,)(,)
() () (,) (,)
((,) (,) (,) ((,) (,) (,)
uv SS uv S S
uv SS uv S S
Val f f S f S f u v f u v
f uv f uv f vu f uv f uv f vu
+?
∈∈
∈∈
=?=?
′′ ′′=++?
∑∑
∑∑
(,)(,) (,)(,)
(,)(,) (,)(,)
(,)(,) (,)(,)
(,) (,)
(,) (,)
(,) (,)
uv SS uv S S
uv SS uv S S
uv SS uv S S
f uv f uv
f uv f vu
f vu f uv
∈∈
∈∈
∈∈
=?
′′++
′′?+
∑∑
∑∑
∑∑
() ()Val f Val f S f S Val f Val f
+?
′′ ′=+? =+。
()
**
(,)
(,)
(,) (,) (,)
() (,)(,)
(,) (,) (,) (,)
(,) (,) (,) (,) (,)( (,))
() ( )
uv A
uv A
uv A uv A uv A
wf f uv wuv
f uv f uv f vu wuv
f uv wuv f uv wuv f vu wuv
wf w f
∈
∈
∈∈ ∈
=?
′′=+
′=?+?+
′′=+
∑
∑
∑∑∑
引理 9.4.2 设 f 和
*
f 是 N 中两个可行流，则 ()Nf中必存在可行流 f ′，满足
*
f ff′=+
null
。
证明：利用 f 和
*
f 来定义 ()Nf中一个流 f ′如下,
对 (,)uv A?∈,
若
*
(,) (,)f uv f uv≥,则定义
*
(,) (,) (,)f uv f uv f uv′ =?，且 (,) 0fvu′ = ；
若
*
(,) (,)f uv f uv<,则定义 (,) 0fuv′ = 且
*
(,) (,) (,)f vu f uv f uv′ =? 。
*ff
uv
≥
→? ；
*ff
uv
<
→?
易验证这样定义的 f ′是 ()Nf中的一个可行流，且
*
f ff′= +
null
。证毕。
例,
引理 9.4.3 设 G 是一个有向图。如果 G 中每个顶点都至少有一条出弧，则 G 包含一个有向圈。
证明 (略 )。
f
*
f
0
v u
0
f? f
*
v u
S S
u
u v
u v
u v
v u
v u
v
S S
u
u v
u v
u v
v u
v u
v
NN(f)
零流弧
非零非饱和弧饱和弧
零流弧
非零非饱和弧饱和弧
f = 4
f
*
= 4
(5)
(2)
f = 2
f
*
=1
(3)
f = 2
f
*
= 3
1(1)
0(2)
0(1)
0(4) 1(2)
0(0)
N 中两个可行流 f 和 f
*
，括号中是弧容量
N( f )及其一个可行流 f ′,括号中是弧容量定义 9.4.3 设 f 是 N 的一个可行流，如果 N 中存在一个有向圈 C，使得对 (,) \ ( )uv A AC? ∈,都有
(,) 0fuv=,则称 f 是 N 的关于圈 C 的圈流，记为
C
f 。
定义 9.4.4 设 f
1
与 f
2
都是 N 中的可行流，定义 f
1
与 f
2
的和 f 为,
12
(,) (,) (,),f uv f uv f uv=+ 对 (,)uv A? ∈ 。
引理 9.4.4 设 f 是 N 上一个流值为 0 的可行流，且 f 不是零流，则 f 可表示为 N 中若干个圈流之和。
证明,令
1
{(,) | (,) 0}AuvAfuv=∈ >。
因 f 不是零流，故
1
A φ≠,设 N
1
是 N 的由弧集
1
A 导出的子网络，则 N 的源、汇点
1
N?,且
1
{(,)|(,) }f uv uv A∈
是 N
1
的一个可行流，即在每条弧上满足容量约束且在 N
1
上每个顶点处都满足流量守恒条件。故 N
1
中每点至少有一条出弧。由引理 9.4.3 知,N
1
有一个有向圈 C
1
。令：
1
min{ (,)|(,) ( )}f uv uv ACδ = ∈,
则可定义 N 中一个圈流
1
C
f 和一个新流
1
f 如下,
1
1
1
,(,) ()
(,)
0,(,) ( )
C
uv AC
fuv
uv AC
δ ∈
=
,
1
1
1
(,),(,) ( )
(,)
(,),(,) ( )
f uv uv AC
fuv
f uv uv AC
δ?∈
=
。
显然
1
1C
f ff=+，且
1
f 至少比 f 多一条流量为 0 的弧。
再考虑
21
{(,) | (,) 0}AuvAfuv=∈ >在 N 中的导出子网络 N
2
，重复上述过程，知 N
2
中含有有向圈
2
C,使得
2
12C
f ff=+，且
2
f 又比 f
1
至少多一条流量为 0 的弧。
如此继续，经有限步后，必须得到
1
k
kCk
f ff
= +,且
k
f 是一个零值流。因此
12 k
CC C
f ff f= ++…+ 。
证毕。
定义 9.4.5,设 f 是 N 的一个可行流,C 是 ()Nf中的一个有向圈，如果
(,) ( )
() (,) 0
uv AC
wC wuv
∈
′′= <
∑
，
则称 C 是 ()Nf的负费用圈。
定理 9.4.1 设 f 是 N 中流值为 v
0
的可行流，则 f 是 N 中最小费用流? ()Nf中没有负费用圈。
证：必要性,用反证法。假设 f 是 N 中最小费用 v
0
值流，但 ()Nf中却有负费用圈 C，即
(,) ( )
(,) 0
uv AC
wuv
∈
′ <
∑
。
令 min{(,)|(,) ( )}cuv uv ACδ ′=∈，则 0δ > 。在 ()Nf上定义一个圈流
C
f 如下,
,(,) ()
(,)
0,(,) ( )
C
uv AC
fuv
uv AC
δ ∈
=
,
于是
(,) ( )
() (,)0
C
uv AC
wf wuvδ
∈
′′=?<
∑
。
令
*
C
f ff=+
null
，由引理 9.4.1 知
*
0C
Val f Val f Val f Val f v=+ ==,
*
( ) () ( ) ()
C
wf wf w f wf′=+ <,
可见 f 不是 N 的最小费用 v
0
值流，矛盾。
充分性,设 ()Nf不含负费用圈，
*
f 是 N 中任一个流值为 v
0
的可行流，则由引理 9.4.2,()Nf
中存在可行流 f ′使得
*
f ff′= +
null
,
（ 1）如果 f ′是 ()Nf中的零 流，则
**
,() ()f fwf wf==。
（ 2）如果 f ′不是 ()Nf中的零 流，则由引理 9.4.1 知
*
00
0Valf Valf Valf v v′=?=?=,
从而由引理 9.4.4
12 k
CC C
f ff f′= ++…+,
其中
i
C
f 为 ()Nf中的圈流,(i = 1,2,…,k )，故
1
() ( )
i
k
C
i
wf wf
=
′′ ′=
∑
。
因 ()Nf不含负费用圈，故 ()0(1,2,,)
i
C
wf i k′ ≥=…，故由引理 9.4.1,
*
( ) () ( ) ()wf wf w f wf′′=+ ≥
由 (1),(2)知,f 为 N 中的最小费用 v
0
值流。证毕。
由定理 9.4.1 可得，求最小费用 v
0
值流的 负费用圈算法,
Step 1：在 N 中运行最大流算法，增流时取
0
min{ ( ),}f Pv fδ = Δ?。要么求出流值为 v
0
的可行流 f，
转 Step 2；要么判定 N 中不存在流值为 v
0
的可行流。停止。
Step 2：构造增量网络 ()Nf，在 ()Nf中找负费用有向圈。如果不存在负费用有向圈，则结束，当前
f 为最小费用 v
0
值流；否则，找到一个负费用有向圈 C，转 Step 3。
Step 3：求 C 上的最小容量 δ,构造 ()Nf的圈流
C
f,令,
C
f ff= +
null
，转 Step 2。
例,求下列网络中从 x 到 y 的流值为 3 的最小费用流。
网 络 N,每条弧 上 的 三 元数 组 分别表示 f,(c,w)。
(2,2)
(2,3)
(3,4)
(1,1)
(3,1)
(2,5)
,(3,2)
x
y
解,(1) 用最大流算法求流值为 3 的可行流 f
1
,
(2) 构造增量网络 N( f
1
)，并找 N( f
1
)中的负费用圈。
(3) 沿负费用圈修改流，得 N 中新的 3 值流 f
2
。
(4) 构造增量网络 N( f
2
)，并找 N( f
2
)中的负费用圈。
(5) 沿负费用圈修改流，得新的 3 值流 f
3
。
网络 N 的一个可行流 f,每条弧
上的三元数组分别表示 f,(c,w)。
2,(2,2)
1,(2,3)
2,(3,4)
0,(1,1)
2,(3,1)
0,(2,5)
1,(3,2)
x
y
增量网络 N(f
1
) 及其一个负费用圈 (虚线所示 )，
每条弧上的二元数组分别表示 (c′,w′ )。
(2,?2)
(1,3)
(1,4)
(1,1)
(1,1)
(2,5)
(2,2)
x
y
(1,?3)
(1,?2)
(2,?1)
(2,?4)
增量网络 N(f
2
)及其一个负费用圈 (虚线所示 )，
每条弧上的二元数组分别表示 (c′,w′ )。
(2,?2)
(1,3)
(2,4)
(1,?1)
(2,1)
(2,5)
(1,2)
x
y
(1,?3)
(2,?2)
(1,?1)
(1,?4)
2,(2,2)
1,(2,3)
1,(3,4)
1,(1,1)
1,(3,1)
0,(2,5)
2,(3,2)
x
y
1,(2,2)
2,(2,3)
0,(3,4)
1,(1,1)
0,(3,1)
0,(2,5)
3,(3,2)
x
y
(6) 构造增量网络 N( f
3
)，并找 N( f
3
)中的负费用圈。
因 N( f
3
)中已无负费用圈，故 f
3
是最小费用 3 值流。
注,（ 1）如果网络 N 中的弧容量全为整数，且 v
0
是非负整数，则负费用有向圈算法在有限步结束。
（ 2）在 N(f)中找负费用圈可利用求最短路的 Floyd 算法。
三、求最小费用流的最小费用路算法
定理 9.4.2 设 f 是网络 (,,,,,)NVxyACw= 上的一个最小费用流，其流值为 V(f),P 是 N(f) 中一条最小费用 x-y 路,δ 是 P 上最小的弧容量,θ 是满足 θ δ≤ 的一个常数，则沿 P 对 f 增流 θ 后所得的流 f ′
是 N 的流值为 V(f) +θ 的最小费用流。
证明：略
由上述定理可得求最小费用流的最小费用路算法。
求最小费用流的最小费用路算法
输入,(,,,,,)NV xyACw,V
0
输出,N 中流值为 V
0
的最小费用流。
Step 0,取零流作为初始可行流 f。
Step1,若 Val f= V
0
，则停止，当前的 f 即为所求的最小费用流，输出 f；否则，转下步。
Step 2,构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，则 N 中无流值为 V
0
的可行流，停止；否则，找出 N( f )的一条最小费用有向路 P，转下步。
Step 3,用 c(P)表示 P 上最小的弧容量，令 min{ ( ),}
0
cp V Valfθ =?,沿 P 对 f 增流 θ,得新流 f，
转 Step1 。
四、求最小费用最大流的算法
问题,求网络 (,,,,,)NV xyACw中的一个费用最小的最大流。
算法,
输入,(,,,,,)NV xyACw,
输出,N 中流值为 V
0
的最小费用流。
Step 0,取零流作为初始可行流 f。
增量网络 N(f
3
)，每条弧上的二元数组分别表示 (c′,w′ )。其中无负费用圈。
(1,?2)
(1,2)
(3,4)
(1,?1) (3,1)
(2,5)
x
y
(2,?3)
(3,?2)
Step1,构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，则当前的 f 即为所求的最小费用最大流，
输出 f；否则，找出 N( f )的一条最小费用有向路 P，转下步。
Step 2,沿 P 对 f 增流，得新的可行流 f，转 Step1 。
五、求总费用限定的最大流的算法
问题,对网络 (,,,,,)NV xyACw和一个预定的总费用值
0
0w ≥,求 N 中总费用不超过
0
w 的一个流，使其流值在所有这样的流中达到最大。
算法,
输入,(,,,,,)NV xyACw；
0
w 。
输出：费用
0
w≤ 的流中流值最大的流。
Step 0,取零流作为初始可行流 f。
Step 1,构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，转 Step 4；否则，找出 N( f )的一条最小费用 x-y 有向路 P，转下步。
Step 2 若 () 0wP′ >,则令
()
min{ ( ),}
()
0
wwf
cP
wP
θ
′=
′
，（ ()cP′ 表示 P 上最小弧容量）,
转 Step3；否则沿 P 对 f 增流，得新的可行流 f，转 Step1。
Step 3 若 0θ =,则停止，当前的 f 便是 N 中费用不超过
0
w 的最大流，输出 f；否则沿 P 对 f 增流值
θ,得新的可行流 f，转 Step1。
第九章习题
1,在下面的网络中，弧上第一 个数字表示流量，第二个数字表示容量。
(1) 确定所有的割；
(2) 求最小割的容量；
(3) 证明给定流是最大流。
2,若 (,)SS 和 (,)TT 都是 N 中的最小割，证明 (,)STST∪∪及 (,)STST∩∩也都是 N 的最小割。
3,对如下网络，从零流开始，分别用 Ford-Fulkson 标号算法和 Dinic 算法求出其最大流，写出或画出算法过程。（注：括号内数字表示弧的容量，括号外数字表示当前流值）。
yx
0(8)
0(7)
0(9)
0(5)
0(2)
0(9)
0(10)
0(5)
v
1
v
3
1(3)
3(4)
3(3)
0(1)
2(5)
2(2)
x
y
v
2
2(2)
流
什么是流？
流就是永恒。
当生命停止，呼吸不再,
流，并未结束。
因为一个生命的终止是另一个生命的开始,
因为地球仍在运转,
太阳还在发光,
时间还在奔流。
个体的生命有限,
宇宙的生命无穷,
流,
与时光共存,
和无限相伴。
流是风，流是雨,
流是奔腾的江河,
流是起伏的山川。
流是婀娜的小草,
在微风中摇曳。
流是我缥缈的思绪,
在缥缈的地方遨游。
§ 9.1 网络与网络流的基本概念
定义 9.1.1 一个 网络 N=(V,A)是指一个连通无环弧且满足下列条件的有向图,
(1) 有一个顶点子集 X，其每个顶点的入度都为 0；
(2) 有一个与 X 不相交的顶点子集 Y，其每个顶点的出度都为 0；
(3) 每条弧都有一个非负的权，称为弧的容量。
注,上述网络 N 可写作 N=(V,X,Y,A,C),X 称为网络的发点集或源点集,Y 称为网络的收点集或汇点集,C 称为网络的容量函数。
例,
定义 9.1.2 网络 N=(V,X,Y,A,C)中的一个 (可行 )流 是指定义在 A 上的一个整值函数 f,
使得,
(1) 对,0 () ()aA fa ca?∈ ≤ ≤,(容量约束 );
(2) 对 (),()()vV X Y f v f v
+
∈? =∪,(流量守恒 )。
其中 ()f v
表示点 v 处入弧上的流量之和,()f v
+
表示点 v 处出弧上的流量之和。
注,(1) 可行流总是存在的，比如 0f ≡ 。
(2) 现实问题中有许多关于网络和流的实例。
比如：产销物资输送网络；输油管线网络；通信数据传输网络等。
定义 9.1.3 设 f 是网络 N=(V,X,Y,A,C)中的一个可行流，则必有 () ()f XfY
+?
= 。
()f X
+
(或 ()f Y
)称为流 f 的 流量,记为 Val f 。
网络最大流问题,给定网络 N=(V,X,Y,A,C)，求 N 中流量最大的可行流 (称为最大流 )。
注,如果一个网络中的源点集和汇点集都只含一个顶点，则称该网络为单源单汇网络。任一网络 N=(V,X,Y,A,C)都可导出一个单源单汇网络。方法如下,
(1) 给 N 添加两个新顶点 s 和 t；
(2) 对 x X?∈,从 s 向 x 连一条弧，其容量为 ∞ (或
()
(,)
vN s
csv
+
∈
∑
);
(3) 对 yY?∈,从 y 向 t 连一条弧，其容量为 ∞ (或
()
(,)
uN t
cut
∈
∑
)。
新添的顶点 s 和 t 分别称为 人工源 和 人工汇,所得的新网络为 (,,,,)NV stAC′ ′′′。
y
1
x
2
x
1
v
2
y
3
v
1
x
3
y
2
v
3
v
4
4
4
4
2
2 2
2
2
22
2
22
2
2
1 1
3
v
1
y
v
3
v
2
v
4
x
2
x
1
3 6
5
2
3 4
1
2 5
2
3
此后的讨论中主要考虑单源单汇网络。
定义 9.1.4 设 N=(V,x,y,A,C)是一个单源单汇网络。 SV?,SVS=? 。用 (,)SS表示尾在 S 中而头在 S 中的所有弧的集合 (即从 S 中的点指向 S 之外点的所有弧之集 )。若 x S∈,
而 y S∈,则称弧集 (,)SS为网络 N 的一个 割 。一个割 (,)SS的 容量 是指 (,)SS中各条弧的容量之和，记为 Cap (,)SS。
例,对网络
令
1235
{,,,,}Sxvvvv=,则割 (,)SS
14 34 54 56
{,,,}vv vv vv vv= 。
注,一个网络 N 可能有多个割，各个割的容量不一定相等。其中容量最小的割称为 N 的
最小割 。
引理 9.1.1 对网络 N 中任一流 f 和任一割 (,)SS，均有
() ()Val f f S f S
+?
=?,
证明：设 f 是网络 N=(V,x,y,A,C)中的流,(,)SS是 N 的一个割，由流的定义,
(),() 0,() () 0,( {})f xValffx fv fv vSx
+?+?
== =?∈?。
故
{}
() () [ () ()] [ () ()]
[(,) (,)] (,) (,)
(,) (,) (,) (,).
vS x vS
vS u u vS u vS u
vSuS vSuS vSuS vSuS
Valf fx fx fv fv fv fv
fvu fuv fvu fuv
f vu f vu f uv f uv
+? +? +?
∈? ∈
∈∈
∈∈ ∈? ∈∈ ∈?
=?+?=?
=?=?
=+
∑ ∑
∑∑ ∑ ∑∑ ∑∑
∑∑ ∑∑ ∑∑ ∑∑
上式中第一式和第三式都表示 S 内部弧上流量之和，故相等；第二式表示从 S 的顶点指向
S 之外点的所有弧上流量之和，因此它等于 ()f S
+；第四式表示从 S 之外的顶点指向 S 中点的所有弧上的流量之和，因此等于 ()f S
。从而 () ()Val f f S f S
+?
=?。 证毕。
定义 9.1.5,对弧 a，若 () 0fa=,则称 a 是 f 零的；
若 () 0fa>,则称 a 是 f 正的；
若 () ()f aca=,则称 a 是 f 饱和的；
若 () ()f aca<,则称 a 是 f 非饱和的。
v
7v
1
v
4
v
3 v6
v
8
v
5
4
1
3
3
42
1
3
23
2
2 2
2
5
6
5
5
x
y
v
2
定理 9.1.1,对网络 N 中任一可行流 f 和任一割 K= (,)SS，均有 Val f CapK≤ 。其中等式成立当且仅当 (,)SS中每条弧都是 f 饱和的而且 (,)SS中每条弧都是 f 零的。
证明：因 f 是可行流，故
() () ()
aK aK
f S f a c a CapK
+
∈∈
=≤=
∑∑
，并且
(,)
() () 0
aSS
fS fa
∈
= ≥
∑
。
由引理 9.1.1,( ) ( )Val f f S f S CapK
+?
=?≤,可见第
一个结论成立。另外注意到 ()f S CapK
+
= 当且仅当
(,)SS中每条弧都是 f 饱和的；而 () 0fS
= 当且仅当
(,)SS 中每条弧都是 f 零的，故定理的第二个结论也成立。证毕。
注,网络 N 的一个割 K 称为 最小割,如果网络 N 中不存在割 K′使得 CapK CapK′< 。
推论 9.1.1 设
*
f 是网络 N 的一个最大流,K
*
是 N 的一个最小割，则
**
Val f CapK≤,
证明显然。
推论 9.1.2 设 f 是 N 的一个可行流,K 是 N 的一个割，若 Val f CapK=,则 f 是最大流而
K 是最小割。
证明：由推论 9.1.1，
**
Val f Val f CapK CapK≤≤ ≤，因 Val f CapK=,故由上式知,
*
Val f Val f=,
*
CapK CapK= 。
证毕。
S S
K
§ 9.2 最大流最小割定理及求最大流的标号算法
一、最大流最小割定理
问题：给定网络 (,,,,)NVxyAC=,如何求 N 中的最大流？
定义 9.2.1 设
1 k
Pxv vy= … 是网络 (,,,,)NVxyAC= 中一条 x-y 路 (无向 )，若弧
1
(,)
ii
vv A
+
∈,则称此弧为路 P 的一条 正向弧 (或称前向弧，顺向弧 )，若弧
1
(,)
ii
vv A
+
∈,则称此弧为路 P 的一条 反向弧
(或称后向弧，逆向弧 )。
例如,在右图所示的路 P 上，所有弧都是正向弧；
在路 Q 上，弧 (v
1
,v
3
)和 (v
2
,v
6
)是正向弧，而 (v
2
,v
4
)和
(v
4
,v
3
)是反向弧。 可见，一条弧是正向弧还是反向弧
与路有关。
定义 9.2.2 设 f 是网络 (,,,,)NVxyAC= 中的一可行流,P 是 N 中一条 x-y 路。如果对于 P 上任一条弧
a
null
，都有
(1) 若弧 a
null
是 P 的正向弧，则 () () () 0fa ca faΔ?>
nullnullnull
null ；
(2) 若弧 a
null
是 P 的反向弧，则 () () 0fa faΔ>
nullnull
null,
则称 P 是流 f 的一条 可增路 。沿路 P 可增加的流量为 () min ()
aP
f Pfa
∈
Δ =Δ
null
，称为路 P 上流的增量或可增量。
例如,在下图中，每条弧上括号内的数字表示弧的容量，括号外的数字是当前流的流量。图（ 1）中虚线所示的路 P 是一条可增路。因
13
(,) 61 5fvvΔ =?=，
34
(,) 2fv vΔ =,
42
(,) 5fv vΔ=，
26
(,) 40 4fv vΔ=?=，故路 P 上的可增量 ( ) min{5,2,5,4} 2fPΔ ==。沿 P 增流后的流网络如图 (2)
所示。
图 (1) 图 (2)
由此可见，如果能找到 N 中一条 f 可增路，则可沿着 P 修改流的值，得到一个流值更大的新流
f,修改办法如下,
() ()
() () ()
(),
aP
aP
P
fa fP
fa fa fP
fa a
+Δ
=?Δ
null
null
null
nullnull
nullnull
若是的正向弧若是的反向弧不在上
，
,(*)
修改后的流值为：
()Val f Val f f P=+Δ。
这给出了求网络 N 的最大流的一个途径：反复找 N 中的可增路，沿可增路将流量扩大，直到找不出可增路为止。直观上想，此时应该已达到最大流。下面的定理证实了这一点。
P
Q
v
2
v
5
x
y
v
3
v
4
v
1
v
6
v
2
v
5
(x)
(y)
v
3
v
4
v
1
v
6
4(4)
3(6)
1(1)
0(3)
2(3)
3(5)
3(5)
0(1)
2(4)
5(5)
v
2
v
5
(x)
(y)
v
3
v
4
v
1
v
6
4(4)
1(6)
1(1)
2(3)
2(3)
5(5)
3(5)
0(1)
0(4)
5(5)
P
定理 9.2.1 (,,,,)NV x yAC 中的流 f 是 N 的最大流当且仅当 N 中不存在 f 可增路。
证明,：必要性：若 N 有 f 可增路，则 f 不是最大流，因为沿 P 按 (*)式修改流可得流值更大的流
f 。
充分性：设 N 中不存在 f 可增路，我们来证明 f 是最大流。令
{|SvV=∈从源 x 到 v 有可增路 }{}x∪,
则 y S?,而 x S∈,从而 (,)KSS= 是 N 中的一个割 (见割定义 )。
对 (,)SS 中的任一条弧 (,)auv=,必定 () ()f aca=,(否则，若 () ()f aca<,因 uS∈,从 x
到 u 有可增路 P,Pa+ 是 S 到 v 的可增路，故 vS∈,矛盾 )；同理，对于 (,)SS中任一条弧
(,)avu=,必定 () 0fa= 。这说明 (,)SS 中每条弧都是 f 饱和的而 (,)SS中每条弧都是 f 零的。由定理 9.1.1,Val f CapK=,再由推论 9.1.2 便知 f 是最大流 (而且当前的 K 是最小割 )。
由定理 9.2.1 的证明立即可知,
推论 9.2.1 (最大流最小割定理,Ford,Fulkerson,1956) 任一个网络 N 中，最大流的流量等于最小割的容量。
由推论 9.2.1 又知,
推论 9.2.2 (整值最大流定理 )，任一网络中，若所有弧的容量都是整数，则最大流的流值也必为整数。
二、求最大流的 Ford－ Fulkerson 标号法
前面已得到求网络 N 中最大流的一种思想：从一个已知流 (例如零流 )开始，递推地构作流值严格增加的流序列。在每一个新的流 f 得出之后，若能找到一条 f 可增路 P，则沿 P 修改流的值，得到一个更大的流
f,作为这个序列中的下一个流；若不存在
f 可增路，则由定理 9.1.1,f 就是最大流，算法终止。
问题,对一个流 f,如何找 f 可增路或判断 f 可增路不存在？
解答,Ford－ Fulkerson 标号法,
标号过程描述,
设当前可行流为 f。
从源点 x 开始。首先给 x 标上∞,即 l(x)＝∞，[ x 称为已标未查顶点，其它顶点称为未标未查顶点]。
任选一已标未查顶点 u，检查其所有尚未标号的邻点。
(1) 对 u 的尚未标号的出邻点 v (即 ()u,v A∈ )，若 (,) (,)cuv f uv>,则给 v 标号,
{ }() min (),(,) (,)lv lu cuv f uv=?，[ v 称为已标未查顶点]；
否则，不给 v 标号。
(2) 对 u 的尚未标号的入邻点 v (即 ()v,u A∈ )，若 (,) 0fvu>,则将 v 标号,
{ }() min (),(,)lv lu f vu=,[ v 称为已标未查顶点]；
否则，不给 v 标号。
当检查完 u 的所有邻点之后,u 称为已标已查顶点。
反复进行上述标、查过程，最终必出现两种结果之一,
(i) 汇点 y 获得标号，此时已得到 f 可增路。沿该路增流。
(ii) y 点未获得标号，但已没有已标未查顶点 (所有已标顶点都已被查，没有更多的新标号顶点 )。
此时当前的流 f 即为最大流 [设当前已标已查的顶点之集为 S，则 (,)SS 为最小割 ]
例如：网络 N(V,x,y,A,C)及其上一个流 f,（括号内数字是弧容量）。
情况 (i)：获得一条 f 可增路 情况 (ii)：已得到最大流和最小割
求网络最大流的 Ford－ Fulkerson 标号算法,
输入：网络 (,,,,)NV x yAC
输出：网络 N 中一个最大流。
第 0 步 (初始化 )：对 aA?∈,令 () 0fa= ；
第 1 步：给源点 x 标号 (,)x ∞ 。,{},LxS==Φ。其中 L 表示已标未查集,S 表示已标已查集。
第 2 步：任取 uL∈,检查 u 的每个尚未标号的邻点 v。
(1) 若 ()vNu
+
∈,v 尚未标号且 (,) (,)Cuv f uv>,则给 v 标号 (,,())ulv+,其中
() min{(),(,) (,)}lv lu Cuv f uv=?。令,{}LLv= ∪ 。
(2) 若 ()vNu
∈,v 尚未标号且 (,) 0fvu>,则给 v 标号 (,,())ulv?,其中
() min{(),(,)}lv lu f vu= 。令,{}LLv= ∪ 。
第 3 步：重复第 2 步，直到汇点 y 被标号，或 y 未被标号但 L =Φ为止。
若是后者，算法结束，当前流是最大流；
若是前者，转下步。
第 4 步：令 zy= 。
第 5 步：若 z 的标号为 (,,()wlz+,则令 (,) (,) ()f wz f wz ly= + ；
若 z 的标号为 (,,()wlz?,则令 (,) (,) ( )f zw f zw ly=? 。
注,不论 z 是哪个点，此处总是 l (y)，因 l (y)是最大的可增量 (沿可增路 )。
第 6 步：若 wx≠,则令 zw=,转第 5 步；
否则，去掉所有的顶点标号，转第 1 步。
v
4
v
1
v
3
x
y
v
2
7(7)
7(9)
5(8)
0(5)
5(9)
0(2)
0(6)
7(10)
5(5)
2
2
3
3
3
∞
v
4
v
1
v
3
x
y
v
2
7(7)
9(9)
7(8)
2(5)
5(9)
0(2)
0(6)
9(10)
5(5)
1
1 1
∞
例,
定理 9.2.2 标号算法结束时所得的流是最大流。
证明：算法结束时,L =Φ,所有已标顶点都已查,S 是所有已标已查顶点的集合。 S ≠Φ (因
y S∈ )。 按照标号规则，对 (,),() ()aSSfaCa?∈ = ；对 (,),() 0aSSfa? ∈=,(否则可得到新的标号顶点，算法不会终止 )。从而
(,) (,) (,) (,)
() () () () (,)
aSS aSS aSS aSS
Valf fa fa fa Ca CapSS
∈∈∈∈
=?===
∑∑∑∑
由推论 9.1.2,f 是最大流，而 (,)SS 是最小割。证毕。
三,Edmends－ Karp 修改标号法,
Ford－ Fulkerson 标号法的缺陷,
(1) 当弧容量为无理数时，可以构造出例子说明算法不能在有限步终止。
见 C.H.Papadimitry 等著，,Combinatorial Optimization－ Algorithms & Complexity》§ 6.3,
或谢政著，《网络算法与复杂性理论》，国防科技大学出版社,2003 年。
(2) 即使弧容量都是有理数或整数，标号算法也不是一个有效算法。
例,
可见，标号算法的计算量并不完全依赖于问题的规模 ν 和 ε,还依赖于容量函数。它不是多项式时间算法。
v
4
v
1
v
5
v
3
x y
v
2
v
6
m
m
mm
mm
m
m
1
v
4
v
1
v
3
x
y
v
2
0(7)
0(9)
0(8)
0(5)
0(9)
0(2)
0(6)
0(10)
0(5)
(v
2
,+,7)(x,+,7)
(x,+,8)
(x,+,∞)
(v
4
,+,7)
(v
1
,+,8)
v
4
v
1
v
3
x
y
v
2
7(7)
7(9)
0(8)
0(5)
0(9)
0(2)
0(6)
7(10)
0(5)
(v
1
,+,5)
(x,+,8)
(x,+,∞)
(v
3
,+,5)
(v
1
,+,8)
增流
v
4
v
1
v
3
x
y
v
2
7(7)
7(9)
5(8)
0(5)
5(9)
0(2)
0(6)
7(10)
5(5)
(v
2
,+,2)(v1,+,3)
(x,+,3)
(x,+,∞)
(v
4
,+,2)
(v
1
,+,3)
v
4
v
1
v
3
x
y
v
2
7(7)
9(9)
7(8)
2(5)
5(9)
0(2)
0(6)
9(10)
5(5)
(v
1
,+,1)
(x,+,1)
(x,+,∞)
(v
1
,+,1)
增流 增流
Edmends－ Karp 修改标号法,
在 Ford－ Fulkerson 标号算法的第 2 步检查已标顶点时，采用“先标先查”规则。
例,
注,
① 先标先查规则，相当于执行广探法；
② 先标先查规则执行的结果相当于求 x 到 y 的最短可增路(层层推进策略)；
③ Edmends－ Karp 修改标号法是有效算法 (弧容量是有理数时 )，其计算复杂性为
2
()O ν ε? 。
§ 9.3 求最大流的 Dinic 算法
一、增量网络
定义 9.3.1 对于网络 N = (V,x,y,A,C)和 N 上的一个可行流 f，构造一个新的网络 N ( f )= (V,x,y,A( f ),
C′ )，其中 A( f )及容量函数 C′ 定义如下,
(1) 若 ()u,v A∈ 且 (,) (,)f uv Cuv<,则 (,) ( )uv A f∈,且 (,) (,) (,)Cuv Cuv fuv′ =? ；
(2) 若 ()u,v A∈ 且 (,) 0fuv>,则 (,) ( )vu A f∈,且 (,) (,)Cvu fuv′ = 。
这样构造的网络 N ( f )称为网络 N 关于流 f 的 增量网络 。
例,
注,
(1) 对应于 N 的每条饱和弧 (u,v),N ( f )中只有一条弧 (v,u),(,) (,) (,)cvu cuv fuv′ = = ；
对应于 N 的每条零流弧 (u,v),N ( f )中只有一条弧 (u,v),(,) (,) (,) (,)cuv cuv cuv fuv′ = =?；
对应于 N 的每条非零流非饱和弧 (u,v),N ( f )中有两条弧 (u,v)和 (v,u),(,) (,) (,)cuv cuv fuv′ =?,
(,) (,)cvu fuv′ = 。
(2) N ( f )中每条弧的容量恰为 N 中相应弧的流可增量。
(3) 严格来讲，增量网络不符合前述网络的定义 (无出度为 0 的点 (源 )和入度为 0 的点 (汇 ))，但因它是在原网络 N 基础上定义的，有明显的源和汇的痕迹，因此我们仍将其看作网络，其中 x 和 y 分别为源和汇，该网络上的一个可行流 f 定义为满足
网络 N 及其一个可行流 f,弧上括号外数字为流量，括号内数字为容量。
2(2)
1(2)
2(3)
0(1)
2(3)
0(2)
1(3)
x
y
增量网络 N(f)。
2
1
1
1
1
2
2
x
y
1
1
2
2
v
3
v
4
v
2
v
1
1000
1000
1000
1000
v
5
x y
v
6
1000 1000
1000 1000
1
() () () 0
() () () 0
() () () 0
fx f x f x
fy f y f y
fu f u f u
+?
+?
+?
=?≥
=?≤
=?=
的流。
定理 9.3.1 设 f 是网络 N 中的一个可行流。则
(1) N 中 f 可增路与 N ( f )中的 x y? 有向路一一对应。
(2) N 中 f 可增路 P 的可增流值 ()f PΔ 等于 N ( f )中对应的 x y? 有向路 P
null
上最小的弧容量。
证明：显然。
定理 9.3..2 设
*
f 是网络 N 中的最大流,f 是 N 中的一个可行流，则增量网络 N ( f )中的最大流的流值为
*
Val f Val f? 。
证明：考虑 N ( f )中的任一个割 (,)SS,对 (,) (,)uv SS?∈,要么 (,) (,)cuv fvu′ = ；要么
(,) (,) (,)cuv cuv fuv′ =?【见注 (1)】。
令,{(,) (,) | (,) (,)}
1
A uv SS c uv f vu′=∈ =,
{(,) (,)| (,) (,) (,)}
2
A uv SS c uv cuv f uv′=∈ =?
则
12
AAφ=∩ 且 ()
12
AAAf=∪ 。
故
(,)(,)
(,) (,)
uv SS
Cap S S c u v
∈
′′=
∑
=
(,) (,)
(,) (,)
12
uv A uv A
cuv cuv
∈∈
′′+
∑∑
(,) (,)
(,) ((,) (,))
12
uv A uv A
f vu cuv f uv
∈∈
=+?
∑∑
(,) (,) (,)
(,) (,) (,)
21 2
uv A uv A uv A
cuv f vu f uv
∈∈ ∈
=+?
∑∑∑
(,Cap S S=）() ()f SfS
+
+? (,)Cap S S Val f=?。
当 f 给定后 min (,) min (,)Cap S S Cap S S Valf′ =?。由最大流最小割定理，
**
Val f Val f Val f=?
null
,
其中
*
f
null
表示 ()Nf中的最大流。
二、网络顶点的分层,
设网络 N = (V,x,y,A,C)，令,{|
i
VvV=∈x 到 v 的最短有向路的长为 i}。设 x 到 y 的最短有向路的长为 n，则 (1),
0 n
x VyV∈∈； (2)
ij
VV=∩ φ,()ji≠ 。
i
V 中的顶点称为网络 N 的第 i 层顶点。
注,这里有向路的长指有向路上有向边的数目。最短有向路指含有向边数最少的有向路。
例,
{},{,},{,,,}
01122345
VxVvvVvvvy= ==
S S
u v
u v
u v
u v
N
N(f)
非零非饱和弧饱和弧零流弧非零非饱和弧
S S
u v
u v
u v
u v
∈A
1
∈A
1
∈A
2
∈A
2
网络 N 网络 N 的分层。
v
1
x
y
v
3
v
2
v
4
v
5
v
1
x
y
v
3
v
2
v
4
v
5
注,(1) 网络顶点分层后，弧有三种可能的情况,
z 从第 i 层顶点指向第 i +1 层顶点；
z 从第 i 层顶点指向第 i 层顶点；
z 从第 i 层顶点指向第 j 层顶点 (j < i )；
(2) 不存在从第 i 层顶点指向第 i+k 层顶点的弧 ()2k ≥ 。
(3) 并非所有网络都能分层。例如，下列网络不能分层。
网络顶点分层的算法 (广探法，广度优先搜索法 ),
给定 N = (V,x,y,A,C),
算法描述 1,
第 0 步：令 {},:
0
0Vxi==,
第 1 步：令,
0
i
ii
k
SV
=
=
∪
若
i
SV=,分层完毕；否则转下步。
第 2 步：令 () {
1iii
VNS S
+
+
==的所有出邻点 }。若
1i
V φ
+
=,则停，网络不能继续分层；否则，转下步。
第 3 步：令,1ii=+，转第 1 步。
算法描述 2,
第 0 步：给 x 标上 0，令
0
{}Vx=,,,:
000
0UVVTVi=? = =。
第 1 步：在 T 中任取顶点 v，找出 v 的所有尚未标号的出邻点，给它们标上 i+1,
第 2 步：令 {}TT v=?,若 T ≠Φ，转第 1 步；否则转下步。
第 3 步：令
1
{
i
V
+
= 标号为 1i + 的所有顶点 }，
11iii
UUV
+ +
=?,
若
11
,
ii
VU
++
≠Φ ≠Φ，则令
1
,,1
i
TV i i
+
= =+，转第 1 步。
若
1i
V
+
≠Φ，但
1i
U
+
=Φ，则停止，分层完毕。
若
1i
V
+
=Φ，但
1i
U
+
≠Φ，则停止，网络不能继续分层。
注,分层算法的复杂性为 O(A)。
三、辅助网络,
定义 9.3.2 设 f 是网络 (,,,,)NV xyAc 的可行流,()Nf是 N 的关于 f 的增量网络，对 ()Nf的顶点按最短有向路分层后，删去比 y 层数高的顶点及与 y 同层的顶点 (保留 y)；再删去从高层指向低层的弧及同层顶点间的弧。所剩的各条弧上的容量与 ()Nf中相同。这样所得的网络是 ()Nf的子网络，称为 N
的关于流 f 的 辅助网络,记为 ()ANf。
x
y
例,
四,Dinic 算法 (1970)
1,基本思想,从任一可行流 f 开始，反复进行如下过程,
(1) 构造增量网络 ()Nf； (2) 对 ()Nf分层并构造辅助网络 ()ANf； (3) 求 ()ANf中一条 x-y 路 P；
(4) 沿 x-y 路 P 增流得到更大的流，并去掉所有的饱和弧。若此时 ()ANf中仍存在 x-y 路，则再沿新的
x-y 路增流，直到剩余网络中没有 x-y 路为止。反复执行上述四步直到新流 f 的增量网络 ()Nf不能分层为止，此时 N 中不再有 f 可增路，因而得到最大流。
更详细地说,Dinic 算法从网络 N 的任一可行流
0
f 开始，构造增量网络
0
()Nf,对
0
()Nf 分层并构造辅助网络
0
()AN f 。在
0
()AN f 中找一条 x-y 路 P，沿 P 增加流，得到可行流
1
0
f,并去掉增流所导致的饱和弧。若此时
0
()AN f 中仍有 x-y 路，再沿新的 x-y 路增加流，得到可行流
2
0
f,并去掉增流所导致的饱和弧。反复执行这个过程，直到剩余网络中没有 x-y 路为止。此时所得的流记为
0
1
f 。
然后对
0
1
f 继续上述过程。经有限次循环后，得一可行流
0
k
f,此时 AN(
0
k
f )中不再有任何 x-y 路，
即 N 中不存在
0
k
f 可增路，从而
0
k
f 便是最大流。
注,构造增量网络的目的：将求 N 中可增路问题化为求 ()Nf中有向 x-y 路；
对 ()Nf分层并作辅助网络的目的：简化 ()Nf，求 ()Nf中最短有向 x-y 路。
2,Dinic 算法步骤,
Step0,在网络 (,,,,)NV x yAC 中任取一个可行流
0
f,令,,
0
00
q
p
pq ff= ==;
Step1,构造增量网络
q
p
()Nf 。
Step2,对增量网络
q
p
()Nf 分层并构造辅助网络
q
p
()AN f 。如果在分层时汇点 y 得不到标号（即不能分层），则结束，当前的
q
p
f 就是 N 的最大流；否则，转 Step3 。
Step3,(找
q
p
()AN f 中的 x-y 路 ) 在辅助网络
q
p
()AN f 中执行如下步骤,
3.0,将源点 x 标号为 (,)1? ∞,令 i,= 0，
i
v = x；
3.1,若
i
v 在
q
p
()ANf 中没有出弧，转 3.4；否则在
q
p
()ANf 任取
i
v 的一条出弧 (,)
ij
vv,转 3.2；
3.2,设
i
v 的标号为 (,)
i
k δ,令 min{,}
jiij
cδ δ=,(其中
ij
c 是
q
p
()ANf 中弧 (i,j)当前的容量 )，将
j
v
标号为 (,)
j
i δ ；
3.3,若
j
v = y，转 Step4；否则令 i = j，转 3.1；
v
4
v
1
v
3
x
y
v
2
7(7)
7(9)
5(8)
0(5)
5(9)
0(2)
0(6)
7(10)
5(5)
v
4
v
1
v
3
x
y
v
2
网络 N 增量网络 N ( f )
v
4
v
1
v
3
x
y
v
2
v
4
v
1
v
3
x
y
v
2
N ( f )的分层网络
辅助网络 AN ( f )
3.4,设
i
v 的标号为 (,)
i
k δ 。若 1k ≠?,在
q
p
()AN f 中删去
i
v 的所有入弧，所得网络仍记为
q
p
()ANf,令 i = k，转 3.1；否则，令,
0
1
q
pp
f f
+
=,p,= p +1,:,0q = 转 Step1。
Step4,(增流 ) 从顶点
y
v 出发按第一个标号反向追踪，求出
q
p
()AN f 的 x-y 路 P，将 P 上每条弧的容量
ij
c 改为
ij y
c δ?,删去容量为 0 的弧，同时把流
q
p
f 增加为流
1q
p
f
+
。将所得网络记为
q+1
p
()AN f,并令
q,= q +1。去掉网络
q
p
()ANf 中所有的标号，转 Step3。
例,
网络 N 及其中一个流 f
0
。图例,f
0
,(c) 增量网络 N ( f
0
)
v
6
v
2
v
5
(x)
(y)
v
3
3(10)
3(3)
3(4)
1(1)
2(7)
1(1)
0(5)
4(6)
2(9)
1(5)
0(2)
0(6)
v
1
v
4
v
7
v
6
v
2
v
5
(x)
(y)
v
3
7
3
1
1
5
4
2
2
6
v
1
v
4
v
7
3
1
3
1
4
2
5
2
7
v
6
v
2
v
5
(x)
(y)
v
3
3(10)
3(3)
4(4)
1(1)
3(7)
1(1)
0(5)
4(6)
3(9)
1(5)
0(2)
0(6)
v
1
v
4
v
7
v
2
v
5
(x)
(y)
v
3
7
2
v
1
v
4
v
7
1
4
5
7
辅助网络 AN ( f
0
)及一条 x-y 路 P 沿 P 增流后的网络流 f
1
v
6
v
2
v
5
(x)
(y)
v
3
7
3
1
1
5
4
3
2
6
v
1
v
4
v
7
3
4
1
4
3
4
2
6
v
2
v
5
(x)
(y)
v
3
1
4
6
6
v
1
v
4
v
7
7
4
增量网络 N ( f
1
) 辅助网络 AN ( f1 )及一条 x-y 路 P
v
6
v
2
v
5
(x)
(y)
v
3
4(10)
3(3)
4(4)
0(1)
4(7)
1(1)
0(5)
4(6)
4(9)
1(5)
0(2)
0(6)
v
1
v
4
v
7
v
6
v
2
v
5
(x)
(y)
v
3
6
3
1
1
5
4
4
2
6
v
1
v
4
v
7
4
4
1
4
4
3
2
5
增量网络 N ( f
1
0
) 沿 P 增流后的网络流 f
1
0
v
6
v
2
v
5
(x)
(y)
v
3
8(10)
3(3)
4(4)
0(1)
4(7)
1(1)
0(5)
4(6)
8(9)
5(5)
0(2)
4(6)
v
1
v
4
v
7
v
2
v
5
(x)
(y)
v
3
3
5
6
v
1
v
4
v
7
6
4
辅助网络 AN ( f
1
0
)及一条 x-y 路 P 沿 P 增流后的网络流 f
1
1
=f
2
v
6
v
2
v
5
(x)
(y)
v
3
2
3
1
1
5
4
8
2 2
v
1
v
4
v
7
8
4
4
5
4
3
2
1
(x)
v
3
v
1
2
辅助网络 AN ( f
2
) AN ( f
2
)无 x-y 路
§ 9.4 最小费用流问题
一、概念
1,费用网络,对网络 (,,,,)NVxyAC=,给其每条弧 (,)uv 赋以一个非负实数 (权 ) (,)wuv,称为弧 (,)uv 的单位费用。这种每条弧都带有单位费用的网络，称为 费用网络,记为
(,,,,,)NVxyACw= 或 (,,,)NVACw=,其中 w 为费用函数。
2,费用网络 (,,,,,)NVxyACw= 中 流 f 的费用,
(,)
() [(,) (,)]
uv A
wf wuv fuv
∈
=?
∑
。
3,最小费用流问题,对于网络 (,,,,,)NVxyACw= 和一个给定的数
0
0v ≥,求 N 中流值为
0
v
且费用最小的可行流。
二、求最小费用流的负费用圈算法
定义 9.4.1 费用网络的增量网络,
设 f 是网络 (,,,,,)NVxyACw= 上的一个可行流,N 关于 f 的 增量网络 为
(,,,(),,)NVxyAfCw′ ′=,
其中 (),,Af C w′′及如下,
(1) 若,)uv A∈（且 (,) (,)f uv Cuv<,则 (,) ( )uv A f∈,且
(,) (,) (,),(,) (,);C uv Cuv f uv w uv wuv′′=?=
(2) 若,)uv A∈（且 (,) 0fuv>,则 (,) ( )vu A f∈,且
(,) (,),(,) (,);C vu f uv w vu wuv′′==?
例,
定义 9.4.2 设 f 是 N 的一个可行流,f ′是 ()Nf的一个可行流，则可得 N 中一个新的可行流
*
f,对
(,)uv A?∈,
*
(,) (,) (,) (,)f uv f uv f uv f vu′′=+?
称
*
f 是 f ′在 f 上的叠加，记为,f f ′+
null
。
引理 9.4.1 设 f 是 N 的可行流,f ′是 ()Nf的一个可行流，则
(),
()()().
Val f f Val f Val f
wf f wf w f
′ ′=+
′ ′′=+
+
+
null
null
网络 N 及其一个可行流 f,每条弧
上的三元数组分别表示 f,(c,w)。
2,(2,2)
1,(3,3)
2,(3,4)
0,(1,1)
2,(3,1)
0,(2,5)
1,(3,2)
x
y
增量网络 N(f),每条弧上的二元数组分别表示 (c′,w′ )。
(2,?2)
(2,3)
(1,4)
(1,1)
(1,1)
(2,5)
(2,2)
x
y
(1,?3)
(1,?2)
(2,?1)
(2,?4)
证明：令
*
f ff′=+
null
。对 N 的任何割 (,)SS,
** * * *
(,)(,) (,)(,)
(,)(,) (,)(,)
() () (,) (,)
((,) (,) (,) ((,) (,) (,)
uv SS uv S S
uv SS uv S S
Val f f S f S f u v f u v
f uv f uv f vu f uv f uv f vu
+?
∈∈
∈∈
=?=?
′′ ′′=++?
∑∑
∑∑
(,)(,) (,)(,)
(,)(,) (,)(,)
(,)(,) (,)(,)
(,) (,)
(,) (,)
(,) (,)
uv SS uv S S
uv SS uv S S
uv SS uv S S
f uv f uv
f uv f vu
f vu f uv
∈∈
∈∈
∈∈
=?
′′++
′′?+
∑∑
∑∑
∑∑
() ()Val f Val f S f S Val f Val f
+?
′′ ′=+? =+。
()
**
(,)
(,)
(,) (,) (,)
() (,)(,)
(,) (,) (,) (,)
(,) (,) (,) (,) (,)( (,))
() ( )
uv A
uv A
uv A uv A uv A
wf f uv wuv
f uv f uv f vu wuv
f uv wuv f uv wuv f vu wuv
wf w f
∈
∈
∈∈ ∈
=?
′′=+
′=?+?+
′′=+
∑
∑
∑∑∑
引理 9.4.2 设 f 和
*
f 是 N 中两个可行流，则 ()Nf中必存在可行流 f ′，满足
*
f ff′=+
null
。
证明：利用 f 和
*
f 来定义 ()Nf中一个流 f ′如下,
对 (,)uv A?∈,
若
*
(,) (,)f uv f uv≥,则定义
*
(,) (,) (,)f uv f uv f uv′ =?，且 (,) 0fvu′ = ；
若
*
(,) (,)f uv f uv<,则定义 (,) 0fuv′ = 且
*
(,) (,) (,)f vu f uv f uv′ =? 。
*ff
uv
≥
→? ；
*ff
uv
<
→?
易验证这样定义的 f ′是 ()Nf中的一个可行流，且
*
f ff′= +
null
。证毕。
例,
引理 9.4.3 设 G 是一个有向图。如果 G 中每个顶点都至少有一条出弧，则 G 包含一个有向圈。
证明 (略 )。
f
*
f
0
v u
0
f? f
*
v u
S S
u
u v
u v
u v
v u
v u
v
S S
u
u v
u v
u v
v u
v u
v
NN(f)
零流弧
非零非饱和弧饱和弧
零流弧
非零非饱和弧饱和弧
f = 4
f
*
= 4
(5)
(2)
f = 2
f
*
=1
(3)
f = 2
f
*
= 3
1(1)
0(2)
0(1)
0(4) 1(2)
0(0)
N 中两个可行流 f 和 f
*
，括号中是弧容量
N( f )及其一个可行流 f ′,括号中是弧容量定义 9.4.3 设 f 是 N 的一个可行流，如果 N 中存在一个有向圈 C，使得对 (,) \ ( )uv A AC? ∈,都有
(,) 0fuv=,则称 f 是 N 的关于圈 C 的圈流，记为
C
f 。
定义 9.4.4 设 f
1
与 f
2
都是 N 中的可行流，定义 f
1
与 f
2
的和 f 为,
12
(,) (,) (,),f uv f uv f uv=+ 对 (,)uv A? ∈ 。
引理 9.4.4 设 f 是 N 上一个流值为 0 的可行流，且 f 不是零流，则 f 可表示为 N 中若干个圈流之和。
证明,令
1
{(,) | (,) 0}AuvAfuv=∈ >。
因 f 不是零流，故
1
A φ≠,设 N
1
是 N 的由弧集
1
A 导出的子网络，则 N 的源、汇点
1
N?,且
1
{(,)|(,) }f uv uv A∈
是 N
1
的一个可行流，即在每条弧上满足容量约束且在 N
1
上每个顶点处都满足流量守恒条件。故 N
1
中每点至少有一条出弧。由引理 9.4.3 知,N
1
有一个有向圈 C
1
。令：
1
min{ (,)|(,) ( )}f uv uv ACδ = ∈,
则可定义 N 中一个圈流
1
C
f 和一个新流
1
f 如下,
1
1
1
,(,) ()
(,)
0,(,) ( )
C
uv AC
fuv
uv AC
δ ∈
=
,
1
1
1
(,),(,) ( )
(,)
(,),(,) ( )
f uv uv AC
fuv
f uv uv AC
δ?∈
=
。
显然
1
1C
f ff=+，且
1
f 至少比 f 多一条流量为 0 的弧。
再考虑
21
{(,) | (,) 0}AuvAfuv=∈ >在 N 中的导出子网络 N
2
，重复上述过程，知 N
2
中含有有向圈
2
C,使得
2
12C
f ff=+，且
2
f 又比 f
1
至少多一条流量为 0 的弧。
如此继续，经有限步后，必须得到
1
k
kCk
f ff
= +,且
k
f 是一个零值流。因此
12 k
CC C
f ff f= ++…+ 。
证毕。
定义 9.4.5,设 f 是 N 的一个可行流,C 是 ()Nf中的一个有向圈，如果
(,) ( )
() (,) 0
uv AC
wC wuv
∈
′′= <
∑
，
则称 C 是 ()Nf的负费用圈。
定理 9.4.1 设 f 是 N 中流值为 v
0
的可行流，则 f 是 N 中最小费用流? ()Nf中没有负费用圈。
证：必要性,用反证法。假设 f 是 N 中最小费用 v
0
值流，但 ()Nf中却有负费用圈 C，即
(,) ( )
(,) 0
uv AC
wuv
∈
′ <
∑
。
令 min{(,)|(,) ( )}cuv uv ACδ ′=∈，则 0δ > 。在 ()Nf上定义一个圈流
C
f 如下,
,(,) ()
(,)
0,(,) ( )
C
uv AC
fuv
uv AC
δ ∈
=
,
于是
(,) ( )
() (,)0
C
uv AC
wf wuvδ
∈
′′=?<
∑
。
令
*
C
f ff=+
null
，由引理 9.4.1 知
*
0C
Val f Val f Val f Val f v=+ ==,
*
( ) () ( ) ()
C
wf wf w f wf′=+ <,
可见 f 不是 N 的最小费用 v
0
值流，矛盾。
充分性,设 ()Nf不含负费用圈，
*
f 是 N 中任一个流值为 v
0
的可行流，则由引理 9.4.2,()Nf
中存在可行流 f ′使得
*
f ff′= +
null
,
（ 1）如果 f ′是 ()Nf中的零 流，则
**
,() ()f fwf wf==。
（ 2）如果 f ′不是 ()Nf中的零 流，则由引理 9.4.1 知
*
00
0Valf Valf Valf v v′=?=?=,
从而由引理 9.4.4
12 k
CC C
f ff f′= ++…+,
其中
i
C
f 为 ()Nf中的圈流,(i = 1,2,…,k )，故
1
() ( )
i
k
C
i
wf wf
=
′′ ′=
∑
。
因 ()Nf不含负费用圈，故 ()0(1,2,,)
i
C
wf i k′ ≥=…，故由引理 9.4.1,
*
( ) () ( ) ()wf wf w f wf′′=+ ≥
由 (1),(2)知,f 为 N 中的最小费用 v
0
值流。证毕。
由定理 9.4.1 可得，求最小费用 v
0
值流的 负费用圈算法,
Step 1：在 N 中运行最大流算法，增流时取
0
min{ ( ),}f Pv fδ = Δ?。要么求出流值为 v
0
的可行流 f，
转 Step 2；要么判定 N 中不存在流值为 v
0
的可行流。停止。
Step 2：构造增量网络 ()Nf，在 ()Nf中找负费用有向圈。如果不存在负费用有向圈，则结束，当前
f 为最小费用 v
0
值流；否则，找到一个负费用有向圈 C，转 Step 3。
Step 3：求 C 上的最小容量 δ,构造 ()Nf的圈流
C
f,令,
C
f ff= +
null
，转 Step 2。
例,求下列网络中从 x 到 y 的流值为 3 的最小费用流。
网 络 N,每条弧 上 的 三 元数 组 分别表示 f,(c,w)。
(2,2)
(2,3)
(3,4)
(1,1)
(3,1)
(2,5)
,(3,2)
x
y
解,(1) 用最大流算法求流值为 3 的可行流 f
1
,
(2) 构造增量网络 N( f
1
)，并找 N( f
1
)中的负费用圈。
(3) 沿负费用圈修改流，得 N 中新的 3 值流 f
2
。
(4) 构造增量网络 N( f
2
)，并找 N( f
2
)中的负费用圈。
(5) 沿负费用圈修改流，得新的 3 值流 f
3
。
网络 N 的一个可行流 f,每条弧
上的三元数组分别表示 f,(c,w)。
2,(2,2)
1,(2,3)
2,(3,4)
0,(1,1)
2,(3,1)
0,(2,5)
1,(3,2)
x
y
增量网络 N(f
1
) 及其一个负费用圈 (虚线所示 )，
每条弧上的二元数组分别表示 (c′,w′ )。
(2,?2)
(1,3)
(1,4)
(1,1)
(1,1)
(2,5)
(2,2)
x
y
(1,?3)
(1,?2)
(2,?1)
(2,?4)
增量网络 N(f
2
)及其一个负费用圈 (虚线所示 )，
每条弧上的二元数组分别表示 (c′,w′ )。
(2,?2)
(1,3)
(2,4)
(1,?1)
(2,1)
(2,5)
(1,2)
x
y
(1,?3)
(2,?2)
(1,?1)
(1,?4)
2,(2,2)
1,(2,3)
1,(3,4)
1,(1,1)
1,(3,1)
0,(2,5)
2,(3,2)
x
y
1,(2,2)
2,(2,3)
0,(3,4)
1,(1,1)
0,(3,1)
0,(2,5)
3,(3,2)
x
y
(6) 构造增量网络 N( f
3
)，并找 N( f
3
)中的负费用圈。
因 N( f
3
)中已无负费用圈，故 f
3
是最小费用 3 值流。
注,（ 1）如果网络 N 中的弧容量全为整数，且 v
0
是非负整数，则负费用有向圈算法在有限步结束。
（ 2）在 N(f)中找负费用圈可利用求最短路的 Floyd 算法。
三、求最小费用流的最小费用路算法
定理 9.4.2 设 f 是网络 (,,,,,)NVxyACw= 上的一个最小费用流，其流值为 V(f),P 是 N(f) 中一条最小费用 x-y 路,δ 是 P 上最小的弧容量,θ 是满足 θ δ≤ 的一个常数，则沿 P 对 f 增流 θ 后所得的流 f ′
是 N 的流值为 V(f) +θ 的最小费用流。
证明：略
由上述定理可得求最小费用流的最小费用路算法。
求最小费用流的最小费用路算法
输入,(,,,,,)NV xyACw,V
0
输出,N 中流值为 V
0
的最小费用流。
Step 0,取零流作为初始可行流 f。
Step1,若 Val f= V
0
，则停止，当前的 f 即为所求的最小费用流，输出 f；否则，转下步。
Step 2,构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，则 N 中无流值为 V
0
的可行流，停止；否则，找出 N( f )的一条最小费用有向路 P，转下步。
Step 3,用 c(P)表示 P 上最小的弧容量，令 min{ ( ),}
0
cp V Valfθ =?,沿 P 对 f 增流 θ,得新流 f，
转 Step1 。
四、求最小费用最大流的算法
问题,求网络 (,,,,,)NV xyACw中的一个费用最小的最大流。
算法,
输入,(,,,,,)NV xyACw,
输出,N 中流值为 V
0
的最小费用流。
Step 0,取零流作为初始可行流 f。
增量网络 N(f
3
)，每条弧上的二元数组分别表示 (c′,w′ )。其中无负费用圈。
(1,?2)
(1,2)
(3,4)
(1,?1) (3,1)
(2,5)
x
y
(2,?3)
(3,?2)
Step1,构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，则当前的 f 即为所求的最小费用最大流，
输出 f；否则，找出 N( f )的一条最小费用有向路 P，转下步。
Step 2,沿 P 对 f 增流，得新的可行流 f，转 Step1 。
五、求总费用限定的最大流的算法
问题,对网络 (,,,,,)NV xyACw和一个预定的总费用值
0
0w ≥,求 N 中总费用不超过
0
w 的一个流，使其流值在所有这样的流中达到最大。
算法,
输入,(,,,,,)NV xyACw；
0
w 。
输出：费用
0
w≤ 的流中流值最大的流。
Step 0,取零流作为初始可行流 f。
Step 1,构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，转 Step 4；否则，找出 N( f )的一条最小费用 x-y 有向路 P，转下步。
Step 2 若 () 0wP′ >,则令
()
min{ ( ),}
()
0
wwf
cP
wP
θ
′=
′
，（ ()cP′ 表示 P 上最小弧容量）,
转 Step3；否则沿 P 对 f 增流，得新的可行流 f，转 Step1。
Step 3 若 0θ =,则停止，当前的 f 便是 N 中费用不超过
0
w 的最大流，输出 f；否则沿 P 对 f 增流值
θ,得新的可行流 f，转 Step1。
第九章习题
1,在下面的网络中，弧上第一 个数字表示流量，第二个数字表示容量。
(1) 确定所有的割；
(2) 求最小割的容量；
(3) 证明给定流是最大流。
2,若 (,)SS 和 (,)TT 都是 N 中的最小割，证明 (,)STST∪∪及 (,)STST∩∩也都是 N 的最小割。
3,对如下网络，从零流开始，分别用 Ford-Fulkson 标号算法和 Dinic 算法求出其最大流，写出或画出算法过程。（注：括号内数字表示弧的容量，括号外数字表示当前流值）。
yx
0(8)
0(7)
0(9)
0(5)
0(2)
0(9)
0(10)
0(5)
v
1
v
3
1(3)
3(4)
3(3)
0(1)
2(5)
2(2)
x
y
v
2
2(2)
