V,∩=pV∪F=,则把从vs指向的弧的全体称为截集。记为(V,V) 即(,V)=(v,")v∈H,"∈V2(v,")∈丹。 截集的截量一一截集中所有容量之和称为该截集的截量。记为 W(V,T)举例说明,不同截集的截量不同。 可以理解,任何可行流的流量vf≤W(sV) 3.最大流最小截量定理: 任一网络D中,最大流的流量=最小截集的截量。 四、求最大流的方法(Ford- Fulkerson标号法) 从以上概念及定理可知,要判断可行流f是否最大流有两种途径: 1)能否找出可行流f的增广链,若能,则f不是最大流,否则f是最 大流。 2)V(们是否等于最小截量,若等,则f是最大流,否则f不是最大流。 标号法的基本思想:从可行流f出发,由V开始,用对D中的每 个顶点进行标号的办法找f的增广链μ。若无,则f为所求的最大流。否则, 在增广链上进行调整。 调整理:=mn{mn(w-fmnf} f+6(v,v,)∈H 调整方法:f=f-0(",")∈ Jfn v:1:)∈ 2步骤 (1)给出初始可行流f(如f=0) (2)给顶点标号,寻找增广链。标号(v,L(v)的第一个标号表示ⅵ点 而来,第二个标号L(表示增广链上中该弧允许的调整量 在标号过程中,每个属于且仅属于下列集合之 V。——已标号未检验点集,V——一已标号已检验的点集,V—一未标 号点集36 Vs Vs = ,Vs Vs = V ，则把从 vs 指向 s v 的弧的全体称为截集。记为( Vs Vs , ) 即 (V ,V ) {(v ,v ) | v V ,v V ,(v ,v ) A} s s = i j i  s j  s i j  。 截集的截量──截集中所有容量之和称为该截集的截量。记为 W( Vs Vs , )举例说明，不同截集的截量不同。 可以理解，任何可行流的流量 v(f)W(Vs.Vs ) 3. 最大流最小截量定理： 任一网络 D 中，最大流的流量=最小截集的截量。 四、求最大流的方法(Ford-Fulkerson 标号法) 从以上概念及定理可知，要判断可行流 f 是否最大流有两种途径： 1）能否找出可行流 f 的增广链，若能，则 f 不是最大流，否则 f 是最 大流。 2）V(f)是否等于最小截量，若等，则 f 是最大流，否则 f 不是最大流。 1. 标号法的基本思想：从可行流 f 出发，由 Vs 开始，用对 D 中的每 个顶点进行标号的办法找 f 的增广链。若无，则 f 为所求的最大流。否则， 在增广链上进行调整。 调整理： min{ min ( ),min } ij ij ij w f f + − = −    调整方法：       −  +   = − +      ( , ) ( , ) ( , ) ij i j ij i j ij i j ij f v v f v v f v v f 2.步骤 （1）给出初始可行流 f(如 f=0) （2）给顶点标号，寻找增广链。标号(vi,L(vi))的第一个标号表示 vi 点 而来，第二个标号 L(vi)表示增广链上中该弧允许的调整量。 在标号过程中，每个属于且仅属于下列集合之一： Vo──已标号未检验点集，Vs──已标号已检验的点集， Vs ──未标 号点集