寻求网络中最大流的方法及其应用

1.网络与流

定义6　给定一个有向图D=（V，A），在V中指定了一点称为发点（记为vs），而另一点称为收点（记为vt），其余的点称为中间点。对于每一条弧（vi，vj）∈A，对应着一个 c（vi，vj）≥0（或简写为cij），称为弧的容量。通常我们把这样的D 叫做一个网络，记作D=（V，A，C）。

所谓网络上的流，是指定义在弧集合A 上的一个函数f={ f（vi，vj）}，并称 f（vi，vj）为弧（vi，vj）上的流量（有时也简记作 fij）。

例如，图6-23 就是一个网络，指定 v1是发点，v6是收点，其他的点是中间点。弧旁的数字为cij。图6-24 所示的运输方案，可以看作这个网络上的一个流，每条弧上的运输量就是该弧上的流量，即 f12=5，f24=2，f13=3，f34=1等。

2.可行流与最大流

从运输网络的实际问题可以看出，对于流有两个明显的要求：一个是每条弧上的流量不能超过该弧的最大通过能力（即弧的容量）；另一个是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为这一点的流量；由于中间点只起转运作用，所以中间点的流量必为零。易见，发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。因此有：

定义7　满足下述条件的流f 称为可行流：

（1）容量限制条件：对每一条弧（vi，vj）∈A，有：0≤fij≤cij；

（2）平衡条件：对于中间点，流出量等于流入量，即对每个i，i≠s，t，有

对于发点 vs，记

对于收点 vt，记

式中 v（f）称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。

可行流总是存在的。比如，令所有弧的流量fij=0，就得到一个可行流（称为零流）。其流量 v（f）=0。

最大流问题就是求一个流{ fij}使其流量 v（f）达到最大，并且满足：

最大流问题是一个特殊的线性规划问题，即求一组{ fij}，在满足条件（1）和（2）下使v（f）达到极大。以后将会看到，利用图的特点来解决这类问题较之线性规划的一般方法更方便、更直观。

3.增广链

若给一个可行流f=（fij），我们把网络中使 fij=cij的弧称为饱和弧，使 fij＜ cij的弧称为非饱和弧，使fij=0的弧称为零流弧，使fij＞0的弧称为非零流弧。

在图6-24中，（v5，v4）是饱和弧，其他的弧为非饱和弧，所有弧都是非零流弧。

若μ 是网络中连结发点 vs和收点 vt的一条链，我们定义链的方向是从 vs到 vt，则链上的弧被分为两类：一类是弧的方向与链的方向一致，叫做前向弧，前向弧的全体记为μ+；另一类是弧的方向与链的方向相反，称为后向弧，后向弧的全体记为μ-。

图6-23中，在链μ=（v1，v2，v3，v4，v5，v6）上，

(www.xing528.com)

定义8　设f 是一个可行流，μ 是从 vs到 vt的一条链，若μ 满足下列条件，称之为（关于可行流f的）增广链：

（1）在弧（vi，vj）∈μ+上，0≤fij＜cij，即μ+中每一条弧都是非饱和弧。

（2）在弧（vi，vj）∈μ-上，0＜fij≤cij，即μ-中每一条弧都是非零流弧。

图6-24中，链μ=（v1，v2，v3，v4，v5，v6）是一条增广链，因为μ+和μ-中的弧满足增广链的条件。比如：（v1，v2）∈μ+，f12=5＜c12=10；（v5，v4）∈μ-，f54=3＞0。

4.截集与截量

设 S，T ⊂ V，S ∩T=∅，我们把始点在S中，终点在T中的所有弧构成的集合，记为（S，T）。

定义9　给定一网络D=（V，A，C），若点集V 被剖分为两个非空集合使vs∈V1，则把弧集称为（分离 vs和 vt的）截集。

显然，若把某一截集的弧从网络中丢去，则从 vs到 vt便不存在路。所以，直观上说，截集是从 vs到 vt的必经之路。

定义10　给一截集把截集中所有弧的容量之和称为这个截集的容量（简称为截量），记为即

不难证明，任何一个可行流的流量 v（f）都不会超过任一截集的容量。即

显然，若对于一个可行流f*，网络中有一个截集使则f*必是最大流，而必定是D的所有截集中容量最小的一个，即最小截集。

定理8　可行流f*是最大流，当且仅当不存在关于f*的增广链。

证明　若f*是最大流，设D中存在关于f*的增广链μ，令

由增广链的定义可知，θ＞0，令

不难验证，是一个可行流，且 v（f**）=v（f*）+θ＞v（f*）。这与f*是最大流的假设矛盾。

现在设D中不存在关于f*的增广链，证明f*是最大流。我们利用下面的方法来定义

于是有如下重要结论：

最大流量最小截量定理：任一个网络D中，从 vs到 vt的最大流的流量等于分离 vs，vt的最小截集的容量。

定理8 为我们提供了一个寻求网络中最大流的方法。若给定一个可行流f，只要判断D中有无关于f的增广链即可。如果有增广链，则可以按定理8 前半部分证明中的方法，改进f，得到一个流量增大的新的可行流；如果没有增广链，则得到最大流。而利用定理8 后半部分证明中定义的方法，可以根据 vt是否属于来判断D中有无关于f的增广链。

实际计算时，用给顶点标号的方法来定义。在标号过程中，有标号的顶点表示是中的点，没有标号的点表示不是中的点。一旦 vt有了标号，就表明找到了一条增广链；如果标号过程进行不下去，而 vt尚未标号，则说明不存在增广链，于是得到最大流，而且同时也得到一个最小截集。