網络流基础及应用.docVIP

网络流基础及应用 一引例 运输方案 下图为联结产品产地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吨物资运输量，改进的方案如下： 改进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(中间点流量守恒，即平衡条件) 这时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=13 2、定理：对于已知的网络流，从源点Z到汇点Z’的流量ω的最大值小于等于任何一个割切的容量，即Max ω=Min C(S,S’)。 证明： 当V为网络流图的任一中间点时，根据平衡条件，恒有 ∑fij-∑fji=0 ⑴ 当i=Z时，∑fZj=ω ⑵ 设(S,S’)为一任一个切，则有 ∑(fij-fji)= ω 注： ∵i∈S，Z’(not∈)S，Z∈S 当i≠Z时，由⑴式得0 当i=Z时，由⑵式得ω 又因为S∪S’=V 所以∑(fij-fji)= ∑(fij-fji)+ ∑(fij-fji)=ω ⑶ ⑶式中∑(fij-fji)的两个下标都是对S的全体求和，其展开式中任意一项fpq都一一对应一项-fpq，所以∑(fij-fji)=0 即由⑶式得∑(fij-fji) =ω