最大流是什么？

一、流网络

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’。此时我们可以定义一个函数 f↑f’，我们将其称作流f’对f的增量（augmentation）。

2. 增广路径（augmenting paths）

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

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

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

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