网路的最大流和最小截

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6.4 网路的最大流和最小截,6.4.1,网路的最大流的概念,网路流一般在有向图上讨论,定义网路上支路的,容量,为其最大通过能力，记为,c,ij,，支路上的实际,流量,记为,f,ij,图中规定一个发点,s,，一个收点,t,节点没有容量限制，流在节点不会存储,容量限制条件,：0,f,ij,c,ij,平衡条件,：,满足上述条件的网路流称为,可行流,，总存在,最大可行流,当支路上,f,ij,=,c,ij,，,称为,饱和弧,最大流问题也是一个线性规划问题,v,i,A,(,v,i,),B,(,v,i,),1,6.4.2,截集与截集容量,定义,：把网路分割为两个成分的弧的最小集合，其中一 个成分包含,s,点，另一个包含,t,点 。,一般包含,s,点的成分中的节点集合用,V,表示，包含,t,点的成分中的节点集合用,V,表示,截集容量,是指截集中正向弧的容量之和,福特-富克森定理,：网路的最大流等于最小截集容量,2,6.4.3,确定网路最大流的标号法,从任一个初始可行流出发，如 0 流,基本算法：找一条从,s,到,t,点的,增广链,(augmenting path),若在当前可行流下找不到增广链，则已得到最大流,增广链中与,s,到,t,方向一致的弧称为,前向弧,，反之,后向弧,增广过程：前向弧,f,ij,=,f,ij,+,q,后向弧,f,ij,=,f,ij,q,增广后仍是可行流,3,最大流最小截的标号法步骤,第一步：标号过程，找一条增广链,1、,给源点,s,标号,s,+,q,(,s,)=,，表示从,s,点有无限流出潜力,2、,找出与已标号节点,i,相邻的所有未标号节点,j,，若,(1) (,i,j,),是前向弧且饱和，则节点,j,不标号；,(2) (,i,j,),是前向弧且未饱和，则节点,j,标号为,i,+,q,(,j,),，表示从节点,i,正向,流出，可增广,q,(,j,),=min,q,(,i,),c,ij,f,ij, ；,(3) (,j,i,),是后向弧，若,f,ji,=0，则节点,j,不标号；,(4) (,j,i,),是后向弧，若,f,ji,0，则节点,j,标号为,i,q,(,j,),，表示从节点,j,流向,i,，,可增广,q,(,j,),=min,q,(,i,),f,ji, ；,3、,重复步骤 2，可能出现两种情况：,(1) 节点,t,尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流,v,(,f,) 就是最大流；所有获标号的节点在,V,中，未获标号节点在,V,中，,V,与,V,间的弧即为最小截集；算法结束,(2)节点,t,获得标号，找到一条增广链，由节点,t,标号回溯可找出该增广链；到第二步,4,最大流最小截的标号法步骤,第二步：增广过程,1、对,增广链中的前向弧，令,f,=,f,+,q,(,t,)，,q,(,t,) 为节点,t,的标记值,2、,对,增广链中的后向弧，令,f,=,f,q,(,t,),3、非增广链上的所有支路流量保持不变,第三步：抹除图上所有标号，回到第一步,以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷,一次只找一条增广链，增广一次换一张图,最后一次用广探法，以便找出最小截集,5,最大流最小截集的标号法举例,(,s,+,),(,s,+,6),(2,6),(3,+,1),(4,+,1),(,s,+,),(,s,+,5),(2,+,2),(5,2),(4,+,2),6,最大流最小截集的标号法举例,(,s,+,),(,s,+,3),(2,3),最小截集,7,最大流标号法的复杂度讨论,找一条增广链的计算量是容易估计的，不会超过,O,(,n,2,),但是最多迭代多少次(即增广的次数)就很难估计，在最坏情况下，与边的容量有关；如上图：先增广 s, u v t , 然后增广 s v u t，每次只能增广 1 个单位，故要增广4000次才能结束,克服这种缺点的经验方法：,尽量先用段数少的增广链,尽量不重复前面出现过的增广链,8,6.4.4,多端网路问题,9,最小费用最大流,双权网路,：每条弧不但有容量，还有单位流量的通过费用,两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法,基于最小费用路径算法,：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧,基于可行弧集的最大流算法,：从 0 费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界,P,，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主-对偶规划的解法。使用这种方法的还有运输问题、匹配问题,10,以最短路为基础汇总网路上的流,在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路,根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设,a,25,=10 是节点2 和 5 之间的电路需求，节点2 和 5 之间的最短传输路径为 2,1,3,5，则加载过程为:,T,21,=,T,21,+10,T,13,=,T,13,+10,T,35,=,T,35,+10；,T,ij,是传输链路,i,j,上加载的电路数；当所有点间电路都加载完则算法结束,11,