第四节-最大流问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/10/10,*,第,4,节网络最大流问题,例连接某产品产地,vs,和销地,vt,的交通网如下：,v,1,v,4,1,1,5,v,2,v,s,v,3,v,t,3,2,5,2,2,4,弧（,vi,，,vj,）：从,vi,到,vj,的运输线，,弧旁数字：这条运输线的最大通过能力,制定一个运输方案，使从,vs,到,vt,的产品数量最多。,2021/10/10,1,弧旁数字：,运输能力。,问题：这个运输网络中，从,v,s,到,v,t,的最大输送量是多少？,v,1,v,4,1,1,5,v,2,v,s,v,3,v,t,3,2,5,2,2,4,2021/10/10,2,7.4.1,最大流的基本概念与定理,（,1,）,.,网络流,网络流,对于网络,G=,（,V,，,A,，,C,），定义在弧集合,A,上的 一个函数,f,=,f,(,v,i,v,j,),称为网络流，,f,(,v,i,v,j,),（简称,f,ij,）为弧,a,ij,A,上的流。,容量,：,在有向图上，每条弧上给出的最大通过能力（最大可能负载）。,c,ij,流量,：网络中加在弧上的负载量（实际负载量）。,f,ij,2021/10/10,3,弧旁数字：,容量,(,a,),图是一个网络,v,2,v,5,3,4,8,v,3,v,1,v,4,v,6,5,10,6,11,17,3,5,v,2,v,5,3,1,3,v,3,v,1,v,4,v,6,1,5,3,6,2,2,2,弧旁数字：,流量,2021/10/10,4,c,ij,f,ij,v,i,v,j,v,2,v,5,(3,3),(4,1),(8,3),v,3,v,1,v,4,v,6,(5,1),(10,5),(6,3),(11,6),(17,2),(3,2),(5,2),2021/10/10,5,（,2,）,.,可行流,可行流,满足下述条件的流,f,称为可行流,:,1),容量限制条件,:,对每一弧,(,v,i,v,j,)A,0,f,ij,c,ij,2),平衡条件,:,对中间点,v,i,(,i,s,t,),有,V(,f,),称为可行流,f,的流量,即发点的净输出量。,如所有,f,ij,=0,，零流。,可行流总是存在的,2021/10/10,6,（,3,）,.,最大流,若,V,（,f*,）为网络可行流，且满足：,V,（,f*,）,=MaxV,（,f,）,f,为网络,D,中的任意,一个可行流，则称,f*,为网络的,最大流,。,（,4,）,.,前向弧与后向弧,设,=,（,x,u,，,v,A,）是网络,G,中的一条初等链并且定义链的方向是从,x,到,A,。若,D,中有弧（,u,，,v,），与,方向一致，则称（,u,，,v,）为链,的,前向弧,，若,D,中有弧（,u,，,v,），与,方向相反,则称（,v,u,），为链,的,后向弧,。,2021/10/10,7,（,5,）,.,增广链,对可行流,f,=,f,ij,：,非饱和弧,：,f,ij,0,零流弧,：,f,ij,=0,链的方向：若,是联结,v,s,和,v,t,的一条链，定义链的方向是从,v,s,到,v,t,。,v,2,v,5,(3,3),(4,1),(8,3),v,3,v,1,v,4,v,6,(5,1),(10,5),(6,3),(11,6),(17,2),(3,2),(5,2),2021/10/10,8,=,(,v,1,v,2,v,3,v,4,v,5,v,6,),+,=(,v,1,v,2,),(,v,2,v,3,),(,v,3,v,4,),(,v,5,v,6,),-,=(,v,4,v,5,),v,2,v,5,(3,3),(4,1),(8,3),v,3,v,1,v,4,v,6,(5,1),(10,5),(6,3),(11,6),(17,2),(3,2),(5,2),2021/10/10,9,增广 链,设,f,是一个可行流,是从,v,s,到,v,t,的一条链,若,满 足下列条件,称之为关于可行流,f,的一条增广 链。,(,v,i,v,j,),-,0,f,ij,c,ij,后向弧 是非零流弧，,(,v,i,v,j,),+,0,f,ij,c,ij,前向弧是 非饱和弧，,v,1,v,2,v,3,v,4,v,5,v,6,(8,4),(6,0),(6,5),(3,3),(5,4),2021/10/10,10,（,6,）,.,截集与截量,对于有向网络,G=(V,A,C,），若,S,为,V,的子集，则称弧集,为网络,G,的一个截集，并将截集中所有弧容量之和称为截容量，即 为截集 的,截容量,（简称为截量）。,（,7,）最小截与最小截量,若 是容量网络中所有截集中截量最小的截集，即,则称 为,G,上的,最小截,，为上的,最小截量,。,2021/10/10,11,性质,任何一个可行流的流量,V(f),都不会超过任一截集的容量。即,可行流,f*,，截集,(V,1,*,，,V,1,*),若,V(f*)=C(V,1,*,，,V,1,*,），,则,f*,必是最大流，,(V,1,*,，,V,1,*),必是,D,的最小截集。,定理,若f*是网络G=（V，A，C）上的可行流，则,可行流f*为最大的充要条件为,中不存在关,于,f*,的增广链。,最大流最小截量定理。任一个网络,D,中，从,v,s,到,v,t,的最大流的流量等于分离,v,s,，,v,t,的最小截集的容量。,2021/10/10,12,7.4.2,寻求最大流的标号法（,FordFulkerson,）,从任一个可行流,f,出发（若网络中没有给定,f,，则从零流开始），经过标号过程与调整过程。,（一）标号过程,2021/10/10,13,标号：,开始，,v,s,标上（,0,，），,v,s,是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查的点,v,i,，对一切未标号的点,v,j,。,（,1,）若弧（,v,i,，,v,j,）上，,f,ij,0,，则给,v,j,标号,(-,i,，,l,(,v,j,),，,l,(,v,j,)=min,l,(,v,i,),f,ji,v,j,成为标号而未检查的点。,f,ij,0,v,i,v,j,(-,i,l,(,v,j,),l,(,v,j,)=min,l,(,v,i,),f,ji,2021/10/10,14,重复上述步骤，一旦,v,t,被标号，则得到一条,v,s,到,v,t,的增广链。若所有标号都已检查过，而,v,t,尚未标号，结束，这时可行流，即最大流。,（二）调整过程,从,v,t,开始，反向追踪，找出增广链,，并在,上进行流量调整。,（,1,）找增广链,如,v,t,的第一个标号为,k,（,或,-k,），,则弧（,v,k,，,v,t,）,（或弧（,v,t,，,v,k,),),。检查,v,k,的第一个标号，若为,i,（或,-,i,），则,(,v,i,v,k,),(,或,(,v,k,v,i,),),。再检查,v,i,的第一个标号,依此下去,直到,v,s,。被找出的弧构成了增广链,。,2021/10/10,15,（,2,）流量调整,令调整量是,l,(,v,t,),，构造新的可行流,f,，,令,去掉所有的标号,对新的可行流,f,=,f,ij,重新进入标号过程。,2021/10/10,16,例 用标号法求下图网络的最大流。弧旁的数字是,(,c,ij,f,ij,),。,解：（一）标号过程。,（,1,）给,v,s,标上（,0,，）；,v,2,v,3,v,1,v,s,v,4,v,t,(3,，,3),(4,，,3),(1,，,1),(5,，,3),(5,，,1),(2,，,2),(2,，,1),(1,，,1),(3,0),（,0,，）,在弧（,v,s,，,v,2,）上，,f,s,2,=,c,s,2,=3,不满足标号条件,。,（,2,）检查,v,s,，在弧（,v,s,，,v,1,）上，,f,s,1,=1,，,c,s,1,=5,，,f,s,1,0,，给,v,2,标号,(-1,l,(,v,2,),在弧（,v,1,，,v,3,）上，,f,13,=2,，,c,13,=2,，不满足标号条件。,v,2,v,3,v,1,v,s,v,4,v,t,(3,，,3),(4,，,3),(1,，,1),(5,，,3),(5,，,1),(2,，,2),(2,，,1),(1,，,1),(3,0),（,0,，）,（,v,s,，,4,）,（,-v,1,，,1,）,（,4,）检查,v,2,，在弧（,v,3,，,v,2,）上，,f,32,=10,，给,v,3,标号,(-2,l,(,v,3,),这里,（,-v,2,，,1,）,2021/10/10,18,在弧（,v,2,，,v,4,）上，,f,24,=3,，,c,24,=4,，,f,24,c,24,给,v,4,标号,(2,l,(,v,4,),其中,（,5,）检查,v,3,，在弧（,v,3,，,v,t,）上，,f,3,t,=1,，,c,3,t,=2,，,f,3,t,c,3,t,，给,v,t,标号,(3,l,(,v,t,),这里,v,t,得到标号，标号过程结束。,v,2,v,3,v,1,v,s,v,4,v,t,(3,，,3),(4,，,3),(1,，,1),(5,，,3),(5,，,1),(2,，,2),(2,，,1),(1,，,1),(3,0),（,0,）,（,v,s,，,4,）,（,-v,1,1,）,（,-v,2,1,）,(v,2,，,1),(v,3,，,1),2021/10/10,19,（二）调整过程,：从,v,t,开始逆向追踪，找到增广链。,（,v,s,v,1,v,2,v,3,v,t,）,=1,，,在,上进行流量,=1,的调整，得,可行流,f,如右,图所示：,v,2,v,3,v,1,v,s,v,4,v,t,(3,，,3),(4,，,3),(1,，,1),(5,，,3),(5,，,1),(2,，,2),(2,，,1),(1,，,1),(3,0),（,0,）,（,v,s,，,4,）,（,-v,1,1,）,（,-v,2,1,）,(v,2,，,1),(v,3,，,1),v,2,v,3,v,1,v,s,v,4,v,t,(3,，,3),(4,，,3),(1,，,0),(5,，,3),(5,，,2),(2,，,2),(2,，,2),(1,，,0),(3,0),2021/10/10,20,去掉各点标号，从,v,s,开始，重新标号。,点,v,1,：标号过程,无法进行，所以,f,即为最大流。,V,（,f,）,=3+2=5,v,2,v,3,v,1,v,s,v,4,v,t,(3,，,3,),(4,，,3),(1,，,0),(5,，,3),(5,，,2,),(2,，,2),(2,，,2),(1,，,0),(3,0),（,0,，）,（,v,s,，,3,）,截集：,V,1,，,V,1,=,（,v,s,，,v,2,），（,v,1,，,v,3,）,V,（,f,）,=CV,1,，,V,1,=5,V,1,=(,v,s,v,1,)V,1,=(,v,2,v,3,v,4,v,t,),问题：,(,v,2,v,1,),是不是截集,V,1,，,V,1,中的弧？,2021/10/10,21,例 用标号法求下图网络的最大流。弧旁的数字是,(,c,ij,f,ij,),。,v,1,v,4,v,2,v,s,v,3,(3,，,3),(5,，,1),(2,，,2),(6,，,2),(3,，,2),(2,，,2),(2,0),(6,，,3),(5,，,2),v,t,2021/10/10,22,解：第一轮 标号过程（,1,）,v,s,标（,0,，,+,），,v,s,为已标号未检查点。（,2,）检查,v,s,，给,v,2,标号（,v,s,，,l(v,2,),），,v,s,成为已标号已检查的点，,v,2,成为已标号未检查的点。（,3,）检查,v,2,，给,v,1,标号（,-,v,2,，,l(v,1,),）。同理给,v,4,标号为（,v,2,，,1,），,v,2,成为已标号已检查的 点，,v,1,，,v,4,成为已标号未检查的点。（,4,）检查,v,1,，给,v,3,标号为（,v,1,，,2,），,v,3,成为已标号未检 查的点。（,5,）检查,v,3,，给,v,t,标号为（,v,3,，,2,）。因为,v,t,已被标号，所以说明找到一条增广链。调整过程 按点的第一个标号，以,v,t,点开始，回溯找到一条增广 链，,如下图红线所示：,2021/10/10,23,v,t,(0,，,+),（,v,s,，,4,）,（,-v,2,，,2,）,（,v,2,，,1,）,（,v,1,，,2,）,（,v,3,，,2,）,v,1,v,4,v,2,v,s,v,3,(3,，,3),(5,，,1),(2,，,2),(6,，,2),(3,，,2),(2,，,2),(2,0),(6,，,3),(5,，,2),2021/10/10,24,v,t,v,1,v,4,v,2,v,s,v,3,(3,，,3),(5,，,1),(2,，,2),(6,，,2),(3,，,2),(2,，,2),(2,0),(6,，,3),(5,，,2),在增广链上进行了流量调整。,前向弧,后向弧,于是调整后流量如下图所示。,(0,，,+),（,v,s,，,4,）,（,-v,2,，,2,）,（,v,2,，,1,）,（,v,1,，,2,）,（,v,3,，,2,）,2021/10/10,25,v,1,v,4,v,2,v,s,v,3,(3,，,3),(5,，,3),(2,，,0),(6,，,4),(3,，,2),(2,，,2),(2,0),(6,，,5),(5,，,2),v,t,2021/10/10,26,第二轮：,标号过程,（,1,）,v,s,标（,0,，,+,），,v,s,为已标号未检查点。,（,2,）检查,v,s,，给,v,2,标号（,v,s,，,2,），,v,2,成为已标号未检查,的点。,（,3,）检查,v,2,，给,v,4,标号（,v,2,，,1,），,v,4,成为已标号未检,查的点。,（,4,）检查,v,4,，给,v,t,标号为（,v,4,，,1,），,v,t,被标，转入下 一阶段。,调整过程,根据标号过程，以,v,t,点开始，回溯找到一条增广链，如,下图红线所示。,2021/10/10,27,v,t,(0,，,+),v,1,v,4,v,2,v,s,v,3,(3,，,3),(5,，,3),(2,，,0),(6,，,4),(3,，,2),(2,，,2),(2,0),(6,，,5),(5,，,2),（,v,s,，,2,）,（,v,2,，,1,）,（,v,4,，,1,）,2021/10/10,28,v,1,v,4,v,2,v,s,v,3,(3,，,3),(5,，,3),(2,，,0),(6,，,4),(3,，,2),(2,，,2),(2,0),(6,，,5),(5,，,2),增广链上的三个弧都为前向弧，于是调整如下：,于是新调整的流量如下图所示。,v,t,(0,，,+),（,v,s,，,2,）,（,v,2,，,1,）,（,v,4,，,1,）,2021/10/10,29,v,1,v,4,v,2,v,s,v,3,(3,，,3),(5,，,3),(2,，,0),(6,，,5),(3,，,3),(2,，,2),(2,0),(6,，,5),(5,，,3),第三轮,v,s,标（,0,+,），,v,2,标号（,v,s,，,1,），检查,v,2,点，标号 过程无法继续下去，于是说明了对于上图所示的新,流，不存在增广链，上图所示的流就是最 大流，算法结束。,最大流量,=3+3+2=8,最小截集为,（,v,s,v,1,），（,v,2,v,3,），（,v,2,v,4,）,，,最小截量为,8,。,v,t,(0,，,+),（,v,s,，,1,）,2021/10/10,30,