《图论最大流问题》PPT课件.ppt

网络与网络流,一、网络流的基本概念先来看一个实例。现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。S、T和中转站作为点，每条公路作为弧作有向图，每条弧上赋予该公路的最大运载量。最多能将多少货物从S运抵T？,定义1若有向图满足下列条件：(1)有且仅有一个入度为零的顶点s，称为源点；(2)有且仅有一个出度为零的顶点t，称为汇点;(3)每一条弧(vi,vj)都有一个非负数cij，称为该边的容量。如果vi,vj之间没有边，cij=0。则称之为网络，记为N=(V,E,C).,图1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。,图1,图2,网络流：是定义在弧集合E上一个函数f=f(vi,vj)，并称f(vi,vj)为弧(vi,vj)上的流量(简记为fij)。如图2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。,二、可行流与最大流,1.定义在实际问题中，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等。因此有定义如下。,定义2网络N中每条边都给定一个非负实数fij满足下列条件(1)容量约束：0fijcij，(vi,vj)E，(2)守恒条件对于中间点：流入量=流出量，即,对于源点与汇点：源点的净流出量=汇点的净流入量，即,这一组fij称为网络N上的可行流,记为f，w称为流量.,网络N中流值最大的流f*称为N的最大流.,2.可增广（流）路径,可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。定义3设f是一个可行流，P是从源点s到汇点t的一条路，若P满足下列条件：(1)在P上的所有前向弧(vivj)都是非饱和弧，即0fijcij；(2)在P上的所有后向弧(vivj)都是非零弧，即00时，则y标记为(x,-,dy)，其中dy=mindx,fxy之后，称y已标记未检查。,(3)与结点x邻接的所有结点都标记完之后，将x的标记的符号“+”或“-”加以标记，表示x已标记且已检查。StepA3重复stepA2，直到收点t被标记，或者收点不能获得标记为止。如果是前者，转向增广过程，如果是后者，算法结束，所得流即是最大流。,2.增广过程BstepB1令z=tstepB2若z的标记为(q,+,dz)，则,若z的标记为(q,-,dz)，则,stepB3若q=s，则把全部标记去掉，转向标记过程A,否则令z=q，转到B2.,例求图9所示的最大流。边上的数字表示容量。,设f是任意可行流，从零流开始，设每条边的流均为0，即,1.找一条可增广路并增加其流值,A(标记过程)发点s标记为(s，+,)考察与s邻接的点v1和v2。对点v1，,则,图9,s,t,8,0,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,于是，v1标记为（s,+,8）,同样的方法v2得到标记（s,+,7）。与s邻接的点都已标记，s标记中的“+”写成，表示s已标记，已检查，如图10。,图10,(s,),（s,+,8）,（s,+,7）,(3)重复stepA2,选一已标记、未检查的点，如选v1点，与v1邻接且未标记的点只有v3。因,v3标记为(v1,+,8)。点v1已标记、已检查，将其标记中的“+”写成，如图11。,s,t,8,0,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,图11,(s,),（s,8）,（s,+,7）,则,（v1,+,8）,(4)重复stepA2,选一已标记、未检查的点，如选v3点，与v3邻接且未标记的点有v4和t。,对于点v4，因（v4,v3）E且fv4v3=0，因此，不能用点v3去标记点v4.对于点t，因,s,t,8,0,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,图12,(s,),（s,8）,（s,+,7）,（v1,+,8）,t标记为(v3,+,5)。如图12。由于t已标记，转到增广过程B.,（v3,+,5）,B.增广过程,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,图13,至此，完成增广过程。如图13。,2.找一条可增广路并增加其流值,图14,A(标记过程),(2)考察与s邻接的点v1和v2。对点v1，,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,(1)发点s标记为(s，+,),(s,+,),s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,于是，v1标记为（s,+,3）,同样的方法v2得到标记（s,+,7）。与s邻接的点都已标记，s标记中的“+”写成，表示s已标记，已检查，如图15。,图15,(s,),（s,+,3）,（s,+,7）,(3)重复stepA2,选一已标记、未检查的点，如选v2点，与v2邻接且未标记的点有v3,v4。因,v4标记为(v2,+,7)。v3不能同过v2标记。点v2已标记、已检查，将其标记中的“+”写成，如图16。,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,图16,(s,),（s,3）,（s,+,7）,则,（v2,+,7）,图17,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,(s,),（s,+,3）,（s,7）,（v2,7）,（v4,+,7）,图18,B.增广过程。从标记过程得到一条可增广路：,s,t,8,5,v1,v4,v3,v2,7,7,5,0,2,0,9,7,6,0,10,7,5,5,9,5,增值d=7,于是得到图18，至此又完成一次增广过程。,3.找一条可增广路并增加其流值,图19,对图18重新标记得到图19，得到一条可增广路：,s,t,8,5,v1,v4,v3,v2,7,7,5,0,2,0,9,7,6,0,10,7,5,5,9,5,(s,),（s,+,3）,（v1,3）,（v2,+,2）,（v4,+,2）,增值d=2,于是得到图20。,图20,s,t,8,7,v1,v4,v3,v2,7,7,5,0,2,0,9,9,6,0,10,9,5,5,9,5,图21,4.对图20重新标记得到图21，v4和t均不能再获标记，算法结束。最大流为14。,s,t,8,7,v1,v4,v3,v2,7,7,5,2,2,0,9,9,6,0,10,9,5,5,9,5,(s,),（s,1）,（v1,1）,（v1,1）,将获得标记的结点归为S,不能标记的结点归为,即,图22,s,t,8,7,v1,v4,v3,v2,7,7,5,2,2,0,9,9,6,0,10,9,5,5,9,5,(s,),（s,1）,（v1,1）,（v1,1）,得到最小割为：,其容量为,可行流：网络N中每条边都给定一个非负实数fij满足下列条件(1)容量约束：0fijcij，(vi,vj)E，(2)守恒条件：对于中间点：流入量=流出量，即,这一组fij称为网络N上的可行流,记为f.,网络N中对应上述可行流的流量：,网络定义推广：入度为0和出度为0的限制去掉。,考虑推广后的网络。网络N中每条边都给定一个非负实数fij满足下列条件(1)容量约束：bijfijcij，(vi,vj)E，(2)守恒条件：对于中间点：流入量=流出量，即,二下界非零网络最大流算法,这一组fij称为N上的可行流,记为f，也称为流函数.,求使流量,最大的流函数f.,记N为N(V,E,s,t,b,c).,下界非零的网络，流函数可能不存在。,s,v2,v1,t,5,6,1,2,3,4,7,8,如图，边上的两个数分别为bij和cij，其流函数不存在。,建立N(V,E,s,t,b,c)的可行流存在的充分必要条件。,为了叙述方便引入记号：a(v)和b(v)，分别表示进入v和从v出来的边集合。,构造N(V,E,s,t,b,c)的伴随网络N1(V1,E1,s1,t1,b1,c1)：(1)V1=Vs1,t1,s1,t1V;,(2)任何vV,加新边e=vt1,且令,c1(e)是N1中边e的容量，下界b(e)=0.,(3)任何vV,加新边e=s1v,且令,c1(e)是N1中边e的容量，下界b(e)=0.,(4)E中的边e仍在N1中保留，但b1(e)=0,c1(e)=c(e)-b(e).,(5)加新边st与ts的容量：下界均为0，容量为。,定理N(V,E,s,t,b,c)存在可行流当且仅当伴随网络N1(V1,E1,s1,t1,b1,c1)上的最大流f1使流出s1的一切边e均满足f1(e)=c1(e).这时f1(e)+b(e)是N上一个可行流。,证明N1上的最大流f1使流出s1的一切边e均满足f1(e)=c1(e).对于网络N，令f(e)=f1(e)+b(e),eE则f是N上一个可行流.这是因为eE时，,即,f(e)满足约束条件(1).,下面证明满足守恒条件(2):,对于vV-s,t,记s=s1v,t=vt1,由于f1是N1的流函数，f1应满足N1中的守恒条件：,又已知从s1出发的边e，f1(e)=c1(e),故,进入t1的边e，f1(e)=c1(e),故,即f在N中满足守恒条件(2).f是可行流.,反之，若f是可行流，令,f1是N1中使流出s1的一切边e均满足f1(e)=c1(e)的最大流.,根据上述定理给出求下界非0的网络最大流的步骤：画出N的伴随网络N1。求出N1的最大流f1。检验f1是否使流出s1的一切边e均满足f1(e)=c1(e).若是，则N上有可行流f,f(e)=f1(e)+b(e)；否则，N上没有可行流。(4)若已得可行流f,将f放大，求N的最大流，这时无需考虑下界条件。,s,v1,v3,0,10,1,3,3,5,2,6,v2,v4,5,7,t,2,8,2,4,1,3,s,v1,v3,10,2,4,v2,v4,2,t,6,t1,s1,2,1,1,2,2,5,5,5,5,3,3,5,5,4,4,4,4,1,1,2,2,2,2,s,v1,v3,10,2,2,2,2,0,4,0,v2,v4,2,0,t,6,2,t1,s1,2,0,2,1,1,1,2,2,5,5,5,5,3,3,5,5,4,4,4,4,1,1,2,2,8,5,8,0,s,v1,v3,10,2,2,2,2,0,4,0,v2,v4,2,0,t,6,2,2,0,2,1,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,第一个数字是c(e),第二个是f(e)=f1(e)+b(e),第一个数字是c1(e),第二个是f1(e),第一个数字是b(e),第二个是c(e),s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,第一个数字是c(e),第二个是f(e)=f1(e)+b(e),s,v1,v3,10,8,3,3,5,5,6,6,v2,v4,7,5,t,8,8,4,2,3,0,第一个数字是c(e),第二个是f*,最大流11。,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,(s,),（s,+,8）,（v3,+,4）,（v3,-,2）,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,(s,),（s,8）,（v3,+,4）,（v3,-,1）,（v4,+,4）,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,(s,),（s,8）,（v3,+,4）,（v3,-,1）,（v4,+,4）,s,v1,v3,10,6,3,3,5,3,6,6,v2,v4,7,5,t,8,8,4,2,3,2,增流,(s,),（s,+,4）,（v3,-,2）,（v2,+,2）,s,v1,v3,10,6,3,3,5,3,6,6,v2,v4,7,5,t,8,8,4,2,3,2,增流,s,v1,v3,10,7,3,3,5,4,6,6,v2,v4,7,5,t,8,8,4,2,3,1,三、最小费用最大流,一批货物要从工厂运至车站，可以有多条线路进行选择，在不同的线路上每吨货物的运费不同，且每条线路的运输能力有限。怎样运输才能使费用最少?用结点s代表工厂，t代表车站，线路为边，线路的交点为网络的结点，每条边都有两个权：容量c和单位费用a，于是构成网络流图N，问题变成求N的最小费用流。,一个旅行社接待的一批客人第二天要从甲地飞往乙地，怎样安排才能使旅费最省？这也是一个最小费用流问题，网络的结点是甲乙两地之间的各个机场，边表示第二天的各个航班，其容量是该航班有效座位数，而费用则是该航班的机票费。,设有一个网络N(V,E)，V=s,a,b,c,t，E中的每条边(i,j)对应一个容量cij，输送单位流量所需费用为aij。如有一个运输方案（可行流），流量为fij，w是要求从s到t的流量。于是最小费流（最小费用最大流）问题可以描述如下：,约束条件,确定最小费最大流的过程实际上是一个多次迭代的过程。基本思想是：从零流为初始可行流开始，在每次迭代过程中对每条边赋予与c(i,j)（容量）、a(i,j)（单位流量运输费用）、f(i,j)（现有流的流量）有关的权数(i,