网络流问题是图论中一类常见的问题。许多系统都包含了流量,例如,公路系统中有车辆流,控制系统中有信息流,供水系统中有水流,金融系统中有现金流等等。先看一个运输方案设计的例子。图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不存在增广路为止。
增广路算法的关键是如何寻找增广,目前已有几种成熟的算法。今天太晚了,我们明天介绍一下(受不了自己这么卖关子了~~)