‍第四节网络最大流问题‍

许多系统包含了流量问题。例如，公路系统中有车辆流，控制系统中有信息流，供水系统中有水流，金融系统中有现金流等。

图5-15是联结某产品产地和销地的交通网，每一弧(，)代表从到的运输线，产品经这条弧由输送到，弧旁的数字表示这条运输线的最大通过能力。产品经过交通网从输送到。现在要求制定一个运输方案使从运到的产品数量最多。

图5-16给出了一个运输方案，每条弧旁的数字表示在这个方案中，每条运输线上的运输数量。这个方案使8个单位的产品从运到，在这个交通网上输送量是否还可以增多，或者说这个运输网络中，从到的最大输送量是多少呢?本节就是要研究类似这样的问题。

图5-15

图5-16

5.4.1基本概念与基本定理

（1）网络与流

定义：给一个有向图，在V中指定了一点称为发点(记为)，而另一点称为收点(记为)，其余的点叫中间点。对于每一个弧(，)∈A，对应有一个c(，)≥0(或简写为)，称为弧的容量。通常我们就把这样的D叫作一个网络。记作

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

例如图5-14就是一个网络，指定是发点，是收点，其他的点是中间点。弧旁的数字为。

图5-15所示的运输方案，就可看作是这个网络上的一个流，每个弧上的运输量就是该弧上的流量，即=5，=2，=3，=1等。

（2）可行流与最大流

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

定义5-4：满足下述条件的流称为可行流：

①容量限制条件：对每一弧(，)∈A

0≤≤

②平衡条件：

对于中间点流出量等于流入量，即对每个(≠s，)有：

对于发点，有：

对于收点，有：

式中称为这个可行流的流量，即发点的净输出量(或收点的净输入量)。

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

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

0≤≤   (，)∈A                  ①

          ②

最大流问题是一个特殊的线性规划问题。即求一组{}，在满足条件①和②下使达到极大。将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。

（3）增广链

若给一个可行流={}，我们把网络中使=的弧称为饱和弧，使<的弧称为非饱和弧。使=0的弧称为零流弧，使>0的弧称为非零流弧。

在图5-15中，(，)是饱和弧，其他的弧为非饱和弧。所有弧都是非零流弧。

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

图5-15中，在链=(，，，，，)上

={(，)，(，)，(，)，(，)}

={(，)}

定义：设是一个可行流，是从到的一条链，若满足下列条件，称之为(关于可行流的)增广链。

在弧(，)∈上，0≤<，即中每一弧是非饱和弧。

在弧(，)∈上，0<≤，即中每一弧是非零流弧。

图10-24中，链=(，，，，，)是一条增广链。因为和中的弧满足增广链的条件。比如：

(，)∈，=5<=10

(，)∈，=3>0

（4）截集与截量

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

定义：给网络，若点集V被剖分为两个非空集合和，使∈，∈，则把弧集(，)称为是(分离和的)截集。

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

定义5-5：给一截集(，)，把截集(，)中所有弧的容量之和称为这个截集的容量(简称为截量)，记为c(，)，即

c(，)=Σ(，)∈(，)

不难证明，任何一个可行流的流量都不会超过任一截集的容量。即≤c(，)

显然，若对于一个可行流，网络中有一个截集(，)，使v()=c(，)，则必是最大流，而(，)必定是D的所有截集中，容量最小的一个，即最小截集。一般地有如下结论：

(1)可行流是最大流，当且仅当不存在关于的增广链。

(2)任一个网络D中，从到的最大流的流量等于分离，的最小截集的容量。

(1)为我们提供了寻求网络中最大流的一个方法。若给了一个可行流，只要判断D中有无关于的增广链。如果有增广链，改进，得到一个流量增大的新的可行流。如果没有增广链，则得到最大流。

5.4.2寻求最大流的标号法

从一个可行流出发(若网络中没有给定，则可以设是零流)，经过标号过程与调整过程。

（1）标号过程

在这个过程中，网络中的点或者是标号点(又分为已检查和未检查两种)，或者是未标号点。每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。

标号过程开始，总先给标上(0，+)，这时是标号而未检查的点，其余都是未标号点。一般地，取一个标号而未检查的点，对一切未标号点：

①若在弧(，)上，<，则给标号(，())。这里()=[()，-]。这时点成为标号而未检查的点。

②若在弧(，)上，>0，则给标号(-，())，这里()=[()，]。这时点成为标号而未检查的点。

于是成为标号而已检查过的点。重复上述步骤，一旦被标上号，表明得到一条从到的增广链，转入调整过程。

若所有标号都是已检查过的，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。

（2）调整过程

首先按及其他点的第一个标号，利用“反向追踪”的办法，找出增广链。例如设的第一个标号为(或-)，则弧(，)(或相应地(，))是上的弧。接下来检查的第一个标号，若为(或-)，则找出(，)(或相应地(，))。再检查的第一个标号，依此下去，直到为止。这时被找出的弧就构成了增广链。令调整量是()，即的第二个标号。令：

去掉所有的标号，对新的可行流，重新进入标号过程。

【例5.7】用标号法求图5-17所示网络的最大流，弧旁的数是(，)。

解：

(1)标号过程

1首先给标上(0，+)

图5-17

②检查，在弧(，)上，，不满足标号条件。弧(，)上，，，<，则的标号为(，())，其中

()=[()，(-)]=[+，5-1]=4

③检查，在弧(，)上，=2，=2，不满足标号条件。

在弧(，)上，=1>0，则给记下标号为(-，())，这里

()=[()，]=[4，1]=1

④检查，在弧(，)上，=3，=4，<，则给标号(，())，这里

()=[()，(-)]=[1，1]=1

在弧(，)上，=1>0，给标号：(-，())，这里

()=[()，]=[1，1]=1

⑤在，中任选一个进行检查。例如

在弧(，)上，=1，=2，<，给标号为(，())，这里

()=[()，(-)]=[1，1]=1

因有了标号，故转入调整过程。

(2)调整过程

按点的第一个标号找到一条增广链，如图5-18中双箭头线表示。

图5-18

易见={(，)，(，)}

={(，)，(，)}

按=1在上调整。

上：+=1+1=2

+=1+1=2

上：-=1-1=0

-=1-1=0

其余的不变。

调整后得如图5-19所示的可行流，对这个可行流进入标号过程，寻找增广链。

图5-19

开始给标以(0，+)，于是检查，给标以(，3)，检查，弧(，)上，=，弧(，)上，=0，均不符号条件，标号过程无法继续下去，算法结束。

这时的可行流(图5-18)即为所求最大流。最大流量为：

=+=+=5

与此同时可找到最小截集(，)，其中为标号点集合，为未标号点集合。弧集合(，)即为最小截集。

上例中，={，}，={，，，}，于是(，)={(，)，(，)}是最小截集，它的容量也是5。

由上述可见，用标号法找增广链以求最大流的结果，同时得到一个最小截集。最小截集容量的大小影响总的输送量的提高。因此，为提高总的输送量，必须首先考虑改善最小截集中各弧的输送状况，提高它们的通过能力。另一方面，一旦最小截集中弧的通过能力被降低，就会使总的输送量减少。