26.2 Ford-Fulkerson方法

本节讨论用来解决最大流问题的Ford-Fulkerson方法。之所以称其为“方法”而不是“算法”，是因为它包含了几种运行时间各不相同的具体实现。Ford-Fulkerson方法依赖于三种重要思想，它们与许多的流算法和问题有关，如残存网络、增广路径和切割。这些思想是最大流最小切割定理(定理26.6)的精髓，该定理以流网络的切割来表述最大流的值。在本节的末尾，我们将给出Ford-Fulkerson方法的一种具体实现，并分析其运行时间。

Ford-Fulkerson方法循环增加流的值。在开始的时候，对于所有的结点u，v∈V，f(u，v)=0,给出的初始流值为0。在每一次迭代中，我们将图G的流值进行增加，方法就是在一个关联的“残存网络”Gf,中寻找一条“增广路径”。一旦知道图Gf中一条增广路径的边，就可以很容易辨别出G中的一些具体的边，我们可以对这些边上的流量进行修改，从而增加流的值。虽然Ford-Fulkerson方法的每次迭代都增加流的值，但是对于图G的一条特定边来说，其流量可能增加，也可能减少;对某些边的流进行缩减可能是必要的，以便让算法可以将更多的流从源结点发送到汇点。重复对流进行这一过程，直到残存网络中不再存在增广路径为止。最大流最小切割定理将说明在算法终结时，该算法将获得一个最大流。

FORD-FULKERSON-METHOD(G,s,t)

initialize flow f to 0//将流f初始化为0
while there exists an augmenting path p in the resdiual network Gf//当在可重构网络GF中存在一个增广路径P时
	augment flow f along p//沿p增大流f
return f//返回f

为了实现和分析Ford-Fulkerson方法，需要引入几个新的概念。

残存网络

例子

残存网络

图 26-4

残存边

递增

抵消操作

引理 26.1

证明

增广路径

增广路径

残存容量

引理 26.2

推论 26.3 如果将流f增加f_p的量，则将获得G的另一个流该流的值更加接近最大值

证明

根据引理26.1和引理26.2可立即得到上述推论。

流网络的切割

Ford-Fulkerson方法的核心就是沿着增广路径重复增加路径上的流量,直到找一个最大流为止。我们怎么知道在算法终止时，确实找到了一个最大流呢?稍后将要证明的最大流最小切割定理告诉我们，一个流是最大流当且仅当其残存网络不包含任何增广路径。为了证明这个定理，首先来探讨一下流网络中的切割概念。

一个网络的最小切割是整个网络中容量最小的切割。

流的定义和切割容量的定义之间存在着不对称性，但这种不对称性是有意而为，并且很重要。对于容量来说，我们只计算从集合S发出进入集合T的边的容量，而忽略反方向边上的容量。对于流，我们考虑的则是从S到T的流量减去从T到S的反方向的流量。这种区别的原因在本节稍后就会清楚了。

净流量 容量

图 26-5

引理 26.4 对于给定流f，横跨任何切割的净流量都相同，都等于|f|，即流的值

推论 26.5 如何使用切割容量来限定一个流的值

流网络G中任意流f的值不能超过G的任意切割的容量。

推论26.5给出的一个直接结论是:一个流网络中最大流的值不能超过该网络最小切割的容量。这就是下面要来陈述和证明的非常重要的最大流最小切割定理。该定理表明一个最大流的值事实上等于一个最小切割的容量。

定理 26.6 最大流最小切割定理

证明

基本的FORD-FULKERSON算法

FORD-FULKERSON(G,s,t)

for each edge(u.v) ∈ G.E
	(u,v).f=0
while there exists a path p from s to t in the residual network Gf
	c_f(p)=min{c_f(u,v):(u,v)is in p}
    for each egde(u,v) in p
    	if (u,v)∈E
        	(u,v).f = (u,v).f + c_f(p)
        else (v,u).f = (v,u).f - c_f(p)

FORD-FULKERSON算法的分析

图 26-6 基本的 FORD-FULKERSON 算法的执行过程

图 26-7 基本的 FORD-FULKERSON 算法的执行过程

练习

26.2-4

In the example of Figure 26.6, what is the minimum cut corresponding to the maximum flow shown? Of the augmenting paths appearing in the example, which one cancels flow?

在图26-6的例子中，对应图中所示最大流的最小切割是什么?在例子中出现的增广路径里，哪一条路径抵消了先前被传输的流?

Solution

与最大流量对应的最小切割为 S={S, v1, v2, v4}和 T={v3, t}。

第（c）部分中的增强路径取消了边缘上的流（v3，v2）。

26.2-10

Show how to find a maximum flow in a network G=(V,E) by a sequence of at most∣E∣ augmenting paths. (Hint: Determine the paths after finding the maximum flow.)

说明在流网络G=(V,E)中，如何使用一个最多包含|E|条增广路径的序列来找到一个最大流。(提示:找到最大流后再确定路径。)

Solution

假设我们已经有一个最大流F。

考虑一个新的图G，在这里我们将边（u，v）的容量设为f（u，v）。

运行Ford Fulkerson，并进行修改，如果流量达到其容量，我们将移除边缘。

换句话说，如果f（u，v）=c（u，v），则剩余网络中不应出现反向边。

在我们的例子中，这仍然会产生正确的输出，因为我们永远不会超过通过边缘的实际最大流量，所以取消流量从来都不是有利的。

在Ford Fulkerson的这个修改版本中选择的增强路径正是我们想要的。

最多有∣E∣ 因为每个增强路径至少产生一条流等于其容量的边，我们将其设置为最大流中该边的实际流，并且我们的修改防止我们破坏此过程。