最大流-标号法(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最大流问题,1,给,定一个有向图,G(V,E)，,其中仅有一个点的入次为零,称为,发点,（源）,，记为,v,s,，,仅有,一个点的出次为零称为,收点（汇）,，记为,v,t,，,其余点称为中间点。,基本概念,3,5,1,1,4,2,3,5,2,v,s,v,2,v,1,v,3,v,4,v,t,对于,G,中的每一个弧(,v,i,v,j,)，,相应,地给,一个数,c,ij,（c,ij,0），,称为弧(,v,i,v,j,),的,容量,。我们把这样的,D,称为,网络（或容量网络）,，记为,G(V,E,C)。,2,所谓网络上的,流,，是指定义在弧集,E,上的函数,ff(v,i,v,j,)，,并称,f(v,i,v,j,),为弧(,v,i,v,j,),上的,流量,，简记为,f,ij,。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,v,s,v,2,v,1,v,3,v,4,v,t,标示方式：每条边上标示两个数字，第一个是容量，第二是流量,3,可行流、可行流的流量、最大流。,可行流是指满足如下条件的流：,（,1,）容量限制条件：对,G,中每条边,(,v,i,v,j,),有,（,2,）平衡条件：,对中间点，有：,（即中间点,v,i,的物资输入量等于输出量）,对收点,v,t,与发点,v,s,，有：,（即,v,s,发出的物资总量等于,v,t,接收的物资总量），,W,是网络的总流量。,4,可行流总是存在的，例如,f,=0,就是一个流量为,0,的可行流。,所谓最大流问题就是在容量网络中寻找流量最大的可行流。,一个流,f,=,f,ij,，当,f,ij,=c,ij,，则称,f,对边,(,v,i,v,j,),是饱和的，否则称,f,对边,(,v,i,v,j,),不饱和。,最大流问题实际上是一个线性规划问题。,但利用它与图的密切关系，可以利用图直观简便地求解。,5,给定容量网络,G(V,A,E)，,若点集,V,被,剖分,为两个非空集合,V,1,和,V,2,，,使,v,s,V,1,，v,t,V,2,，,则把,弧集(,V,1,V,2,),称为（分离,v,s,和,v,t,的）,割,集,。,显然，若把某一,割,集的弧从网络中去掉，则从,v,s,到,v,t,便不存在路。所以，直观上说，,割,集是从,v,s,到,v,t,的必经之路。,3,5,1,1,4,2,3,5,2,v,s,v,2,v,1,v,3,v,4,v,t,注：有向边也称为弧。,6,对教材,P259,定义,21,的解释,vs,v1,v4,v3,vt,v2,边集（,vs,v1,），（,v1,v3,），（,v2,v3,），（,v3,vt,），（,v4,vt,）是,G,的割集。其顶点分别属于两个互补不相交的点集。去掉这五条边，则图不连通，去掉这五条边中的任意,1-4,条，图仍然连通。,7,割,集的容量,(简称,割,量,),最小,割,集,割集,(V,1,V,2,),中所有,起点,在,V,1,，,终点,在,V,2,的边的容量的和称为割集容量。例如下图中所示割集的容量为,5,3,5,1,1,4,2,3,5,2,v,s,v,2,v,1,v,3,v,4,v,t,在容量网络的所有割集中，割集容量最小的割集称为最小割集（最小割）。,8,对于可行流,f,f,ij,，,我们把网络中使,f,ij,c,ij,的弧称为,饱和弧,，使,f,ij,0,的弧称为,非零流弧,。,设,f,是一个可行流，,是从,v,s,到,v,t,的一条链，若,满足,前向弧,都是非饱和弧,后向弧都是,都是非零流弧,则称,是（可行流,f,的）一条,增广链,。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,v,s,v,2,v,1,v,3,v,4,v,t,若,是联结发点,v,s,和收点,v,t,的一条链，我们规定,链的方向,是从,v,s,到,v,t,，,则链上的弧被分成两类：,前,向弧,、,后,向弧,。,9,对最大流问题有下列定理：,定理,1,容量网络中任一可行流的流量不超过其任一割集的容量。,定理2（最大流,-,最小,割定理,）,任一容量网络中,，最大流的流量等于最小,割,集的,割,量。,推论,1 可行流,f,*,f,ij,*,是最大流，,当且仅当G中不存在关于,f,*,的增广链。,10,求最大流的标号法,标号法思想是：,先找一个可行流。,对于一个可行流，经过,标号过程,得到从发点,v,s,到收点,v,t,的增广链；经过,调整过程,沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。,11,标号过程:,(1)给,v,s,标号(-,+)，,v,s,成为已标号未检查的点，其余都是未标号点。,(2)取一个已标号未检查的点,v,i,，,对一切未标号点,v,j,：,若有非饱和弧(,v,i,v,j,)，,则,v,j,标号(,v,i,l,(,v,j,)，,其中,l,(,v,j,)min,l,(,v,i,),c,ij,f,ij,，,v,j,成为已标号未检查的点；若有非零弧(,v,j,v,i,)，,则,v,j,标号(-,v,i,l,(,v,j,)，,其中,l,(,v,j,)min,l,(,v,i,),f,ji,，,v,j,成为已标号未检查的点。,v,i,成为已标号已检查的点。,(3)重复步骤(2)，直到,v,t,成为标号点或所有标号点都检查过。若,v,t,成为标号点，表明得到一条,v,s,到,v,t,的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。,调整过程：,在增广链上，前向弧流量增加,l,(,v,t,)，,后向弧流量减少,l,(,v,t,)。,12,下面用实例说明具体的操作方法：例,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),v,s,v,2,v,1,v,3,v,4,v,t,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),v,s,v,2,v,1,v,3,v,4,v,t,在图中给出的可行流的基础上，求,v,s,到,v,t,的最大流。,(-,+),(v,s,4),(-v,1,1),(-v,2,1),(v,2,1),(v,3,1),(3,3),(5,2),(1,0),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),v,s,v,2,v,1,v,3,v,4,v,t,(v,s,3),(-,+),得增广链，标号结束，进入调整过程,无增广链，标号结束，得最大流。同时得最小截。,13,下图中已经标示出了一个可行流，求最大流,-,v,s,3,v,s,4,v,2,4,-,v,4,2,v,s,v,1,v,2,v,3,v,4,v,5,v,s,(4,0),(5,2),(1,0),(4,0),(1,0),(2,2),(3,2),(4,0),(2,0),(5,2),v,4,3,如图已经得到增广链，然后进行调整。,14,调整后的可行流如下图：,v,s,v,1,v,2,v,3,v,4,v,5,v,s,(4,3),(5,2),(1,0),(4,3),(1,0),(2,2),(3,2),(4,0),(2,0),(5,5),-,v,s,3,v,s,1,v,2,1,-,v,4,1,v,3,1,v,5,1,如图已经得到增广链，然后进行调整。,15,调整后的可行流如下图：,v,s,v,1,v,2,v,3,v,4,v,5,v,s,(4,4),(5,2),(1,0),(4,4),(1,0),(2,2),(3,1),(4,1),(2,1),(5,5),-,v,s,3,如图所示最小割集的容量（即当前可行流的流量），就是最大流的流量。,注：用该方法可以同时得到最小割集，即图中连结已标号的点与未标号的点的边集。,16,具有实际背景的例子,国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱辗转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：,17,成都,重庆,武汉,上海,西安,郑州,沈阳,昆明,广州,北京,成都,10,5,15,8,12,10,30,重庆,5,6,15,25,武汉,10,上海,15,8,西安,8,6,郑州,14,8,沈阳,18,昆明,8,10,广州,8,2,6,10,18,用图来描述就是,成,重,武,昆,上,广,西,郑,沈,京,8,5,10,15,8,12,10,30,5,6,15,25,10,15,8,8,6,14,18,8,10,8,2,6,10,发点,v,s,=,成都，收点,v,t,=,北京。前面已订购机票情况表中的数字即是各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零时略去不写，以零流作为初始可行流。,19,利用标号法（经,5,次迭代）可以得到从成都发送旅客到北京的最大流量如图所示,重,武,昆,上,广,西,郑,沈,京,成,30,10,0,6,12,2,8,0,12,5,10,6,10,10,6,0,0,0,10,8,0,18,10,10,0,W(,f,*,)=10+6+12+30+12+10+5=85,20,多个发点多个收点的情形,对于多发点多收点的容量网络的最大流问题可以通过添加两个新点,v,s,与,v,t,扩充为新的单发点与单收点的容量网络的方式解决。,x,1,x,2,.,x,m,y,1,y,2,.,y,n,v,s,v,t,+,+,其中,v,s,到各已知点，以及各已知点到,v,t,的弧的容量取为,+,。,21,最大匹配问题,考虑工作分配问题。有,n,个工人，,m,件工作，每个工人能力不同，各能胜任其中某几项工作。假设每件工作只需一人做，每人只做一件工作。怎样分配才能使尽量多的工作有人做，更多的人有工作做？,该问题用图论的语言可以描述为：在图中，,x,1,x,2,x,n,表示工人，,y,1,y,2,y,m,表示工作，有向边,(,x,i,y,j,),表示工人,x,i,胜任工作,y,j,，因此得到一个二部图。,x,1,x,2,x,3,x,n,y,1,y,2,y,3,y,m,22,如果记,X,=,x,1,x,2,x,n,，,Y,=,y,1,y,2,y,m,，则该二部图可记为,G,=(,X,Y,E,),，而上述的工作匹配问题就是：在图,G,中找一个边集,E,的子集，使得这个子集中任意两条边没有公共端点，最好的方案就是要使得该子集中的边数达到最大。,定义：对于二部图,G,=(,X,Y,E,),，,M,是边集,E,的一个子集，如果,M,中的任意两条边没有公共端点，则称,M,是图,G,的一个匹配（也称对集）。,M,中任意一条边的端点,v,称为（关于,M,的）饱和点，,G,中的其他顶点称为非饱和点。,若不存在另一匹配,M,1,使得,|,M,1,|,M|,，则称,M,为最大匹配。,23,下面的二部图表示了一个匹配问题,x,1,x,2,x,3,x,4,y,1,y,2,y,3,y,4,y,5,x,1,x,2,x,3,x,4,y,1,y,2,y,3,y,4,y,5,x,1,x,2,x,3,x,4,y,1,y,2,y,3,y,4,y,5,它有如下两个最大匹配：,24,最大匹配问题可以化为最大流问题求解。化的方式类似于多发点多收点问题，具体做法是：,在原二部图中添加两个点,v,s,和,v,t,，其中,v,s,有以它为起点，以,X,中各点为终点的有向边；连结,v,t,有以它为终点，,Y,中各点为起点的有向边。并且在这样的图中各边上的容量取为,1,。若一条边上的流量为,1,，则表示一个相应的分配。如下图,x,1,x,2,x,3,x,n,y,1,y,2,y,3,y,m,v,s,v,t,这样最大匹配问题就化为对上图的网络的最大流问题。,25,例,x,1,y,1,有,5,位求职者和,5,项工作岗位，这,5,位求职者各自能胜任的工作如图所示，问如何安排才能实现最大就业,?,x,2,x,3,x,4,y,2,y,3,y,4,y,5,x,5,v,s,v,s,首先将原图扩充成一个容量网络，其中每边的容量均为,1,。然后用标号法来求最大流。,26,x,1,y,1,x,2,x,3,x,4,y,2,y,3,y,4,y,5,x,5,v,s,v,s,-,+,v,s,1,v,s,1,v,s,1,v,s,1,v,s,1,x,1,1,x,1,1,x,1,1,y,1,1,x,1,y,1,x,2,x,3,x,4,y,2,y,3,y,4,y,5,x,5,v,s,v,s,1,1,1,-,+,v,s,1,v,s,1,v,s,1,x,2,1,x,2,1,y,4,1,v,s,1,27,x,1,y,1,x,2,x,3,x,4,y,2,y,3,y,4,y,5,x,5,v,s,v,s,1,1,1,1,1,1,-,+,v,s,1,v,s,1,v,s,1,x,3,1,x,3,1,y,5,1,x,1,y,1,x,2,x,3,x,4,y,2,y,3,y,4,y,5,x,5,v,s,v,s,1,1,1,1,1,1,1,1,1,-,+,v,s,1,v,s,1,x,5,1,x,4,1,-y,4,1,x,2,1,-y,1,1,x,1,1,x,1,1,y,2,1,28,x,1,y,1,x,2,x,3,x,4,y,2,y,3,y,4,y,5,x,5,v,s,v,s,1,1,1,1,1,1,1,1,1,1,1,1,1,1,最大匹配为,(,省略了最后一步的标号过程,):,x,1,y,1,x,2,x,3,x,4,y,2,y,3,y,4,y,5,x,5,29,