网络的最大流.ppt

§5 网络的最大流 一??? 引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统的最大流问题是图与网络流理论中的最优化问题，它对于解决生产实际问题起着十分重要的作用。 §5 网络的最大流 §5 网络的最大流 二 基本概念 定义 设一个加权有向图D(V,A),在V中指定一个发点s和一个收点t,其他的点叫做中间点。对于D中的弧(vi,vj)∈A,都有一个权 cij 叫做弧的容量。这样的图D称做一个网络系统，简称网络，记做 D(V，A，C)。 网络D上的流，是指加在弧集合A上的一组负载量,记作f(vi,vj),或fij. 若网络上所有的fij=0,这个流称为零流。 §5 网络的最大流 §5 网络的最大流 网络系统上流的特点： (1)发点的总流出量和收点的总流入量必相等； (2)每一个中间点的净流量=0(流入量-流出量=0) ； (3)每一条弧上的流量不能超过它的最大通过能力（即容量）。 §5 网络的最大流 定义 网络上的一个流 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)叫做这个可行流的流量。 §5 网络的最大流 §5 网络的最大流 任意一个网络上的可行流总是存在的。比如零流v(f)=0,就满足可行流的条件。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。 设流f={fij}是网络D上的一个可行流。我们把D中fij=cij的弧叫做饱和弧;fijcij的弧叫做非饱和弧;fij0的弧为非零流弧，fij=0的弧叫做零流弧。 将割 中所有弧的容量之和称作割的容量，记作 ,即 §5 网络的最大流 §5 网络的最大流 增广链，如果链μ满足以下条件： 1．在弧（vi,vj）∈μ+上，有0=fijcij ,即μ+中的每一条弧是非饱和弧。 2．在弧（vi,vj）∈μ-上，有0fij=cij ,即μ-中的每一条弧是非零流弧。 §5 网络的最大流 定理1 网络中的一个可行流f*是最大流当且仅当不存在关于f*的增广链。 定理2 在网络中 s→t 的最大流量等于最小割的容量。 定理1实际上提供了寻求网络系统最大流的方法：如果网络D中有一个可行流f，只要判断网络是否存在关于可行流f的增广链 。如果没有增广链，那么f一定是最大流。如有增广链，可以按照定理2，不断增大可行流f的流量，最终可以得到一个最大流。 §5 网络的最大流 三．标号法 从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。 用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。 §5 网络的最大流 1．? 标号过程 在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）。或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的。以便找出增广链。第二个标号是为了用来确定增广链上的调整量θ。 标号过程开始，先给vs标号（0，+∞）。这时，vs是标号未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj： §5 网络的最大流 1）如果在弧（vi,vj）上，fijcij,那么给vj标号（vi,l(vj)）.其中l(vj)=min[l(vi),cij-fij].这时，vj成为标号未检查的点。 2）如果在弧（vj,vi）上，fij0,那么给vj标号（-vi, l(vj)）.其中l(vj)=min[l(vi),cij-fij].这时，vj成为标号未检查点。 于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链μ，转入下一步调整过程。 §5 网络的最大流 2.调整过程 首先按照vt和其他的点的第一个标号，反向追踪，找出增广链μ。例如，令vt的第一个标号是vk，则弧（vk,