资源描述：
《最大网络流-最小费用流模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、最大网络流1基本概念和术语（1）网络G是一个简单有向图，G=(V,E)，V={1，2，…，n}。在V中指定一个顶点s，称为源,另一个顶点t，称为汇。有向图G的每一条边(v,w)∈E，对应有一个值cap(v,w)≥0，称为边的容量。这样的有向图G称作一个网络。（2）网络流网络上的流是定义在网络的边集合E上的一个非负函数flow={flow(v,w)}，并称flow(v,w)为边(v,w)上的流量。1（3）可行流满足下述条件的流flow称为可行流：(3.1)容量约束：对每一条边(v,w)∈E，0≤flow(v,w)≤cap(v,w)。(3.2)平衡约束：对于中间顶点：流出量=流入量。即对每个v∈V
2、(v≠s,t)有：顶点v的流出量－顶点v的流入量=0，即对于源s：s的流出量－s的流入量=源的净输出量f，即对于汇t：t的流入量－t的流出量的=汇的净输入量f，即式中f称为这个可行流的流量，即源的净输出量(或汇的净输入量)。可行流总是存在的。例如，让所有边的流量flow(v,w)=0，就得到一个其流量f=0的可行流(称为0流)。2（4）边流对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边；flow(v,w)0的边称为非零流边。当边(v,w)既不是一条
3、零流边也不是一条饱和边时，称为弱流边。（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，其费用定义为：3（7）残流网络对于给定的一个流网络G及其上的一个流flow，网络G关于流flow的残流网络G*与G有相同的顶点集V，而网络G中的每一条边对应于G*中的1条边或2条边。设(v,w)
4、是G的一条边。当flow(v,w)>0时，（w,v）是G*中的一条边，该边的容量为cap*(w,v)=flow(v,w)；当flow(v,w)5、和(w,v)与之对应，这2条边的容量分别为cap(v,w)-flow(v,w)和flow(v,w)。残流网络是设计与网络流有关算法的重要工具。4增广路算法1算法基本思想设P是网络G中联结源s和汇t的一条路。定义路的方向是从s到t。将路P上的边分成2类：一类边的方向与路的方向一致，称为向前边。向前边的全体记为P+。另一类边的方向与路的方向相反，称为向后边。向后边的全体记为P-。设flow是一个可行流，P是从s到t的一条路，若P满足下列条件：（1）在P的所有向前边(v,w)上，flow(v,w)6、)>0，即P-中的每一条边都是非零流边。则称P为关于可行流flow的一条可增广路。可增广路是残流网络中一条容量大于0的路。将具有上述特征的路P称为可增广路是因为可以通过修正路P上所有边流量flow(v,w)将当前可行流改进成一个流值更大的可行流。5增流的具体做法是：（1）不属于可增广路P的边(v,w)上的流量保持不变；（2）可增广路P上的所有边(v,w)上的流量按下述规则变化：在向前边(v,w)上，flow(v,w)+d；在向后边(v,w)上，flow(v,w)-d。按下面的公式修改当前的流。其中d称为可增广量，可按下述原则确定：d取得尽量大，又要使变化后的流仍为可行流。按照这个原则，d既不能
7、超过每条向前边(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的一个最大流。62算法描述最大流的增广路算法如下。该
