6图与网络1讲诉.ppt

2、称满足下列条件的流为可行流： （1）容量条件：对于每一个弧（vi ,vj）∈A 有 0 ≤ fij ≤ cij 。 （2）平衡条件： 对于发点vs，有 对于收点vt ，有 对于中间点，有 可行流中 fij＝cij 的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0 的弧为非零流弧，fij＝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) 图中 为零流弧，其余为非饱和弧。 3、容量网络G =（V，A，C），vs为始点，vt为终点。如果把V分成两个非空集合 使 ，则所有始点属于V，而终点属于 的弧的集合，称为 由V决定的割 ,记作 。 割 中所有弧的容量之和，称为这个 割 的容量，记为 。 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 4、容量网络G，若 为网络中从vs到vt的一条链，给 定向为从vs到vt， 上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。 f 是一个可行流，如果满足： 则称 为从vs到vt 的关于f 的一条增广链。 即 中的每一条弧都是非饱和弧 即 中的每一条弧都是非零流弧 推论 可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。 定理2： 在网络中 的最大流等于它的最小割的容量，即： 证明 参见教材（163页） 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 是一个增广链 显然图中增广链不止一条 （二）、 求最大流的标号法 标号过程： 1．给始发点vs 标号（0，+∞）。 2．取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理： （1）如果边 ，且 ，那么给vj 标号 ，其中： （2）如果边 ，且 ，那么给vj 标号 ，其中： 3．重复步骤2，直到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) (3 ,0) (5 ,3) (2 ,1) （0，+∞） （v1, 1） （ vs , 4） （v2 ，1） （v2，1） ( v3 ，1) (1 ,0) v2 v1 v4 v3 vs vt (3 , 3) (5 , 2) (1 , 0) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,2) (1 ,0) v2 v1 v4 v3 vs vt (3 , 3) (5 , 2) (1 , 0) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,2) （0，+∞） （ vs , 3） 最小截集 最小截量为：3+2=5 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5