网络流基础及应用

网络流基础及应用第1页共16页网络流基础及应用一.引例运输方案下图为联结产品产地V1和销地V6的交通网，每一边(Vi,Vj)代表从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边旁的数字表示这条运输线的最大通行能力(简称容量)。产品经过交通网从V1输送到V6，现要求制定一个输送方案，使V1运到V6的产品数量最多。下面是一个可行的输送方案，边旁的数字为该运输线的实际运输量(单位：吨)。该运输方案表示：2吨产品沿有向路P1(V1,V2,V4,V6)运到销地；1吨产品沿有向路P2(V1,V2,V5,V6)运到销地；2吨产品沿有向路P3(V1,V3,V5,V6)运到销地。总共有5吨从V1运到V6。运输方案的可行必须满足以下三个条件：⑴实际运输量不能是负的；⑵每条边的实际运输量不能大于该边的容量；⑶除了起点V1和终点V6，对其他顶点(中间点)来说，不能囤积物资，即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。运输方案的改进：根据这个运输网，是否可增大运输量？改进1：我们找到一条有向路P4(V1,V2,V3,V4,V6)可再增加1吨物资运输量，改进的方案如下：2284371V1V2V5V3V4V644图12230203021V1V2V5V3V4V6图23V3V1224103121V2V5V43V3V1224103121V2V5V4V6图34V6图3网络流基础及应用第2页共16页改进2：有向路P5(V1,V3,V4,V6)还可增加1吨运输量：改进3：观察有向路P6(V1,V3,V2,V4,V6)中，将正方向的边(V1,V3)、(V2,V4)、(V4,V6)都可增加运输量，而反方向的边(V3,V2)的运输量为1，现将反向边(V3,V2)的运量调到正向边(V2,V4)上去完成，这样有向路P6(V1,V3,V2,V4,V6)的运量可增加1(想一想为什么可以这样做)。至此，再找不到可“改进”的有向路了，所以，该交通网的最大运输量为8吨。通过上述实例分析，包含了流量因素的问题，是一类特殊的图。引例给出的交通网其具体的物理模型是多种多样的。比如网络的有向边可以表示为城市之间的公路、电信网之间的通讯线路、天然气站之间的输气管道等；边的容量则可以表示为允许通过的物资数量、汽车数量、速率或最大信号流量等。这一类特殊的图，称为网络流图。网络流图中需要解决的基本问题是求最大流问题。二.网络流图与最大流类似于上述交通网，可构造下列称为网络流图的模型。1、网络流图的构造设G=(V,E)为一简单有向图。当且仅当只有一个入度为0(d(z)=0)的点，在V中指定该顶点为源点(记为Z)，当且仅当有一个顶点出度为0的顶点，为汇点(记为Z’)，对于每一条边(Vi,Vj)∈E，赋予一个非负数Cij=0，叫做该边的容量。记为D=(V,E,C)(图示参见引例)2、网络的流对于网络流图D=(V,E,C)的每一条边(Vi,Vj)给定一个非负数fij，且满足下列条件：①0=fij=Cij(容量限止条件)②除源点和汇点外，其余顶点Vi恒有∑fij=∑fki(中间点流量守恒，即平衡条件)5V3V1244003231V2V5V43V3V1224103121V2V5V4V6图34V6图54V3V1234103221V2V5V43V3V1224103121V2V5V4V6图34V6图4网络流基础及应用第3页共16页这时D=(V,E,C)中的流称为D的可行流f。3、关于D的可行流①当所有fij=0，称为零流，零流一定是可行流。②对于源Z和汇Z’有∑fZj=∑fjZ’=ω数ω叫做网络流的流量。③当fij=Cij时，称边(Vi,Vj)饱和，表示流f对于该边饱和。④ω达到最大值时的流f，称为D=(V,E,C)的最大流。三.求最大流的理论基础1、割切概念——某些边的集合⑴设D=(V,E,C)是已知的网络流图，假定S是V的一个子集，且S满足①Z∈S②Z’(not∈)S且令S’为S的补集，这样把顶点集V分成S和S’两个部分，其中Z∈S,Z’∈S’对于一个端点在S，而另一个端点在S’的所有边的集合，叫做网络流图D的一个割切，用(S,S’)表示。下图用虚线划去的表示一个割切，其中S={Z,b,c,d}，S’={a,Z’}。图片⑵割切容量C(S,S’)：在割切(S,S’)中，把从S到S’的边容量和叫做这割切的容量。上边割切容量C(S,S’)=CZa+Cba+CbZ’+CdZ’=4+3+2+4=132、定理：对于已知的网络流，从源点Z到汇点Z’的流量ω的最大值小于等于任何一个割切的容量，即Maxω=MinC(S,S’)。证明：当Vi为网络流图的任一中间点时，根据平衡条件，恒有∑fij-∑fji=0⑴当i=Z时，∑fZj=ω⑵设(S,S’)为一任一个切，则有∑(fij-fji)=ω注：∵i∈S，Z’(not∈)S，Z∈S当i≠Z时，由⑴式得0网络流基础及应用第4页共16页当i=Z时，由⑵式得ω又因为S∪S’=V所以∑(fij-fji)=∑(fij-fji)+∑(fij-fji)=ω⑶⑶式中∑(fij-fji)的两个下标都是对S的全体求和，其展开式中任意一项fpq都一一对应一项-fpq，所以∑(fij-fji)=0即由⑶式得∑(fij-fji)=ω⑷再由于0=fijCij，所以fij-fji=fij=Cij由⑷式ω=∑(fij-fji)=∑Cij=C(S,S’)故有Maxω=MinC(S,S’)3、最大流量最小割切定理(Ford-Fulkerson定理)在一个给定的网络流图上，流的极大值等于割切容量的最小值，即Maxω=MinC(S,S’)(下面的证明是构造性的，可以从中引出求最大流的算法思想)证明：(求证思路：由于已知Maxω=MinC(S,S’)是不能进一步增加流量，直到使Maxω=MinC(S,S’))在网络流图D=(V,E,C)中，定义从源点Z到汇点Z’的道路：设Z=V0,V1,...,Vn-1,Vn=Z’为D上的顶点序列，对于i=0,1,...,n-1，恒有(Vi,Vi+1)或(Vi+1,Vi)边是D的一条边。则称V0,V1,...,Vn是一条从Z到Z’的道路。由于D是有向图，道路上边的方向与道路方向一致的边称为前向边P+，反之称为后向边P-。道路上边的饱和：前向边若fij=Cij，后向边若fij=0,称边(Vi,Vj)为关于该道路上的饱和边。若从Z到Z’的道路上所有的边均不饱和，即对于P+若fijCij，P-有fij0，则称这条路为可增广道路。修改可增广道路上每条边的流量，同时保持网络流的可行性，达到流量的增加，其增量的确定方法如下：令δij={取δ=Min(δij)，为增量。就是对可增广道路P的每一条前向边流量增加δ，每一条后向边流量减少δ，从而使得整个网络流的流量获得增加(这是显而易见的)下面论证Maxω=MinC(S,S’)设网络流图D的流量f达到极大，我们构造一个割切(S,S’)如下①Z∈S②若x∈S，且fxyCxy，则y∈S若x∈S，且fyx0，则y∈S显然Z’∈S’(Z’的出度d(Z’)=0)，Cij-fijP+fijP-若Z’∈S，则有一条从Z到Z’的道路，Z=V0,V1,...,Vk=Z’，这条道路上所有的边均不饱和，因而是条可增广道路，这和f是最大流的假设矛盾。Z’Vn-1Vj+1VjViZV1V2Vi+1网络流基础及应用第5页共16页所以(S,S’)是一个割切。按照子集S的定义，若x∈S，y∈S’，则fxy=Cxy若y∈S’，x∈S，则fyx=0所以ω=∑(fxy-fyx)=∑fxy=∑C(S,S’)即Maxω=MinC(S,S’)通过以上论证，可知①当D中找不到可增广道路时，此时的流为最大流；②当D中的流最大时，一定存在容量最小的割切(S,S’)四.求网络最大流的算法根据上述最大流最小割切定理及其论证，我们不难得出下面重要结论：设f是网络流图D的一个流，如果存在从源点Z到汇点Z’的关于f可增广道路P，那么f一定是最大流。至此，求最大流的基本思路为：㈠标号法(Ford-Fulkerson算法)标号法分为两个过程，一是标号过程，通过标号过程找到一条可增广道路或无法找到可增广道路；二是增广过程，沿可增广道路增加网络流量。从一个可行流出发(若网络中没有初始流，则可以设f是零流)1、标号过程：用Vs表示源点，Vt表示汇点。在此过程中，网络中的顶点或者是已标号点(又分为已检查和未检查两种)，或者是未标号点。每个标号点的标号包含两部分。第一个标号指明它的标号是从哪个顶点得到的，以便找出可改进量，第二个标号是为确定可改进量δ而设的。标号过程开始，先给源点Vs标上(0,+∞)，这时Vs是已标号而未检查的点，其余都是未标号点。一般地，取一个已标号而未检查的点Vi，对一切未标号点Vj：⑴若存在弧(Vi,Vj)且fijCij，则给Vj标号(Vi,L(Vj))，其中L(Vj)=Min(L(Vi),Cij-fij)；⑵若存在弧(Vj,Vi)且fji0，则给Vj标号(-Vi,L(Vj))，其中L(Vj)=Min(L(Vi),fji),至此，Vj成为已标号而未检查点。在Vi的全部相邻顶点都已标号后，Vi成为标号而已检查的顶点。重复上述步骤，一旦Vt被标号，表明得到一条从Vs到Vt的可增广道路P，转入增广过程。若所有标号点都已检查过使得标号过程无法继续时，则算法结束，这是的可行流即为最大流。取所有fij=0为第一个流F现有流存在可增道路广道路将F改为更大的流F为最大流求最大流的基本思路网络流基础及应用第6页共16页2、增广过程所得可增广道路P上的顶点都已标号。因此多用“倒向追踪”的方法，从Vt开始，利用标号点的第一个标号可得P上一条边，并以Vt的第二个标号l(Vt)(即可增广流量δ)作为改进量，增大P上的流量。具体步骤如下：①取Vt的第一个标号Vk（或-Vk），则弧（Vk,Vt）(或相应的弧（Vt,Vk）)是P上的弧，接下来再根据Vk的第一个标号Vi（或-Vi），再找到P上的弧(Vi,Vk)(或(Vk,Vi))……，直到找到Vs为止，这是所有被找出的弧就构成了可增广道路P。根据第一个标号的正负号，可知其方向是前向还是后向。令改进量δ=L(Vt)，对弧上的流量fij作改进：②去掉所有的标号，对新的流F’=(fij’)重新进入标号过程。求最大流标号发的描述⑴数据结构Constmaxn=网络顶点数Typenode=record{可增广道路的顶点类型}l,p:integer；{第一标号，检查标号}end;arc=record{网络边类型}c,f:integer;{容量，流量}end;gtype=array[0..maxn,0..maxn]ofarc；{网矩阵}ltype=array[0..maxn]ofnode;{可增广道路}varlt:ltype;{可增广道路}g:gtype;{网络}n,s,t:integer;{顶点数，源点，汇点}⑵主要算法①初始化网络，可增广道路procedureread-graph；varI,j:integer;beginreadln(n);{顶点数}fillchar(g,sizeof(g),0);{初始化网络}fillchar(lt,sizeof(lt),0);{初始化可增广道路}fori:=1tondoforj:=1tondoread(g[I,j].c);end;②寻找已标号而来检查的顶点序号Fij’=fij+δ(Vi,Vj)为p+fij-δ(Vi,Vj)为p-网络流基础及应用第7页共16页functioncheck:integer;vari:integer;begini:=1;while(i=n)andnot((lt[i].l0)and(lt[i].p=0))doinc(i);ifinthencheck:=0{顶点不存在}elsecheck:=i;end;③标号过程，并返回是否找到可增广道路及改进量afunctionford(vara:integer):boolean;{无增广道路返回true}varI,j,m,x:in