网络最大流问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,问题,已知网络,D,=,（,V,，,A,，,C,），其中,V,为顶点,集，,A,为弧集，,C,=,c,ij,为容量集，,c,ij,为弧（,v,i,，,v,j,）,上的容量。现,D,上要通过一个流,f,=,f,ij,，其中,f,ij,为弧,（,v,i,，,v,j,）上的流量。问应如何安排流量,f,ij,可使,D,上,通过的总流量,v,最大？,例如：,v,4,v,2,v,s,v,1,v,t,v,3,2,1,3,1,4,5,3,2,5,第四节 网络最大流问题,1,7.4.1,网络的最大流的概念,网络流一般在有向图上讨论,定义网络上弧的,容量,为其最大通过能力，记为,c,ij,，弧上的实际,流量,记为,f,ij,图中规定一个发点,s,，一个收点,t,节点没有容量限制，流在节点不会存储,容量限制条件,：,0,f,ij,c,ij,平衡条件,：,满足上述条件的网络流称为,可行流,，总存在,最大可行流,v,i,A,(,v,i,),B,(,v,i,),2,如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。,v,4,v,2,v,s,v,1,v,t,v,3,（,2,，,2,）,（,1,，,1,）,（,3,，,3,）,（,1,，,1,）,（,4,，,3,）,（,5,，,13,，,0,）,（,2,，,1,）,（,5,，,3,）,（,2,）可增值链（增广链）,v,4,v,2,v,s,v,1,v,t,v,3,（,2,，,2,）,（,1,，,1,）,（,3,，,3,）,（,1,，,1,）,（,4,，,3,）,（,5,，,1,）,（,3,，,0,）,（,2,，,1,）,（,5,，,3,）,3,（,3,）截集与截量,截量：截集上所有弧的容量和，记 。,例,4,对于下图，若,V,1,=,v,s,，,v,1,，请指出相应的截集与截量。,v,4,v,2,v,s,v,1,v,t,v,3,（,2,，,2,）,（,1,，,1,）,（,3,，,3,）,（,1,，,1,）,（,4,，,3,）,（,5,，,1,）,（,3,，,0,）,（,2,，,1,）,（,5,，,3,）,解：,4,（,4,）流量与截量的关系,最大流最小割定理：,v,4,v,2,v,s,v,1,v,t,v,3,（,2,，,2,）,（,1,，,1,）,（,3,，,3,）,（,1,，,1,）,（,4,，,3,）,（,5,，,1,）,（,3,，,0,）,（,2,，,1,）,（,5,，,3,）,（,5,）最大流的判别条件,5,最大流最小截的标号法步骤,第一步：标号过程，找一条增广链,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,；,7.4.2,确定网络最大流的标号法,6,3,、重复步骤,2,，可能出现两种情况：,(1),节点,t,尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流,v,(,f,),就是最大流；所有获标号的节点在,V,中，未获标号节点在,V,中，,V,与,V,间的弧即为最小截集；算法结束,(2),节点,t,获得标号，找到一条增广链，由节点,t,标号回溯可找出该增广链；到第二步,第二步：增广过程,1,、对,增广链中的前向弧，令,f,=,f,+,q,(,t,),，,q,(,t,),为节点,t,的标记值,2、,对,增广链中的后向弧，令,f,=,f,q,(,t,),3,、非增广链上的所有支路流量保持不变,第三步：抹除图上所有标号，回到第一步,7,例,1,用标号法求下面网络的最大流。,解：第一次标号及所得可增值链如图，调量,=1,，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量,v,=5,，同时得最小截,v,4,v,2,v,s,v,1,v,t,v,3,（,2,，,2,）,（,1,，,1,）,（,3,，,3,）,（,1,，,1,）,（,4,，,3,）,（,5,，,1,）,（,3,，,0,）,（,2,，,1,）,（,5,，,3,）,2,0,2,0,8,例,2,最大流最小截集的标号法举例,(,s,+,),(,s,+,6),(2,6),(3,+,1),(4,+,1),(,s,+,),(,s,+,5),(2,+,2),(5,2),(4,+,2),12,3,4,5,6,t,s,s,1,2,3,4,5,6,t,9,最大流最小截集的标号法举例,(,s,+,),(,s,+,3),(2,3),最小截集,(4,+,2),t,t,s,s,1,1,2,2,3,3,4,4,5,5,6,6,10,例,.3,：求下图中的最大流：,（,3,）,x,y,v,2,v,4,4,4,7,x,y,v,4,v,3,8,2,3,x,v,2,v,3,v,4,v,5,y,8.0,4.0,2.0,2.0,4.0,6.0,7.0,4.0,1.0,9.0,4.4,解：增广链：,（,1,）,4.4,7.4,（,2,）,8.2,2.2,7.6,6,x,y,2,9,v,3,v,5,8.42.2,9.2,V,f;,最大流,8,11,练习 用标号法求下面网络从,s,到,t,的最大流量,并找出该网络的最小割,.,12,13,6.5,中国邮递员问题,一个邮递员从邮局出发分送邮件，要走完他负责的所有街道，最后再返回邮局。应如何选择路线，才能使所走的路线最短，这就是中国邮递员问题。,1962,年，管梅谷先生提出中国邮递员问题,。,中国邮递员问题用图论的观点来看就是：在一个赋权连通图中，找一个过每边至少一次的闭链（圈），并且使闭链的权最小。它的算法与一笔画问题有关。,14,一、一笔画问题,有关一笔画问题有如下结论：,1.,一个连通图中的顶点都是偶点，没有奇点，则该图可以一笔画出。,2.,一个连通图中的顶点恰有两个奇点，其余都是偶点，则从任一奇点出发，则可以一笔画出该图。,3.,一个连通图中的顶点有两个以上是奇点，则该图不能一笔画出。,图中的顶点都是偶点，没有奇点，则该图可以一笔画出。,15,图中的顶点都是奇点，没有偶点，则该图不能一笔画出。,图中的顶点有二个是奇点，其它是偶点，则从任一奇点出发，则该图可以一笔画出。从任一偶点出发，则该图不能一笔画出。,16,二、中国邮递员问题。,解中国邮递员问题的奇偶点图上作业法：具体步骤如下：,1.,通过加重复边，消灭图中的奇点。将奇点两两配对，在每一对奇点的通路上，均加上重复边。,2,。删除过多的重复边。如果图中某条边的重复边多于一条，则可将它的重复边删除偶数条。,3,。优化重复边。使所加的重复边的总长度最小。,下面通过具体例子来说明具体计算过程：,17,例,6.7,设有街道图如下：假如邮递员从,V,1,点出发，求他的最优投递路线。,4,4,4,4,4,5,9,6,5,5,V,1,3,2,V,9,V,4,V,3,V,2,V,8,V,7,V,6,V,5,解：,18,考虑加边的圈：,V1,V2,V9,V8,中，加边的长度是,4+6=10,，而不加边的长度是,4+5=9,，故需改进如下。,4,4,4,4,4,5,9,6,5,5,V,1,3,2,V,9,V,4,V,3,V,2,V,8,V,7,V,6,V,5,考虑加边的圈：,v4,v5,v6,v9,中，加边的长度是,3+5=8,，而不加边的长度是,4+2=6,，故需改进如下。,图中已无奇点，可得最优投递路线：,19,奇偶点图作业法步骤,构造初始可行方案：由于奇点个数必为偶数，因此奇点必成对出现；同时由于图是连通的，因此每一对奇点之间必存在一条链，在这条链上的各边都加上重复边而成为新图，必定是无奇点的欧拉图。,寻找改进可行方案：在两奇点间检查所有链，若某链的长度小于已加重复边的长度，则在该链的每边加上重复边，去掉原重复边。,重复以上步骤，直到任意两奇点间加重复边的链是最短的为止。,20,求解中国邮递员问题：例子,21,例子的初始可行解,22,例子的修正解,23,