Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第十三章,网络最大流,11/19/2024,1,第一页，共27页。,第十三章 网络最大流10/4/20231第一页，共27页,13.1 网络的流与割,11/19/2024,2,第二页，共27页。,13.1 网络的流与割10/4/20232第二页，共27,网络的定义,定义12.1.1：设有向图N具有两个非空的顶点子集X、Y，XY=,，并且在弧集A上定义了一个非负整数值的函数C，则称N为一个网络，记为N(X,Y,C)，,其中：,1)X和Y中的顶点分别称为源和汇，其它顶点称为中间点。,2),函数C：A,N,(,N,为非负整数集)，称为此网络的容量函数，它在一条弧上的值称为该弧的容量。记为C()或C(i,j)，这里=(i,j)A。,11/19/2024,3,第三页，共27页。,网络的定义定义12.1.1：设有向图N具有两个非空的顶点子集,一个网络,下面是一个网络：,x,y,v,1,v,5,v,6,v,4,v,3,v,2,4,6,5,2,4,4,7,1,4,2,1,8,其中：,x,和,y,分别为源和汇；,v,1,v,6,为中间点；各弧上标记的整数是该弧的容量函数值，例如C(x,v,1,)=4。,11/19/2024,4,第四页，共27页。,一个网络下面是一个网络：xyv1v5v6v4v3v24652,网络中的一个函数,f,设N是有一个源x和一个汇y的网络，,f,是定义在弧集A(N)上的一个整数值函数，即,f,：A,N,(,N,为整数集),，V,1,、V,2,是V,(N)的子集。记,(V,1,V,2,)=(u,v)A(N)|uV,1,vV,2,f,(V,1,V,2,)=,f,(,)，这里,(V,1,V,2,)。,特别，当V,1,=i 时，将,f,(V,1,V,2,)记为,f,(i,V,2,)。,函数,f,可以看作网络中弧上的实际流量。它们还需要满足一定的条件才会在网络上形成“流”。,11/19/2024,5,第五页，共27页。,网络中的一个函数 f设N是有一个源x和一个汇y的网络，f是定,流的概念,定义13.1.2：设,N(x,y,C)是一个网络，,f,是定义在,A(N,)上的一个整数值的函数。若,f,满足：,对,A(N,),，0,f,()C();(13.1),对,中间点i有,f,(i,V)=,f,(V,i);(13.2),则称,f,是网络N的一个流，,f,(x,V)称为流,f,的值，记为,f,xy,。其中：,式(13.1)称为,约束条件,，即流量不超过容量。,式(13.2)称为,守恒条件,，即任何中间点的流入等于流出。,11/19/2024,6,第六页，共27页。,流的概念定义13.1.2：设N(x,y,C)是一个网络,流的一个例子,上图给出了一个网络及其流。,弧上的第一个数字是容量，第二个是流。,可以验证该网络满足约束条件和守恒条件。,该网络的流,f,的值,f,xy,=,f,(x,V),=4+4=8。,x,v,1,v,2,v,4,v,3,y,8,4,7,4,5,1,2,0,9,5,9,3,6,1,5,4,10,4,11/19/2024,7,第七页，共27页。,流的一个例子上图给出了一个网络及其流。xv1v2v4v3y8,最大流,：设,f,是网络的一个流。如果不存在N的流,f,，使得,f,xy,f,xy,，则称,f,为最大流，记为,f,max,。,运输网络的一个主要问题就是找出它的一个最大流,f,max,，最大流表示在尽量满足条件的情况下，网络中各条干线上的最大运输量。,为了解决网络最大流的问题，需要引进割的概念。,11/19/2024,8,第八页，共27页。,最大流：设 f 是网络的一个流。如果不存在N的流 f，使得,割,定义13.1.4：设N=(x,y,C)为一个网络，V,1,V(N),x,V,1,y,V,1,=,V(N),V,1,，,称(V,1,V,1,)为N的一个割，记为,K=(V,1,V,1,)=(u,v)A(N)|uV,1,v,V,1,。,由割的定义可知，网络N的一个割即是分离源和汇的弧之集合。记,C,(K)=,K,C,()。,称,C,(K)为割K的容量。,11/19/2024,9,第九页，共27页。,割定义13.1.4：设N=(x,y,C)为一个网络，,割的例子,x,v,1,v,2,v,4,v,3,y,8,4,7,4,5,1,2,0,9,5,9,3,6,1,5,4,10,4,在网络中，若取V,1,=x,v,1,v,2,V,1,=y,v,3,v,4,，则K,1,=v,1,v,3,，v,2,v,4,。,这个割的容量为,C(K,1,)=C(v,1,v,3,)+C(v,2,v,4,)=18.,在网络中，取V,1,=x,V,1,=y,v,1,v,2,v,3,v,4,，则K,2,=xv,1,，xv,2,。,这个割的容量为,C(K,2,)=C(xv,1,)+C(xv,2,)=15.,在网络中，取V,1,=x,v,1,V,1,=y,v,2,v,3,v,4,，则K,3,=xv,2,，v,1,v,2，,v,1,v,3,。,这个割的容量为,C(K,3,)=C(xv,2,)+C(v,1,v,2,)+C(v,1,v,3,)=21.,在网络中，取V,1,=x,v,1,v,2,v,3,V,1,=y,v,4,，则K,4,=v,3,y,，,v,2,v,4,。,这个割的容量为,C(K,4,)=C(v,2,v,4,)+C(v,3,y)=14.,由此可知网络可有多个割，且容量可以不同。,11/19/2024,10,第十页，共27页。,割的例子xv1v2v4v3y8,47,45,12,09,59,最小割,定义13.1.5：设K是网络N的一个割，若不存在N的其它割K，使得,C(K)C(K),则称K为N的最小割，记为K,min,。,在,上例,中K,4,是N的最小割，其容量为14。,割其实是网络上的咽喉要道，割的容量自然会制约着网络上的流。实际上最小割的容量就是网络的最大流。,11/19/2024,11,第十一页，共27页。,最小割定义13.1.5：设K是网络N的一个割，若不存在N的其,割与流,定理13.1.1：设网络N的流,f,的值为,f,xy,，(V,1,V,1,)是N的割.于是,f,xy,=,f,(V,1,V,1,),f,(,V,1,V,1,)。,证明：由流的定义：,f,(x,V)=,f,xy,；,f,(V,x,)=,0；,f,(v,V),f,(V,v)=0,vx,y,(守恒条件,)；,于是对任意的SV，xS，yS，有,f,xy,=,v,S,f,(v,V),f,(V,v)，,或者,f,xy,=,f,(S,V),f,(V,S)。,将V=SS代入可得,f,xy,=,f,(S,S),f,(,S,S)。,？,由S的任意性可知定理成立。,将V=,SS代入该式，并注意到SS=：,f,xy,=,f,(S,V,),f,(V,S)=,f,(S,SS),f,(,SS,S),而,f,(S,SS)=,f,(S,S)+,f,(S,S),f,(S,SS),=,f,(S,S)+,f,(S,S)，,f,(S,S,S)=,f,(S,S)+,f,(,S,S),f,(S,S,S),=,f,(S,S)+,f,(,S,S)。,即,f,xy,=,f,(S,S),f,(,S,S)。,11/19/2024,12,第十二页，共27页。,割与流定理13.1.1：设网络N的流 f 的值为fxy，(V,流值不超过最小割的容量,定理13.1.1说明，网络中任何从源到汇的流的值等于任何割中的流的净值，即割的正向流(从V,1,到,V,1,)与逆向流,(从,V,1,到,V,1,)的差值。,推论13.1.1：设,(V,1,V,1,)是网络的任意一个割，于是,f,xy,C(V,1,V,1,)。,证明：由定理13.1.1知,f,xy,=,f,(,V,1,V,1,)-,f,(,V,1,V,1,),即,f,xy,f,(V,1,V,1,),由约束条件知,f,(V,1,V,1,),C(V,1,V,1,)，故结论成立。,显然对于任何网络，均有,f,max,C(K,min,)。,11/19/2024,13,第十三页，共27页。,流值不超过最小割的容量定理13.1.1说明，网络中任何从源到,13.2 最大流与最小割定理,11/19/2024,14,第十四页，共27页。,13.2 最大流与最小割定理10/4/202314第十四,最大流最小割定理,定理13.2.1(最大流最小割定理)：任何网络中最大流的值等于最小割的容量，即,f,max,=C(K,min,)。,证明：设f是最大流，按照如下的方法定义N的顶点子集V,1,：,xV,1,；,若,v,i,V,1,，且,f,(v,i,v,j,)C(v,i,v,j,)，则v,j,V,1,；,若,v,i,V,1,，且,f,(v,j,v,i,)0，则v,j,V,1,。,由,V,1,的定义可以证明，y,V,1,。,？,因此(V,1,V,1,)是割。其中：,V,1,=V-V,1,若yV,1,，则按V,1,的定义，将有从x到y的“链”,(不一定是有向链)。设=xv,1,v,m,y，其中，若v,i,v,i+1,A(N)，则称为前向弧；,若v,i+1,v,i,A(N)，则称为后向弧；将,中前向弧的集合记为,+,，后向弧的集合记为,。于是有对,+,中的和,中的均有：,f,()C()，,f,()0。取,=min(minC(),f,()|,+,min,f,()|,显然0，现将,f,修改为,f,：,f,()=,if,+,then,f,()+,else,if,then,f,(),else,f,(),不难验证,f,仍是N的一个流，但是,f,xy,=f,xy,+,，这与,f,是最大流矛盾。故y,V,1,。,11/19/2024,15,第十五页，共27页。,最大流最小割定理定理13.2.1(最大流最小割定理)：任何网,最大流最小割定理,证明：构造(V,1,V,1,)是N的一个割。,按V,1,的定义，若(v,i,v,j,),(V,1,V,1,)，则,f,(v,i,v,j,)=C(v,i,v,j,)，,(由V,1,的定义(2)和约束条件）,若(v,j,v,i,),(V,1,V,1,)，则,f,(v,j,v,i,)=0，,(由V,1,的定义(3)）,否则v,j,将在V,1,中。于是有,f,(V,1,V,1,)=C(V,1,V,1,)，,f,(V,1,V,1,)=0。,从而，由定理13.1.1,有,f,xy,=C(V,1,V,1,)，,此时必有,f,xy,=,f,max,=C(K,min,)=C(V,1,V,1,)。证毕。,11/19/2024,16,第十六页，共27页。,最大流最小割定理证明：构造(V1,V1)是N的一个割,求最大流方法的基本思想,定理13.2.1的证明是构造性的因而也给出了求最大流的方法；即任取一个流，然后设法逐步增大流值，直至不能再增大为止。具体做法是：,按照定理中的定义寻找从x到y的“链”，使其所有前向弧满足,f,()C()(称为未饱和弧)，后向弧满足,f,()0。那么就可以使该“链”上的前向弧增加，后向弧减少，从而使流值增加了。这种“链”称为可增广路。,反复这样做，直到网络上不再有可增广路。,11/19/2024,17,第十七页，共27页。,求最大流方法的基本思想定理13.2.1的证明是构造性的因而也,1,有 f xy=C(V1,V1)，,于是 fxy=f(V1,V1)f(V1,V1)。,C(K)=K C()。,这时，网络中不再存在可增广路。,网络是由顶点和弧构成的，一个顶点可由顶点编号、指向前向弧链的指针、指向后向弧链的指针以及标记位构成。,如果不存在N的流 f