图论最大流问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,网络与网络流,一、网络流的基本概念,先来看一个实例。,现在,想将一些物资从,S,运抵,T,，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。,S,、,T,和中转站作为点，每条公路作为弧作有向图，每条弧上赋予该公路的最大运载量。最多能将多少货物从,S,运抵,T,？,1,定义1,若有向图满足下列条件：,(1)有且仅有一个入度为零的顶点s，称为源点；,(2) 有且仅有一个出度为零的顶点t，称为汇点;,(3) 每一条弧(,v,i,v,j,)都有一个非负数,c,ij,，称为该,边的容量。如果,v,i,v,j,之间没有边，,c,ij,=0。,则称之为网络，记为,N,= (,V,E,C,).,图1所给出的一个赋权有向图N就是一个网络，,指定,v,1,是源点，,v,4,为汇点，弧旁的数字为,c,ij,。,2,图1,图2,网络流：是定义在弧集合E上一个函数,f,=,f,(,v,i,v,j,)，并称,f,(,v,i,v,j,)为弧(,v,i,v,j,)上的流量(简记为,f,ij,)。如图2所示的网络N，弧上两个数，第一个数表示容量,c,ij,，第二个数表示流量,f,ij,。,3,二、可行流与最大流,1.,定义,在实际问题中，对于流有两个显然的要求：一是,每个弧上的流量不能超过该弧的最大通过能力,(即弧,的容量)；二是中间点的流量为0，源点的净流出,量,和汇点的净流入量必相等。因此有定义如下。,4,定义,2,网络N中每条边都给定一个非负实数,f,ij,满足下列条件,(1)容量约束：0,f,ij,c,ij,，(,v,i,v,j,),E,， (2)守恒条件 对于中间点：流入量=流出量，即,对于源点与汇 点：源点的净流出量,=,汇点的净流入量，即,这一,组,f,ij,称为网络,N,上的,可行流,记为,f,，,w,称为流量.,网络,N,中流值最大的流,f,*称为,N,的,最大流.,5,2. 可增广（流）路径,可增广路径,，是指这条路径上的流可以修改，通,过修改，使得整个网络的流值增大。,定义3,设,f,是一个可行流，,P,是从源点,s,到汇点,t,的一,条路，若,P,满足下列条件： (1)在,P,上的所有前向弧(,v,i,v,j,)都是非饱和弧，即,0,f,ij,c,ij,；,(2)在,P,上的所有后向弧(,v,i,v,j,)都是非零弧，即,0,f,ij,c,ij,。则称,P,为(关于可行流,f,的)一条可增广路,径。,6,3. 割及其容量,定义4,如果S是V的一个子集， ，,，则称边集 为网络N的一个割。显然，若把某一割的弧从网络中去掉，则从,s,到,t,就不存在路。所以直观上讲，割是从,s,到,t,的必经之道。,7,定义,5,给一割,，把其中所有弧的容量,之和称为这个,割的容量,，记为,，即,网络N中容量最小的割,称为N的,最小割,。,不难证明，任何一个可行流的流量,w,都不会超过任一割的容量，即,8,例如，图2中，若,图2,9,定理1,网络的最大流量不超过最小的割的容量，即,证明 设,f,是给定网络的任意可行流，由可行流的性质,任给一个割,即,10,所以,因,由于,所以,由于可行流和割的任意性，定理成立。,11,如果网络的可行流不是最大流，就一定存在从s到t的,可增流路径,。,令,s,v,1,v,2,v,k,t是一条s到t的路径,P,st,，其中每条边的方向都是v,j,到v,j+1,称为,向前边,。如果这条路径上每条边,e,ij,都有,f,ij,c,ij,，那么令,令,P,st,每条边的流都增加,d,，所得流分布仍然是网络的可行流分布，但流增加了,d,.,12,(5,3),(2,1),(6,2),(4,1),(5,2),s,v,4,t,v,1,v,2,v,3,(5,4),(2,2),(6,2),(4,2),(5,3),s,v,4,t,v,1,v,2,v,3,d,=1,图3 网络中的一部分,图4,13,还可以包含向后的可增流路径,P,st,，要求向前边,e,ij,都有,f,ij,0,对前向边,e,ij,后向边,e,ji,图5，,d,=1,14,图5，,d,=1,(5,3),(2,1),(6,2),(4,1),(5,2),s,v,4,t,v,1,v,2,v,3,图5，,d,=1,(5,4),(2,2),(6,1),(4,2),(5,3),s,v,4,t,v,1,v,2,v,3,15,(1,0),(2,0),(1,0),(2,0),(2,0),s,t,a,c,b,第1条可增路s,c,b,t,d,(1,0),(1,0),(2,2,),(1,0),(2,2,),(2,2,),s,t,a,c,b,d,(1,0),d,=2,第2条可增路s,a,b,c,d,t,(1,0),(1,0),(1,1,),(2,2,),(1,1,),(2,1,),(2,2,),s,t,a,c,b,d,(1,1,),(1,1,),最大流w=3,图6,图7,图8,16,定理2,最大流最小割定理：在一个网络N中，最大流量等于最小割的容量,。,证明 设网络的一个可行流,f,为最大流，确定一个割如下：,是向前边且,，则,若,是后前边且,，则,若,则,，,否则存在,s,到,t,的一条可增路，矛盾。,因此，,，,则任意,的边(x,y)有,若,是向前边，,是后前边，,17,由定理,1,，,又,所以,18,最大网络流,最大流问题实际上是求一可行流,f,ij,，使得,w,达到最大。若给了一个可行流,f,，只要判断N中有无关于,f,的,增广路径,，如果有增广路径，改进,f,， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。,设 是最小割，下面用,顶点标号法,来定义,S,*，在标号过程中，有标号的顶点表示是,S,*中的点，没有标号的点表示不是,S,*中的点。,如 果,t,有标号，则说明找到了一条增广路；,如果标号过程进行不下去，而,t,没有标号，则说明不存在增广路，于是得到了最大流，同时也得到了一个最小割集。,19,求最大流的标号法(Ford,Fulkerson) 从一个可行流(一般取零流)开始，不断进行以下的,标号过程,与,增广过程,，直到找不到关于,f,的可增广路径为止。 1. 标号过程A标记过程中每个结点给予3个标号，第一个标号表示该点的先驱点，第二个标号为“+”或“-”，表示先驱点与该点连接的边在可增广路中是前向边还是反向边，第三个标号表示这条边上能增加或减少的流值。,20,stepA1 发点s标记为(s，+, )，此时成为已标记，未检查，其余点均称为未标记，未检查。,stepA2 任选一已标记未检查的结点,x,，若结点,y,与,x,邻接且未标记，则当,(1) 若(,x,y,),E,且,c,xy,f,xy,时，则,y,标记为(,x,+,d,y,)，其中,d,y,=,min,d,x,c,xy,-,f,xy,之后，称,y,已标记未检查。,(2) 若(,y,x,),E,且,f,yx,0时，则,y,标记为(,x,-,d,y,)，其中,d,y,=,min,d,x,f,xy,之后，称,y,已标记未检查。,21,(3) 与结点,x,邻接的所有结点都标记完之后，将,x,的标记的符号“+”或“-”加以标记，表示,x,已标记且已检查。,StepA3 重复stepA2，直到收点,t,被标记，或者收点不能获得标记为止。如果是前者，转向增广过程，如果是后者，算法结束，所得流即是最大流。,22,2. 增广过程BstepB1 令,z,=,t,stepB2 若,z,的标记为(,q,+,d,z,)，则,若,z,的标记为(,q,-,d,z,)，则,stepB3 若,q=s,，则把全部标记去掉， 转向标记过程A, 否则令,z=q,，转到B2.,23,例 求图9所示的最大流。边上的数字表示容量。,s,t,8,v,1,v,4,v,3,v,2,7,5,2,9,6,10,5,9,设,f,是任意可行流，从零流开始，设每条边的流均为0 ，即,1.,找一条可增广路并增加其流值,A (标记过程),发点,s,标记为,(s,，,+, ),考察与,s,邻接的点,v,1,和,v,2,。对点,v,1,，,则,图9,24,s,t,8,0,v,1,v,4,v,3,v,2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,于是，,v,1,标记为（,s,+,8）,同样的方法,v,2,得到标记（,s,+,7）。,与s邻接的点都已标记，s标记中的“+”写成,，表示s已标记，已检查，如图10。,图10,(s, ),（,s,+,8）,（,s,+,7）,25,(3) 重复stepA2,选一已标记、未检查的点，如选,v,1,点，与,v,1,邻接且未标记的点只有,v,3,。因,v,3,标记为(,v,1,+,8)。,点,v,1,已标记、已检查，将其标记中的“+”写成,，如图11。,s,t,8,0,v,1,v,4,v,3,v,2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,图11,(s, ),（,s,8）,（,s,+,7）,则,（,v,1,+,8）,26,(4) 重复stepA2,选一已标记、未检查的点，如选,v,3,点，与,v,3,邻接且未标记的点有,v,4,和,t,。,对于点,v,4,，因（,v,4,v,3,）,E,且,f,v,4,v,3,=0，因此，不能用点,v,3,去标记点,v,4,.,对于点t，因,s,t,8,0,v,1,v,4,v,3,v,2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,图12,(s, ),（,s,8）,（,s,+,7）,（,v,1,+,8）,t标记为(,v,3,+,5),。,如图12。,由于t已标记，,转到增广过程B.,（,v,3,+,5）,27,B. 增广过程,s,t,8,5,v,1,v,4,v,3,v,2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,图13,至此，完成增广过程,。,如图13。,28,2.,找一条可增广路并增加其流值,图14,A (标记过程),(2)考察与,s,邻接的点,v,1,和,v,2,。对点,v,1,，,s,t,8,5,v,1,v,4,v,3,v,2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,(1) 发点,s,标记为(s，+, ),(s,+, ),29,s,t,8,5,v,1,v,4,v,3,v,2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,于是，,v,1,标记为（,s,+,3）,同样的方法,v,2,得到标记（,s,+,7）。,与s邻接的点都已标记，s标记中的“+”写成,，表示s已标记，已检查，如图15。,图15,(s, ),（,s,+,3）,（,s,+,7）,30,(3) 重复stepA2,选一已标记、未检查的点，如选,v,2,点，与,v,2,邻接且未标记的点有,v,3,v,4,。因,v,4,标记为(,v,2,+,7)。v,3,不能同过v,2,标记。,点,v,2,已标记、已检查，将其标记中的“+”写成,，如图16。,s,t,8,5,v,1,v,4,v,3,v,2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,图16,(s, ),（,s,3）,（,s,+,7）,则,（,v,2,+,7）,31,图17,s,t,8,5,v,1,v,4,v,3,v,2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,(s, ),（,s,+,3）,（,s,7）,（,v,2,7）,（,v,4,+,7）,32,图18,B. 增广过程。从标记过程得到一条可增广路：,s,t,8,5,v,1,v,4,v,3,v,2,7,7,5,0,2,0,9,7,6,0,10,7,5,5,9,5,增值,d,=7,于是得到图18，至此又完成一次增广过程。,33,3.,找一条可增广路并增加其流值,图19,对图18重新标记得到图19，得到一条可增广路：,s,t,8,5,v,1,v,4,v,3,v,2,7,7,5,0,2,0,9,7,6,0,10,7,5,5,9,5,(s, ),（,s,+,3）,（,v,1,3）,（,v,2,+,2）,（,v,4,+,2）,增值,d,=2,于是得到图20。,34,图20,s,t,8,7,v,1,v,4,v,3,v,2,7,7,5,0,2,0,9,9,6,0,10,9,5,5,9,5,35,图21,4. 对图20重新标记得到图21，v4和t均不能再获标,记，算法结束。最大流为14。,s,t,8,7,v,1,v,4,v,3,v,2,7,7,5,2,2,0,9,9,6,0,10,9,5,5,9,5,(s, ),（,s,1）,（,v,1,1）,（,v,1,1）,将获得标记的结点归为,S,不能标记的结点归为,即,36,图22,s,t,8,7,v,1,v,4,v,3,v,2,7,7,5,2,2,0,9,9,6,0,10,9,5,5,9,5,(s, ),（,s,1）,（,v,1,1）,（,v,1,1）,得到最小割为：,其容量为,37,可行流：,网络N中每条边都给定一个非负实数,f,ij,满足下列条件,(1)容量约束：0,f,ij,c,ij,，(,v,i,v,j,),E,， (2)守恒条件：对于中间点：流入量=流出量，即,这一,组,f,ij,称为网络,N,上的,可行流,记为,f,.,网络,N,中对应上述可行流的流量：,网络定义推广：入度为0和出度为0的限制去掉。,38,考虑推广后的网络。,网络N中每条边都给定一个非负实数,f,ij,满足下列条件,(1)容量约束：,b,ij,f,ij,c,ij,，(,v,i,v,j,),E,， (2)守恒条件：对于中间点：流入量=流出量，即,二 下界非零网络最大流算法,这一,组,f,ij,称为,N,上的,可行流,记为,f，,也称为流函数,.,求使流量,最大的流函数,f,.,记,N,为,N,(,V,E,s,t,b,c,).,39,下界非零的网络，流函数可能不存在。,s,v,2,v,1,t,5,6,1,2,3,4,7,8,如图，边上的两个数分别为,b,ij,和,c,ij,，其流函数不存在。,建立,N,(,V,E,s,t,b,c,)的,可行流存在的充分必要条件。,为了叙述方便引入记号：,a,(,v,)和,b,(,v,)，分别表示进入,v,和从,v,出来的边集合。,40,构造,N,(,V,E,s,t,b,c,)的伴随网络,N,1,(,V,1,E,1,s,1,t,1,b,1,c,1,)：,(1),V,1,=,V,s,1,t,1,s,1,t,1,V,;,(2) 任何,v,V,加新边,e,=,vt,1,且令,c,1,(,e,)是,N,1,中边,e,的容量，下界,b,(,e,)=0.,(3) 任何,v,V, 加新边,e,=,s,1,v,且令,c,1,(,e,)是,N,1,中边,e,的容量，下界,b,(,e,)=0.,41,(4),E,中的边,e,仍在,N,1,中保留，但,b,1,(,e,)=0,c,1,(,e,)=,c,(,e,)-,b,(,e,).,(5) 加新边,st,与,ts,的容量：下界均为0，容量为。,定理,N,(,V,E,s,t,b,c,)存在可行流当且仅当伴随网络,N,1,(,V,1,E,1,s,1,t,1,b,1,c,1,)上的最大流,f,1,使流出,s,1,的一切边,e,均满足,f,1,(,e,)=,c,1,(,e,). 这时,f,1,(,e,)+,b,(,e,)是,N,上一个可行流。,证明,N,1,上的最大流,f,1,使流出,s,1,的一切边,e,均满足,f,1,(,e,)=,c,1,(,e,). 对于网络,N,，令,f(e)=f,1,(,e,)+,b,(,e,) ,e,E,则,f,是,N,上一个可行流. 这是因为,e,E,时,，,42,即,f,(,e,),满足约束条件,(1).,下面证明满足守恒条件(2):,对于v,V-s,t,记,s,=,s,1,v,t,=,vt,1, 由于,f,1,是,N,1,的流函数，,f,1,应满足,N,1,中的守恒条件：,43,又已知从s,1,出发的边e，,f,1,(,e,) =,c,1,(,e,),故,进入t,1,的边e，,f,1,(,e,) =,c,1,(,e,),故,44,即,f,在,N,中满足守恒条件(2).,f,是可行流.,反之，若,f,是可行流，令,f,1,是,N,1,中使流出,s,1,的一切边,e,均满足,f,1,(,e,)=,c,1,(,e,)的最大流.,45,根据上述定理给出求下界非0 的网络最大流的步骤：,画出,N,的伴随网络,N,1,。,求出,N,1,的最大流,f,1,。,检验,f,1,是否使流出,s,1,的一切边,e,均满足,f,1,(,e,)=,c,1,(,e,).,若是，则,N,上有可行流,f,f,(,e,),=f,1,(,e,)+,b,(,e,),；,否则，,N,上没有可行流。,(4),若已得可行流,f,将,f,放大，求,N,的最大流，这时,无需考虑下界条件。,46,s,v,1,v,3,0,10,1,3,3,5,2,6,v,2,v,4,5,7,t,2,8,s,v,1,v,3,0,10,1,3,3,5,2,6,v,2,v,4,5,7,t,2,8,2,4,1,3,47,s,v,1,v,3,10,2,4,v,2,v,4,2,t,6,t,1,s,1,2,1,1,2,2,5,5,5,5,3,3,5,5,4,4,4,4,1,1,2,2,2,2,48,s,v,1,v,3,10,2,2,2,2,0,4,0,v,2,v,4,2,0,t,6,2,t,1,s,1,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,49,s,v,1,v,3,10,2,2,2,2,0,4,0,v,2,v,4,2,0,t,6,2,2,0,2,1,s,v,1,v,3,10,2,3,3,5,3,6,2,v,2,v,4,7,5,t,8,4,4,2,3,2,s,v,1,v,3,0,10,1,3,3,5,2,6,v,2,v,4,5,7,t,2,8,第一个数字是,c,(,e,),第二个是,f,(,e,)=,f,1,(,e,)+,b,(,e,),第一个数字是,c,1,(,e,),第二个是,f,1,(,e,),第一个数字是,b,(,e,),第二个是,c,(,e,),50,s,v,1,v,3,10,2,3,3,5,3,6,2,v,2,v,4,7,5,t,8,4,4,2,3,2,第一个数字是,c,(,e,),第二个是,f,(,e,)=,f,1,(,e,)+,b,(,e,),s,v,1,v,3,10,8,3,3,5,5,6,6,v,2,v,4,7,5,t,8,8,4,2,3,0,第一个数字是,c,(,e,),第二个是,f,*,最大流11。,51,s,v,1,v,3,10,2,3,3,5,3,6,2,v,2,v,4,7,5,t,8,4,4,2,3,2,(,s,),（,s,+,8）,（,v,3,+,4）,（,v,3, - ,2）,s,v,1,v,3,10,2,3,3,5,3,6,2,v,2,v,4,7,5,t,8,4,4,2,3,2,(,s,),（,s,8）,（,v,3,+,4）,（,v,3, - ,1）,（,v,4,+,4）,52,s,v,1,v,3,10,2,3,3,5,3,6,2,v,2,v,4,7,5,t,8,4,4,2,3,2,(,s,),（,s,8）,（,v,3,+,4）,（,v,3, - ,1）,（,v,4,+,4）,s,v,1,v,3,10,6,3,3,5,3,6,6,v,2,v,4,7,5,t,8,8,4,2,3,2,增流,53,(,s,),（,s,+,4）,（,v,3, - ,2）,（,v,2,+,2）,s,v,1,v,3,10,6,3,3,5,3,6,6,v,2,v,4,7,5,t,8,8,4,2,3,2,增流,s,v,1,v,3,10,7,3,3,5,4,6,6,v,2,v,4,7,5,t,8,8,4,2,3,1,54,三、最小费用最大流,一批货物要从工厂运至车站，可以有多条线路进行选择，在不同的线路上每吨货物的运费不同，且每条线路的运输能力有限。怎样运输才能使费用最少?,用结点,s,代表工厂，,t,代表车站，线路为边，线路的交点为网络的结点，每条边都有两个权：容量,c,和单位费用,a,，于是构成网络流图,N,，问题变成求,N,的最小费用流。,55,一个旅行社接待的一批客人第二天要从甲地飞往乙地，怎样安排才能使旅费最省？,这也是一个最小费用流问题，网络的结点是甲乙两地之间的各个机场，边表示第二天的各个航班，其容量是该航班有效座位数，而费用则是该航班的机票费。,56,设有一个网络,N,(,V,E,)，,V,=,s,a,b,c,t,，,E,中的每条边(,i,j,)对应一个容量,c,ij,，输送单位流量所需费用为,a,ij,。如有一个运输方案（可行流），流量为,f,ij,，w是要求从s到t的流量。于是最小费流（最小费用最大流）问题可以描述如下：,约束条件,57,确定最小费最大流的过程实际上是一个多次迭代的过程。基本思想是：从零流为初始可行流开始，在每次迭代过程中对每条边赋予与c(i,j)（容量）、a(i,j)（单位流量运输费用）、f(i,j)（现有流的流量）有关的权数(i,j)，形成一个有向赋权图。再用求最短距离路径的方法确定由发点s至收点t的费用最小的可增流路，沿着该路增加流量，得到相应的新流。经过多次迭代，直至达到最大流为止。,58,最小费用流算法,把费用看做是该边的长度，则寻找一条从,s,到,t,的最短的增流路，它的费用增长的也就最小。如果最后的流值达到,w,，这时的费用一般应是最小。,1. 初始流分布,f,0,使每条边,e,都为,f,(,e,)=0,亦即,w,0,=0.,2. 在当前可行流分布下修改各边(,i,j,)的费用,a,ij,*,59,构造权的方法如下：,对任意边（i,j），根据现有的流f，该边上的流量可能增加，也可能减少。因此，每条边赋予向前费用权,+,(i,j)与向后费用权,-,(i,j）,：,60,对于赋权后的有向图，如把权(i,j)看作长度，即可确定s到t 的费用最小的非饱和路，等价于从s到t 的最短路。确定了可增流路后，就可确定该路的最大可增流量。因此需对每一条边确定一个向前可增流量,+,(i,j)与向后可增流量,-,(i,j) ：,61,因此，确定最小费用最大流的具体算法如下：,(1)从零流开始，令f0。,(2)赋权,62,(3)确定一条从s到t的最短路,P(s,t)(,s,i,1,)，(i,1,i,2,)，(i,k,t),若P(s，t)的长度为，表明已得到最小费用最大流，则停止；否则转向(4)。,(4)确定沿着该路P(s，t)的最大可增流量,min(s,i,1,),(i,1,i,2,),，(i,k,t),其中根据边的取向决定取,或,。,63,(5)生成新的流,若f(i,j)已为最小费用最大流，则停止；否则转向(2)。,64,