网络最大流

null第四节 最大流问题第四节 最大流问题网络流的基本概念 求解网络最大流的基本原理 寻找网络最大流的标号法 确定网络中最大流的方法null 一  引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。4 .网络系统的最大流问题4 .网络系统的最大流问题图8.19vtv3v2v1v4vs1735108611453Cij图8.19是一个网络。每一个弧旁边的权就是对应的容量（最大通过能力）。要求指定一个运输，使得从vs 到vt 的货运量最大，这是寻求网络系统的最大流问题。null二 基本概念 定义8.5 设一个赋权有向图D =（V,A）,在v中指定一个发点vs 和一个收点vt,其他的点叫做中间点。对于D中的每一个弧（vi,vj）∈A,都有一个权 cij 叫做弧的容量。我们把这样的图 D 叫做一个网络系统，简称网络，记做D =（V，A，C）。 网络D上的流，是指定义在弧集合A上的一个函数f={f(vi,vj)}={fij } f(vi,vj)=fij 叫做弧在(vi,vj)上的流量。nullv3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fij图8.20网络上的一个流（运输方案） 每一个弧上的流量fij 就是运输量 例如fs1=5,fs2=3,f13=2等等vtnull网络系统上流的特点： (1)发点的总流出量和收点的总流入量必相等； (2)每一个中间点的流入量与流出量的代数和等于零； (3)每一个弧上的流量不能超过它的最大通过能力（即容量）。null 定义8.6 网络上的一个流f叫做可行流，如果f满足以下条件 （1）容量条件：对于每一个弧（vi,vj）∈A,有 0  fij  cij . （2）平衡条件： 对于发点vs ，有∑fsj -∑fjs =v(f) 对于收点vt ，有∑ftj -∑fjt =-v(f) 对于中间点，有∑fij -∑fji =0 其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。null任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。 设流f={fij}是网络D上的一个可行流。我们把D中fij=cij的弧叫做饱和弧，fij0的弧为非零流弧，fij=0的弧叫做零流弧。 设μ是网络D中连接发点νs和收点vt 的一条链。定义链的方向是从vs 到vt ，于是链μ上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做μ+。二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做μ-。在下图（图8.19与8.20合并图）中，(v4,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。在下图（图8.19与8.20合并图）中，(v4,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6,3）（11,6）（4,1）（5,1）（3,2）fij如图，在链（vs,v1,v2,v3,v4,vt)中， μ+={(vs,v1),(v1,v2),(v2,v3),(v4,vt)}, μ-={(v4,v3)}.vtnull 增广链，如果链μ满足以下条件： 1．在弧（vi,vj）∈μ+上，有0≤fij0,那么给vj标号（-vi, l(vj)）.其中l(vj)=min[ l(vi), fij ].这时，vj成为标号未检查点。 于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链μ，转入下一步调整过程。null 2.调整过程 首先按照vt 和其他的点的第一个标号，反向追踪，找出增广链μ。例如，令vt 的第一个标号是vk，则弧（vk,vt ）在μ上。再看vk 的第一个标号，若是vi，则弧(vi,vk )都在μ上。依次类推，直到vs 为止。这时，所找出的弧就成为网络D的一条增广链μ。取调整量θ= l(vt) ,即vt 的第二个标号， 再去掉所有的标号，对新的可行流f’={f’ij},重新进行标号过程，直到找到网络D的最大流为止。 nullV4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1） （1,1） (Cij,fij)Vt图8.21null 例8.8: 求图8.21的网络最大流，弧旁的权数表示（cij,fij）。 解.用标号法。 1.标号过程。 （1）首先给vs 标号（0，+∞） （2）看vs:在弧(vs,v2)上,fs2=cs3=3,不具备标号条件。在弧(vs,v1)上,fs1=10,故给v2标号（-v1, l(v2)）,其中l(v2)=min[l(v1),f21]=min[4,1]=1.null（4）看v2:在弧（v2,v4）上，f24=30, 故给v3标号（-v2，l(v3))， 其(l(v3)=min[l(v2),f32]=min[1,1]=1。 （5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，f3t=10, 给V3 标号Q= f32=3. null选择已标号点V3, V4和V6都能标号, 选择V4, 标 号Q=C34-F34=3-0=3. 选择已标号点V4, V7可标 号, 给V7标号Q=10-3=7.nullV7已标号说明找到了一条增广链, 沿着标号的线 路追踪得到增广链U={(1,2),(3,2),(3,4),(4,7)}, U+= {(1,2), (3,4),(4,7)}, U-={(3,2)}, 增广链的最小值为: Q0=MIN{M,2,3,3,7}=2.null调整增广链上的流量. 弧(1,2), (3,4),(4,7)上的流量加上2, 弧(3,2)上的流量减去2, 其余弧流量不变. null对所得新图, 发点标号M(无穷大), V2不能标号, V3可以标 号, 给V3标号Q=14-10=4. 选择已标号点V3, 给V2标号Q= 5-1=4, V4和V5不能标号, 回朔到V3, 选择V4, 给V4标号, Q=3-2=1, 选择V7,给V7标号Q=10-5=5, 得增广链U={(1,3), (3,4),(4.7)}, 调整量Q0=MIN{M,4,1,5}=1.null对流量进行调整, 增广链上弧的流量加1, 其余不 变.null选V3, 标号Q=14-11=3, 选V6,标号Q=8-7=1,选V4, 标号Q=3-1=2,选V7, 标号Q=10-6=4, 得增广链U= {(1,3),(3,6),(6,4),(4,7)}, 调整量Q0=MIN{3,1,2,4}=1M5(1)3241null对流量进行调整, 对图进行标号, V1,V3,V2得到标 号后, 其余点无法标号.以不存在增广链.网络最大 流V=8+12=20.5(1)