网络最大流问题
一产生背景
流量问题在实际中是一种常见的问题，在许多实际的网络系统中都存在着流量和最大流问题。
例如铁路运输系统中的车辆流，城市给排水系统的水流问题,控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。
在一定条件下,求解给定系统的最大流量,就是网络最大流问题.网络系统最大流问题是图与网络理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。
二基本概念与定理
设cij为弧（i，j）的容量，fij为弧（i，j）的流量。
容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合f={fij}称为网络的流。
发点到收点的总流量记为v=v(f)。
设D=(V,A)是一有向图且对任意E均有容量cij =（vi，vj），记C={cij︱（vi，vj）∈A},此外D中只有一个源vs和汇vt( 即D中与vs相关联的弧只能以vs为起点，与vt相关联的弧只能以vt为终点)，则称D=(V,A,C, vs,vt)为一网络。
引例1：图1给出了一张网络，其中：vs为源，vt为汇，弧旁的数字为该段弧的容量cij与流量fij，则显然有0≤fij ≤ cij 。
v2 （3,3) v4
（3,3）（5,5）
vt (2,2) (2,2) (2,2) vt
(6,4) (6,2)
v1 (6,6) v3
图1
最大流问题可以建立如下形式的线性规划数学模型。
图1最大流问题的线性规划数学模型为
12
max 0(,)0s s ij ij j i ij ij v f f f f i s t f c =+⎧-=≠⎪⎨⎪≤≤⎩∑∑所有弧(i,j)
由线性规划理论知，满足式上式的约束条件的解{fij}称为可行解，在最大流
问题中称为可行流。
可行流满足下列三个条件：
(1)0(2)(3)i j i j m j i m j i sj it vs vt f c
f f
v f f ≤≤===∑∑∑∑
条件（2）和条件（3）也称为流量守恒条件。
另外对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收
点,并将其分别与各发点、收点连起来（图*），就可以转换为只含一个发点和一
个收点的网络。
S T
S*
T*
图*
所以一般只研究具有一个发点和一个收点的网络
在图D 中，从发点到收点的一条路线称为链，从发点到收点的方向规定为
链的方向。
与链的方向相同的弧称为前向弧，前向弧集合记为u+ ，与链的方向
相反的弧称为后向弧，后向弧集合记为u-。
设f 是一个可行流，如果存在一条从发点vs 到收点vt 到的链u 满足：
（1）所有前向弧上fij ＜cij
(2) 所有后向弧上fij ＞0 ，则称链u 为增广链.
设,,,,s t S T V S T v S v T ∈⋂=∅∈∈则称
{}
(,)(,)|,i j i j S T v v v S v T =∈∈
为图D 的一个割集；称 (,)(,)(,)(,)i j i j v v s t C S T c v v ∈=∑ 为割集（S ，T ）的容量。
显然对任意可行流f 及任意割集（S ，T ）总有V(f)=C(S,T)。
故有某个可行
流f*及某一割集（S*，T*）使得V(f*)= C （S*，T*），则f*为D 的最大流，（S*，
T*）为最小容量割集。
定理1 图D 上的可行流f*是最大流的充要条件是D 上不存在关于f*的增
广链。
三 求解网络最大流的方法（标号法）
标号法是一种图上迭代计算方法，该算法首先给出一个初始可行流，通过标
号找出一条增广链，然后调整增广链上的流量，得到更大的流量。
再用标号找出
一条新的增广链，再调整直到标号过程不能进行下去为止，这时的可行流就是最
大流。
标号法步骤如下：
第一步 找出一个初始可行流fij(0),例如所有弧的流量fij(0) =0.
第二步 对点进行标号找出一条增广链。
（1） 起点标号（∞）
（2） 选一个点vi 已标号且另一端未标号的弧沿着某条链向收点检查
（a ）如果弧是前向弧且有fij ＜cij ，则vj 标号
j i j i j
c f θ=- （b ）如果弧是后向弧且有fij ﹥0，则vj 标号j ij f θ=
当收点已得到标号时，说明已找到增广链，依据v 的标号反向追踪得到一条
增广链。
当收点不能得到标号时，说明不存在增广链，计算结束
第三步 调整流量
(1) 求增广链上点的vi 标号的最小值，得到调整量号
min j j j θθ=
(2) 调整流量
1(,)(,)(,)ij i j ij i j ij i j f v v u f f v v u f v v u θθ+-
⎧+∈⎪⎪=-∈⎨⎪∉⎪⎩
得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广
链，直到收点不能标号为止。
四 例题应用
例2：用标号法求网络最大流（图1），弧旁数字为（cij ，fij(0)）。
解 （1） 标号过程。
见图2。
（2） 增广链为{vs ，v1，v2，v3，vt} （注意2132(,),(,)v v v v u -∈）。
（3）调整量θ=2调整后得图3。
（4） 二次标号过程。
见图3。
标号无法进行下去，最大流流量V(f*)=3+6=9，最小割集（S*，T*）, S*={vs},
T*={ v1，v2，v3，v4，vt}。
（-v1,2）
v2 （3,3） v4 （5,5）
（3,3）
vs （2,2） （2,2） （2,2） vt (v3,2) （0，+∞）
（6,4） （6,2）
v1 （6,6） v3
（v1,2） （-v2,2)
图2
v2 （3,3） v4
（5,5）
（3,3）
vs （2,0） （2,0） （2,2） vt
（0，+∞）
（6,6） （6,4）
v1 （6,6） v3
图3
例3：在下面的有向图中1是发点，6是收点，求最大流.
2 1 4
4 2
1 2 4 2 6
5 6
3 3 5
图解法如下：
2(1,+4) 1 4(2,+1)
4 2
1(0,+inf) 2 4 2 6 (5,4)
5 6
3(5,+5) 3 5(2,+4)
2(5,-3) 1 4(5,+2)
(4,4) 2
1(0,inf) 2 (4,4) 2 6(5,2)
5 (6,4)
3(1,+5) 3 5(3,+3)
2(5,-1) 1 4(5,+1)
(4,4) 2
1(0,inf) 2 (4,4) 2 6(4,+1)
(5,2) (6,6)
3(1,+3) (3,2) 5(3,1)
2 1 4
(4,4) (2,1)
1(0,inf) 2 (4,4) (2,1) 6
(5,3) (6,6)
3(1,2) (3,3) 5
图中红色的是可增广链，可见S={1,3}, S’={2,4,5,6}, 蓝色的三条边(1,2), (3,5)，(2,3)组成的集合是最小割，割集容量为(1,2)和(3,5)两条边的容量之和7，也就是最大流的流量.
参考文献
[1] 杨民助．运筹学[M]．西安：西安交通大学出版社，2000，201-204
[2] 宁宣熙．运筹学实用教程[M]．第二版．北京：科学出版社，2007，147-152
[3] 黄桐城．运筹学基础教程[M]．第一版．上海：上海人民出版社，2004，124-128。
