网络最大流问题

给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧

，对应一个数

（简记），称之为弧的容量。通常我们把这样的

D叫做网络，记为D=(V,A,C)。

（2）网络流：在弧集A上定义一个非负函数的实际流量，简记

。

是通过弧为网络流的流量。

，称是网络上的流函数，简称网络流或流，称

§4 网络最大流问题

网络最大流问题是网络的另一个基本问题。

许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。

4.1 基本概念与定理

1． 1．网络与流

定义14 （1）网络：

例1如图7-20是连结某产品产地

和销地的交通图。弧表示从到的

运输线，弧旁的数字表示这条运输线的最大通过能力流

。现要求制定一个运输方案，使从

运到

，括号内的数字表示该弧上的实际

的产品数量最多。

可行流与最大流

在运

输网络的实际问题中，我们可以看出，对于流有两个基本要求：

一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。

因此有下面所谓的可行流的定义。

定义14对于给定的网络D=（V,A,C）和给定的流条件：

（1） 容量限制条件：对每一条弧

，有

，若

满足下列

(7.9)

（2）平衡条件： 对于中间点：

流出量=流入量，即对于每一个i (i≠s,t)，有

(7.10)

对于出发带点，有

(7.11)

对于收点，有

(7.12)

则称为一个可行流，称为这个可行流的流量。 是指只有从

发出去的弧，而没有指向

的弧；收

注意，我们这里所说的出发点

点

是指只有弧指向

，而没有从它的发出去的弧。

可行流总是存在的。例如令所有弧上的流其流量

。

，它显然满足定

，就得到一个可行流，（称为零流），

如图7-20中，每条弧上括号内的数字给出的就是一个可行流义中的条件（1）和（2）。其流量

所谓网络最大流问题就是求一个流义15中的条件（1）和（2），即

max(7.13)

。 ，使得总流量

达到最大，并且满足定

网络最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较直线性规划的一般方法要简便和直观的多。

例2写出图7-20所表示的网络最大流问题的线性规划模型。

解设max

，则其线性规划模型为

3. 增广链 在网络D=(V,A,C)中，若给定一个可行流饱和弧，使称为非零流弧。

如图7-20中的弧都是非饱和弧，而弧若

是网络中联结发点

和收点

的弧称为非饱和弧。把

，我们把网络中使的弧称为零流弧，把

的弧称为

的

为零流弧。

到

S，则链上

的一条链，我定义链的方向是从

的弧被分为两：

一类是：弧的方向与链的方向一致，我们称此类和为前向弧，所有前向弧的集合记为

。

另一类是：弧的方向与链的方向一致，我们称此类弧为后向弧，所有后向弧的集合

记为

。

如图7-20中，设

是一条从

则

,

定义15设满足下列条件：

(1)在弧(2)在弧则称

是关于

(vi,vj)∈μ+上，即上，即

的一条增广链。

中的每一条弧都是非饱和弧；

是网络D=(V,A,C)上的一个可行流，是从

到

的一条链，若

到

的链，

中的每一条弧都是非零流弧。

如前面所说的链就是一条增广链。因为其中μ+上的弧均非饱和，如(vs,v2) ∈μ

+

,fs2=50，。显然这样的增广链不止一条。

4.截集与截量

定义16给定网络D=(V,A,C)，若点集V被分割成两个非空集合V1和V2，使得

V=V1+V2,V1∩V2=φ(空集)，且vs∈V1,vt∈V2，则把始点在V1,终点在V2的弧的集合称为分离vs和vt的一个截集，记为(V1,V2)。

如图9.26中，设V1=｛vs,v2,v5｝，V2=｛v3,v4,v6,vt｝则截集为

,