最大网络流最小费用流模型知识课件.ppt

最大网络流（3）可行流
满足下述条件的流flow称为可行流：
(3.1)容量约束：对每一条边(v,w)∈E，0≤flow(v,w)≤cap(v,w)。
(3.2)平衡约束：
对于中间顶点：流出量=流入量。
即对每个v∈V(v≠s,t)有：顶点v的流出量－顶点v的流入量=0，即

对于源s：s的流出量－s的流入量=源的净输出量f，即

对于汇t：t的流入量－t的流出量的=汇的净输入量f，即

式中f称为这个可行流的流量，即源的净输出量(或汇的净输入量)。
可行流总是存在的。
例如，让所有边的流量flow(v,w)=0，就得到一个其流量f=0的可行流(称为0流)。（4）边流
对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边；flow(v,w)<cap(v,w)的边称为非饱和边；flow(v,w)=0的边称为零流边；flow(v,w)>0的边称为非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时，称为弱流边。
（5）最大流
最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足：
0≤flow(v,w)≤cap(v,w)，(v,w)∈E；且

（6）流的费用
在实际应用中，与网络流有关的问题，不仅涉及流量，而且还有费用的因素。此时网络的每一条边(v,w)除了给定容量cap(v,w)外，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：（7）残流网络
对于给定的一个流网络G及其上的一个流flow，网络G关于流flow的残流网络G*与G有相同的顶点集V，而网络G中的每一条边对应于G*中的1条边或2条边。
设(v,w)是G的一条边。
当flow(v,w)>0时，（w,v）是G*中的一条边，该边的容量为cap*(w,v)=flow(v,w)；
当flow(v,w)<cap(v,w)时，(v,w)是G*中的一条边，该边的容量为
cap*(v,w)=cap(v,w)-flow(v,w)。
按照残流网络的定义，当原网络G中的边(v,w)是一条零流边时，残流网络G*中有唯一的一条边(v,w)与之对应，且该边的容量为cap(v,w)。
当原网络G中的边(v,w)是一条饱和边时，残流网络G*中有唯一的一条边(w,v)与之对应，且该边的容量为cap(v,w)。
当原网络G中的边(v,w)是一条弱流边时，残流网络G*中有2条边(v,w)和(w,v)与之对应，这2条边的容量分别为cap(v,w)-flow(v,w)和flow(v,w)。
残流网络是设计与网络流有关算法的重要工具。增流的具体做法是：
（1）不属于可增广路P的边(v,w)上的流量保持不变；
（2）可增广路P上的所有边(v,w)上的流量按下述规则变化：
在向前边(v,w)上，flow(v,w)+d；
在向后边(v,w)上，flow(v,w)-d。
按下面的公式修改当前的流。

其中d称为可增广量，可按下述原则确定：d取得尽量大，又要使变化后的流仍为可行流。
按照这个原则，d既不能超过每条向前边(v,w)的cap(v,w)-flow(v,w)，也不能超过每条向后边(v,w)的flow(v,w)。
因此d应该等于向前边上的cap(v,w)-flow(v,w)与向后边上的flow(v,w)的最小值。也就是残流网络中P的最大容量。
增广路定理：设flow是网络G的一个可行流，如果不存在从s到t关于flow的可增广路P，则flow是G的一个最大流。2算法描述
最大流的增广路算法如下。该算法也常称作FordFulkerson算法。3算法的计算复杂性
增广路算法的效率由下面2个因素所确定。
（1）整个算法找增广路的次数；
（2）每次找增广路所需的时间。
给定的网络中有n个顶点和m条边，且每条边的容量不超过M。
可以证明，在一般情况下，增广路算法中找增广路的次数不超过nM次。
最短增广路算法在最坏情况下找增广路的次数不超过nm/2次。
找1次增广路最多需要O(m)计算时间。
因此，在最坏情况下最短增广路算法所需的计算时间为O(nm2)。
当给定的网络是稀疏网络，即m=O(n)时，最短增广路算法所需的计算时间为O(n3)。
最大容量增广路算法在最坏情况下找增广路的次数不超过2mlogM次。
由于使用堆来存储优先队列，找1次增广路最多需要O(nlogn)计算时间。
因此，在最坏情况下最大容量增广路算法所需的计算时间为
当给定的网络是稀疏网络时，最大容量增广路算法所需的计算时间为预流推进算法无论用哪种增广路算法，都会找到10条增广路，每条路长为10，容量为1。
共需要10次增广，每次增广需要对10条边进行操作，每条边增广1个单位流量。
10条增广路中的前9个顶点（前8条边）是完全一样的。