最大流问题

网络最大流问题

一产生背景

流量问题在实际中是一种常见的问题，在许多实际的网络系统中都存在着流

量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题,

控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。

在一定条件下,求解给定系统的最大流量,就是网络最大流问题.网络系统最大流

问题是图与网络理论中十分重要的最优化问题，它对于解决生产实际问题起着十

分重要的作用。

二基本概念与定理

设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 。

（3,3 ）

图1

最大流问题可以建立如下形式的线性规划数学模型。图1最大流问题的线性

规划数学模型为

maxvfs1fs2

fijfij0(is,t)ji0fijcij所有弧(i,j)

由线性规划理论知，满足式上式的约束条件的解{fij}称为可行解，在最大流

问题中称为可行流。

可行流满足下列三个条件：

(1)0fijc

jiijim(2)fmjf

vsvt(3v)fsjfit

条件（2）和条件（3）也称为流量守恒条件。

另外对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收

点,并将其分别与各发点、收点连起来（图*），就可以转换为只含一个发点和一

个收点的网络。

S T

图*

所以一般只研究具有一个发点和一个收点的网络

在图D中，从发点到收点的一条路线称为链，从发点到收点的方向规定为

链的方向。与链的方向相同的弧称为前向弧，前向弧集合记为u+ ，与链的方向

相反的弧称为后向弧，后向弧集合记为u-。

设f是一个可行流，如果存在一条从发点vs到收点vt到的链u满足：

（1）所有前向弧上fij＜cij

(2) 所有后向弧上fij＞0 ，则称链u为增广链.

设S,TV,ST,vsS,vtT则称

(S,T)(vi,vj)|viS,vjT

C(S,T)

为图D的一个割集；称 (vi,vj)(s,t)c(vi,vj) 为割集（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cijf ij

（b）如果弧是后向弧且有fij﹥0，则vj标号jfij

当收点已得到标号时，说明已找到增广链，依据v的标号反向追踪得到一条

增广链。当收点不能得到标号时，说明不存在增广链，计算结束

第三步调整流量

(1) 求增广链上点的vi标号的最小值，得到调整量号

jminjj

(2) 调整流量

fij(vi,vj)uf1fij(vi,vj)u

fij(vi,vj)u

得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广

链，直到收点不能标号为止。

四例题应用

例2：用标号法求网络最大流（图1），弧旁数字为（cij ，fij(0)）。

解（1）标号过程。见图2。

(v,v),(v,v)u32 （2）增广链为{vs，v1，v2，v3，vt} （注意21）。

（3）调整量θ=2调整后得图3。

（4）二次标号过程。见图3。

标号无法进行下去，最大流流量V(f*)=3+6=9，最小割集（S*，T*）, S*={vs},

T*={ v1，v2，v3，v4，vt}。

（-v1,2）

（vs 2,2） 2,2） 2,2） vt (v3,2) v2 （3,3）（5,5）

（0，+ （6,4 （6,2）

（v1,2）（-v2,2)

图2

v2 （3,3）（5,5）

（vs 2,0） 2,0） 2,2） vt

（0，+ （6,6 （6,4）

图3

例3：在下面的有向图中1是发点， 6是收点，求最大流.

1 6

图解法如下：

6(5,2)

3(1,+5) 3

2 6(4,+1)

2 6 (3,3)

图中红色的是可增广链，可见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