网络流问题是图论中一类常见的问题。许多系统都包含了流量，例如，公路系统中有车辆流，控制系统中有信息流，供水系统中有水流，金融系统中有现金流等等。先看一个运输方案设计的例子。图6.1(a)是连接产品产地Vs和销售地Vt的交通网，每一条弧代表两点间的运输线，弧旁的数字表示这条运输线的最大通过能力。现在要求制定一个运输方案，使得从Vs运输到Vt的产品数量最多。
在上面的例子中，任何一个方案都应该满足以下三点要求：
1)实际运输量不能是负的；
2)每条弧的实际运输量不能大于该弧的容量；
3)除了Vs和Vt外，对其它顶点来说，所有流入的运输量总和应该等于所有流出的运输量总和。
好了，我们现在面临的就是一个典型的“最大流”问题。怎么解决它呢？
还是用上面的例子，看一个启发性的问题：
a，b，c三条线把图的顶点分成了两部分。注意红色的a线b线与蓝色的c线有所区别：红线分割之后，网络流只会从源点Vs所在的一侧流向目的地Vt所在的一侧，而蓝线不能保证这种性质。我们把网络流只会从源点Vs所在的一侧流向目的地Vt所在一侧的划分线叫做网络的割线。由于货物只会从割线的一侧流到另一侧，而绝对不会发生逆流，所以割线有个非常重要的性质：割线上的流量是瓶颈，整张图上的最大流量不能超过任意一个割线上的流量。事实上，整张图的流量等于割线上的最小流量。这就是著名的最大流-最小割定理。
知道了最大流的上限是最小割只能算是得到一个笼统的性质，接下来还有两个更重要的问题：最小割是多少？以及更重要的：与最小割对应的通路是哪条？
解决这些问题需要用到一个重要的概念：增广路。所谓增广路，通俗的讲就是从源点到目的地点，仍然有改进余地的一条通路。严格的定义如下：
假设已经存在一个从源点到目的地点的流量方案f，一个连接源点和目的地点的路径P（注意从源点到目的地点，P是有方向的）。对于P经过的任意相邻两点间的弧t：
1）当t与f流经它的方向相同时，如果f的流量小于t的容量，或者
2）当t与f流经它的方向相反时，如果f的流量大于0.
则P称为f的一条增广路。
（上面的定义太枯燥了，我拿人话解释一下：方向相同时，如果f的流量小于弧的容量，表示没有弧上还有潜在的运输能力可以使用；方向相反表示根本没办法这么分配，如果已经犯错了分配了那就赶紧改过来）
根据定义可以推断出来，如果一个方案f中存在增广路，那么它就不是最优的，我们需要把这条增广路给修理好。于是就有了下面增广路算法：为了得到最大流，可以从任何一个可行流开始，沿着增广路对网络流进行优化修改，直到网络中不存在增广路为止，算法的基本流程是：
(1)取一个可行流f作为初始流（如果没有给定初始流，则取零流f={ 0 }作为初始流）；
(2)寻找关于f的增广路P，如果找到，则沿着这条增广路P将f改进成一个更大的流；
(3)重复第(2)步直到f不存在增广路为止。
增广路算法的关键是如何寻找增广，目前已有几种成熟的算法。今天太晚了，我们明天介绍一下（受不了自己这么卖关子了~~）
网友评论