[管理学]网络最大流.ppt

最小截集： 容量最小截集的称为网络G的最小截集。 最大流-最小截集定理： 在任一个网络D中，从vs到vt的最大流的流量等于分离的最小截集的容量。 * 四、 最大流问题 （一）、 基本概念 1、设一个赋权有向图D=（V, E）,在V中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D中的每一个弧（vi , vj）∈E ,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做 D=（V，E，C）。 网络D上的流，是指定义在弧集合E上的一个函数 其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量。 2、称满足下列条件的流为可行流： （1）容量条件：对于每一个弧（vi ,vj）∈E 有 0 ≤ fij ≤ cij 。 （2）平衡条件： 对于发点vs，有 对于收点vt ，有 对于中间点，有 W为网络流的总流量。 可行流总是存在的，例如f={0}就是流量为0的可行流。最大流问题就是在流量网络中，寻找流量最大的可行流。 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 图中 为零流弧，其余为非饱和弧。 可行流中 fij＝cij 的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0 的弧为非零流弧，fij＝0 的弧叫做零流弧。 3、容量网络G，若 为网络中从vs到vt的一条链，给 定向为从vs到vt， 上的弧,凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。 f 是一个可行流，如果满足： 则称 为从vs到vt 的关于f 的一条可增广链。 推论 可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。 即 中的每一条弧都是非饱和弧 即 中的每一条弧都是非零流弧 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 是一个增广链 显然图中增广链不止一条 4、容量网络D =（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合 使 ，则所有始点属于S，而终点属于 的弧的集合，称为由S决定的截集,记作 。截集 中所有弧的容量之和，称为这个截集的容量，记为 。 vs v1 v2 v4 v3 vt 3 7 4 5 5 6 3 7 8 S 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 设 ， 则截集为 容量为24 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 设 ， 则截集为 容量为20 （二）、 求最大流的标号法 标号过程： 1． 给发点vs 标号（0，+∞）。 2． 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理： （1）如果边 ，且 ，那么给vj 标号 ，其中： （2）如果边 ，且 ，那么给vj 标号 ，其中： 3．重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。 调整过程 按点的第一个标号寻找一条增广链 对vt,,按逆方向进行调整，下式中的 1．令 2．去掉所有标号，回到第一步，对可行流重新标号。 求下图所示网络中的最大流，弧旁数为 (1 ,1) v2 v1 v4 v3 vs vt (3 , 3) (5 , 1) (1 , 1) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,1) (1 ,1) v2 v1 v4 v3 vs vt (3 , 3) (5 , 1) (1 , 1) (4 ,3) (2 , 2)