有上下界的网络流

    有上下界的网络最大流是指在网络流图中两点之间的路径上的流量Flow必须在一个范围之内。用[Bi,Ci]表示路径i,说明路径i上的流量Flow(i)大于等于Bi且小于等于Ci. 
    有上下界的网络流问题可以分为四类: 
1. 无源汇网络可行流 
2. 有源汇网络可行流 
3. 有源汇网络最大流 
4. 有源汇网络最小流

无源汇网络可行流

    无源汇网络是指在网络流图中没有明确指定源点和汇点,流在网络中是循环流动的,可行流是指网络中所有路径上的流量均满足 Flow(i) 属于[Bi, Ci],且每个点的流入量之和等于流出量之和。 
    每条边必须有一个流量下界,这非常麻烦,考虑将流量下界单独出去,成为一个新图,使得边的流量下界为0,流量上界为 Ci-Bi,变成了一个普通的网络流问题(每条边只有流量上界,即容量)。称每条边的流量下界为必须流,每条边的流量减去流量下界为自由流,由于边的流量范围的限制,有些情况下网络流图可能无法流通。比如下图中国 1-->2 的边上的流量上界为3,而2-->3的边上的流量下界为4,那么网络就无法流动。网络中存在满足边的上下界要求的网络流,称为可行流 
 
    求解可行流 
    设每个点所有流入量的流量下界之和IBi和所有流出量下界之和OBi,然后虚拟一个源点SS和一个汇点TT,使得原图中每个点都有OBi的流量流入SS,同时有IBi的流量从TT流入,这样,就将每个点的流量下界独立出来。这样,每条边的必须流就被SS和TT管理。 
    以SS,TT分别为新图的源点和汇点,寻找网络最大流,如果最大流使得从SS出发的每条路径都被填满(那么到达TT的每条路径也必然被填满),那么说明对于原图中的每个点,都满足最低流入量的流流入和最低流出量的流流出,从而存在满足原图流量下界的可行流。 
如下图: 
 
原图中边上的数字表示边的流量范围。

 
   加SS和TT之后的新图,从每个点的引出容量为最低流出量之和OBi的路径指向汇点TT,并从SS引入容量为最低流入量之和IBi的路径指向该点。 同时,每条边的最低流量变为0,容量变为Ci-Bi。 
    然后,从SS到TT寻找网络最大流。图中所示,SS-->1-->2-->TT的路径上流量为3,SS-->1-->TT路径上流量为1,SS-->2-->3-->TT路径上的流量为1,SS-->3-->TT路径上流量为3。则最大流为8,且能够使得SS到原图中每个点的边上的流量均满流。因此,原图存在可行流。

有源汇网络的可行流

    对于流量有上下界的有源汇网络,原图中存在源点S和汇点T,为了求可行流,先将其转换为无源汇网络。 
    从T-->S引入一条边,其流量上下界为[0, INF],此时原图变为了无源汇网络,然后按照无源汇网络求解可行流的方法来求解。 

有源汇网络的最大流

    要求最大流,先求可行流,通过“有源汇网络的可行流”的求解方法来判断有源汇网络存在可行流。 
    若存在可行流,记从S流出的流量sum1,然后将T-->S的边取消,再次从S到T求解网络的最大流,记从S流出的流量sum2. 那么该有源汇网络的最大流为 sum1 + sum2. 
    其中,sum1是在网络满足流量下界的条件下,从源点S流出的流量;求出sum1之后,网络中可能还有余量可以继续增广,那么再次求解从S到T的最大流,得到sum2,sum1 + sum2即为最终的最大流。

有源汇网络的最小流

    求解有源汇网络最小流分为以下几步: 
(1)对SS到TT求一次最大流,即为f1.(在有源汇的情况下,先把整个网络趋向必须边尽量满足的情况); 
(2)添加一条边T-->S,流量上限为INF,这条边即为P.(构造无源网络) 
(3)对SS到TT再次求最大流,即为f2。(判断此时的网络中存在可行流,同时求出SS-->TT最大流) 
    如果所有必须边都满流,证明存在可行解,原图的最小流为“流经边P的流量”(原图已经构造成无源汇网络,对于S同样满足 入流和==出流和,只有新添加的边流向S,而S的出流就是原图的最小流)。 
注: 最小流求法的正确性不知如何证明,待继续学习。

原文地址:https://www.cnblogs.com/gtarcoder/p/4888973.html