图的网络最大流

Published on 2016 - 06 - 26

网络最大流的求解

网络最大流的求解主要有两大类算法:增广路算法(Augmenting Path Algorithm)和预流推进算法(Preflow-Push Algorithm)。

增广路算法

根据增广路定理,为了得到最大流,可以从任何一个可行流开始,沿着增广路对网络流进行增广,直到网络中不存在增广路为止,这样的算法称为增广路算法。问题的关键在于如何有效地找到增广路,并保证算法在有限次增广后一定终止。

增广路算法的基本流程如下(如图8所示)。

  1. 取一个可行流f作为初始流(如果没有给定初始流,则取零流f={0}作为初始流)。
  2. 寻找关于f的增广路P,如果找到,则沿着这条增广路P将f改进成一个更大的流。
  3. 重复第(2)步直到f不存在增广路为止。

增广路算法的关键是寻找增广路和改进网络流。

预流推进算法

预流推进算法是从一个预流出发对活跃顶点沿着允许弧进行流量增广,每次增广称为一次推进(Push)。在推进过程中,流一定满足流量限制条件(式1),但一般不满足流量平衡条件(式2),因此只是一个伪流。此外,如果一个伪流中,从每个顶点(除源点Vs、汇点Vt外)流出的流量之和总是小于等于流入该顶点的流量之和,称这样的伪流为预流(Preflow)。因此这类算法被称为预流推进算法。

一般增广路方法——Ford-Fulkerson算法

在Ford-Fulkerson算法中,寻找增广路和改进网络流的方法为标号法(Label Method),接下来先看标号法的两个实例,再介绍标号法的运算过程和程序实现。

标号法实例

以下两个实例分别从初始流为零流和非零流出发采用标号法求网络最大流。

  • 标号法求最大流的实例1——初始流为零流

如图9(a)所示,各条弧上的流量均为0,初始可行流f为零流。

在图9(b)中,对初始流f进行第1次标号。每个顶点的标号包含以下两个分量。

  1. 第1个分量指明它的标号从哪个顶点得到,以便找出可改进量。
  2. 第2个分量是为确定可改进量α用的。

首先对源点Vs进行标号,标号为(0,+∞)。每次标号,源点的标号总是(0,+∞)。其中第1个分量为0,表示该顶点是源点;第2个分量为+∞,表示Vs可以流出任意多的流量(只要从它发出的弧可以接受)。

源点有标号以后,采用广度优先搜索(BFS)的思路从源点出发进行遍历,并对遍历到的每个顶点进行标号。假设在对某个顶点的多个未标号邻接顶点中进行标号时,按顶点序号从小到大的顺序进行标号。例如源点Vs有两个邻接顶点:V1和V2,则先对顶点V1进行标号。对顶点V1的标号为(Vs,8)。该标号的含义是:第2个分量为8,表示Vs可以流出+∞的流量,但弧<Vs,V1>的容量为8,所以,顶点Vs只能接受8;第1个分量表示流量改进量“8”来自顶点Vs。按照同样的思路对顶点V2进行标号,标号为(Vs,4)。

源点Vs的邻接顶点检查完毕后,再从顶点V1出发对它的邻接顶点进行标号:对顶点V3的标号为(V1,2),对顶点V4的标号为(V1,2)。注意,顶点V2也是V1的“邻接”(通过后向弧“邻接”)顶点,但V2已经有标号了,所以不能通过V1对V2进行标号。

源点V1的邻接顶点检查完毕后,再从顶点V2出发对它的邻接顶点进行标号,此时顶点V2的邻接顶点中,都已经有标号了。

源点V2的邻接顶点检查完毕后,再从顶点V3出发对它的邻接顶点进行标号,从而通过V3对汇点Vt进行标号,标号为(V3,2)。

一旦汇点Vt有标号,且第2个分量不为0,则表示找到一条增广路。确定这条增广路的方法是:从汇点Vt标号的第1个分量出发,采用“倒向追踪”的方法,一直找到源点Vs。

例如在图9(b)中,汇点Vt标号的第1个分量为V3,表示增广路上汇点Vt前面的顶点为V3;顶点V3标号的第1个分量为V1,表示增广路上顶点V3前面的顶点为V1;顶点V1标号的第1个分量为Vs,表示增广路上顶点V1前面的顶点为Vs;因此找到的这条增广路为:P(Vs,V1,V3,Vt),增广路中的弧用粗线标明。并且这条增广路的可改进量α就是汇点Vt标号的第2个分量,为2。沿着这条增广路,可以将流量增加2,流量变成2,改进后的流如图9(c)所示。

图9(d)对第1次调整后的网络流进行第2次标号,求得的增广路为:P(Vs,V1,V4,Vt),可改进量α=2;调整后得到的网络流如图9(e)所示,流量为4。

图9(f)对第2次调整后的网络流进行第3次标号,求得的增广路为:P(Vs,V2,V3,Vt),可改进量α=1;调整后得到的网络流如图9(g)所示,流量为5。

图9(h)对第3次调整后的网络流进行第4次标号,求得的增广路为:P(Vs,V2,V4,Vt),可改进量α=3;调整后得到的网络流如图9(i)所示,流量为8。

在图9(j)中,对第4次调整后得到的网络流进行第5次标号:通过源点Vs对顶点V1的标号为(Vs,4),源点Vs无法对顶点V2进行标号,因为弧<Vs,V2>已经饱和了;而顶点V1也无法对它的邻接顶点进行标号。此后汇点Vt无法获得标号,或者说汇点Vt的可改进量α为0。至此,标号法结束,求得的最大流流量为8。

  • 标号法求最大流的实例2——初始流为非零流

如图10(a)所示,初始可行流f为非零流,其流量为5。

摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.
摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.

摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.

摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.

摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.
摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.
摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.

摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.

摘录来自: 王桂平. “图论算法理论、实现及应用”。 iBooks.