「流」最大流（Maximum Flow）

流

一、流网络

G=（V，E）是一个有向图，其中每条边（u，v）有一个非负的容量值c（u，v），而且如果E中包含一条边（u，v），那么图中就不存在它的反向边。在流网络中有两个特殊的结点，源结点s和汇点t。

下面给出流网络的形式化定义。令G=（V，E）为一个流网络，其容量函数为c，设s我为网络的源点，t为汇点。G中的流是一个实值函数f，满足以下两条性质：

1. 容量限制（capacity contraint）：对于所有的结点u，v，要求

2. 流量守恒（flow conservation）：对于所有的非源点和汇点的结点u，要求：

下图是一个流网络的示例图，帮助大家理解，其中的“/”只是分隔符而不是运算符，“/”前代表的是流的值，后面的数值则是该条边的容量（capacity）：

流网络常见的一种应用场景是运输问题，需要将货物从s运输到t，途经几个中转站，每次运输到每个中转站的货物的数量是有限制的。在实际应用中我们可能会在某条边上双向运输，这样便违反了我们之前对流网络的定义，但是我们可以将包含反平行边的图来改造成流网络，具体的方法是引入一个是虚构的中转结点，方法如下图。

考虑另外一种特殊情形，从多个工厂发出货物最终运输到别的多个工厂，这时候我们具有了多个源点和多个汇点，这也很好解决，解决的方法就是人为添加超级源点（supersource）和超级汇点（supersink），具体方法见下图。

二、Ford-Fulkerson方法

将实际问题转化成流网络后，我们就可以来解决最大流问题了。理解这个方法需要先理解几个关于流网络的基础概念。

1. 残存网络（residual network）

假定有一个流网络G=（V，E），其源点为s，汇点为t，f为G中的一个流。对即诶点对u，v，定义残存容量（residual capacity），有：

残存网络可能包含图G中不存在的边，残存网络中的反向边允许算法将已经发送出来的流量发送回去。一个残存网络示例图如下：

图a是一个流网络，b是a对应的残存网络，注意每条边上的值，残存网络中针对每条正向边计算出该条边在存在流的情况下的剩余容量，并画出一条反向边，反向边的容量即是发出流的大小，方便将发出的流运输回发送地，并将权重为0的边省略。

残存网络是如何增大原始流网络中的流的一种指示。如果f是G的一个流，对应的有一个残存网络，残存网络中我们可以定义一个流。此时我们可以定义一个函数，我们将其称作流对f的增量（augmentation）。

2. 增广路径（augmenting paths）

给定流网络G和流f，增广路径p是残存网络中一条从源结点s到汇点t的简单路径。根据残存网络的定义，对于一条增广路径上的边（u，v），我们可以增加其流量的幅度最大为，即我们之前定义的残存容量（residual capacity）。我们将这里讨论的情形总结成一条引理：

引理设G为一个流网络，设f为图G中的一个流，设p为残存网络中的一条增广路径。定义一个函数如下：

其中是残存网络中的一个流，其值。

推论设G为一个流网络，设f为G中的一个流，设p为残存网络中的一条增广路径。设如上述引理所定义，假定将f增加的量，则函数是图G中的一个流，其值为。

3. 流网络的切割（cuts of networks）

流网络G中的一个切割（S，T）将结点集合V划分为S和T=V-S两个集合，使得、。若f是一个流，则定义横跨切割（S，T）的净流量f（S，T）如下：

切割（S，T）的容量是：

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

举例说明切割的计算方法：

横跨该切割的净流量：

该切割的容量：

引理设f为流网络G的一个流，该流网络的源结点为s，汇点为t，设（S，T）为流网络G的任意切割，则横跨切割（S，T）的净流量为。

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

定理（最大流最小切割定理） 设f为流网络G=（V，E）中的一个流，该流网络的源结点为s，汇点为t，则下面的条件是等价的：

1. f是G的一个最大流。

2. 残存网络不包含任何增广路径

3. |f|=c（S，T），其中（S，T）是流网络G的某个切割。

4. 基本的Ford-Fulkerson算法

在Ford-Fulkerrson方法的每次迭代中，寻找某条增广路径p，然后使用p来对流f进行修改（增加）。我们不断地在图中寻找增广路径，并依据来增大f的值，直到图中不含增广路径。伪代码实现如下：

Ford-Fulkerson算法的运行时间取决与寻找增广路径的方法，这也是Edmonds-Karps算法对基础Ford-Fulkerson算法做改进的理论基础。

我们在残存网络中选择的增广路径是一条从源结点s到汇点t的最短路径，其中每条边的权重为单位距离，我们称如此实现的Ford-Fulkerson算法为Edmonds-Karp算法。