网络流基础及应用

《网络流基础及应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络流基础及应用网络流基础及应用一.引例运输方案2284371V1V2V5V3V4V644图1下图为联结产品产地V1和销地V6的交通网，每一边(Vi,Vj)代表从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边旁的数字表示这条运输线的最大通行能力(简称容量)。产品经过交通网从V1输送到V6，现要求制定一个输送方案，使V1运到V6的产品数量最多。下面是一个可行的输送方案，边旁的数字为该运输线的实际运输量(单位：吨)。2230203021V1V2V5V3V4V6图2该运输方案表示：2吨产品沿有向路P1(V1,V2,V4,V6)运到销地；1吨产

2、品沿有向路P2(V1,V2,V5,V6)运到销地；2吨产品沿有向路P3(V1,V3,V5,V6)运到销地。总共有5吨从V1运到V6。运输方案的可行必须满足以下三个条件：⑴实际运输量不能是负的；⑵每条边的实际运输量不能大于该边的容量；⑶除了起点V1和终点V6，对其他顶点(中间点)来说，不能囤积物资，即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。运输方案的改进：根据这个运输网，是否可增大运输量？3V3V1224103121V2V5V44V6图3改进1：我们找到一条有向路P4(V1,V2,V3,V4,V6)可再增加1吨物资运输量，改进的

3、方案如下：第16页共16页网络流基础及应用改进2：有向路P5(V1,V3,V4,V6)还可增加1吨运输量：4V3V1234103221V2V5V44V6图4改进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(想一想为什么可以这样做)。5V3V1244003231V2V5V44V6图5至此，再找不到可“

4、改进”的有向路了，所以，该交通网的最大运输量为8吨。通过上述实例分析，包含了流量因素的问题，是一类特殊的图。引例给出的交通网其具体的物理模型是多种多样的。比如网络的有向边可以表示为城市之间的公路、电信网之间的通讯线路、天然气站之间的输气管道等；边的容量则可以表示为允许通过的物资数量、汽车数量、速率或最大信号流量等。这一类特殊的图，称为网络流图。网络流图中需要解决的基本问题是求最大流问题。二.网络流图与最大流类似于上述交通网，可构造下列称为网络流图的模型。1、网络流图的构造设G=(V,E)为一简单有向图。当且仅当只有一个入度为0(d(z)=0)

5、的点，在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(中间点流量守恒，即平衡条件)这时D=(V,E,C)中的流称为D的可行流f。第16页共16页网络流基础及应用3、关于D的可行流①当所有fij=0

6、，称为零流，零流一定是可行流。②对于源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’)表示。下图

7、用虚线划去的表示一个割切，其中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)=ω注：∵

8、i∈S，Z’(not∈)S，Z∈S当i≠Z时，由⑴式得0当i=Z时，由⑵式得ω第16页共16页网络流基础及应用又因为S∪S’=V所以∑(fij-fji)=∑(fij