定理9.21N(V,x,y,A,C)中的流∫是N的最大流当且仅当N中不存在∫可增路。 证明::必要性:若N有∫可増路,则∫不是最大流,因为沿P按(*)式修改流可得流值更大的流∫。 充分性:设N中不存在∫可增路,我们来证明∫是最大流。令 S={v∈|从源x到v有可增路}∪{x} 则ygS,而x∈S,从而K=(S,S)是N中的一个割见割定义)。 对(S,S)中的任一条弧a=(u,v),必定∫(a)=c(a),(否则,若f(a)<c(a),因u∈S,从x 到u有可增路P,P+a是S到ν的可增路,故ν∈S,矛盾);同理,对于(S,S)中任一条弧 a=(v,u),必定f(a)=0。这说明(S,S)中每条弧都是f饱和的而(S,S)中每条弧都是∫零的。由定 理9.1,al∫= Capk,再由推论912便知∫是最大流(而且当前的K是最小割)。 由定理92.1的证明立即可知 推论921(最大流最小割定理,Ford, Fulkerson,1956)任一个网络N中,最大流的流量等于最小割的容 量 由推论921又知: 推论922(整值最大流定理),任一网络中,若所有弧的容量都是整数,则最大流的流值也必为整数 二、求最大流的Ford- Fulkerson标号法 前面已得到求网络N中最大流的一种思想:从一个已知流(例如零流)开始,递推地构作流值严格增 加的流序列。在每一个新的流∫得出之后,若能找到一条∫可增路P,则沿P修改流的值,得到一个更 大的流∫,作为这个序列中的下一个流;若不存在∫可增路,则由定理91.1,∫就是最大流,算法终 止 问题:对一个流∫,如何找∫可增路或判断∫可增路不存在? 解答:Ford- Fulkerson标号法 标号过程描述: 设当前可行流为f。 从源点x开始。首先给x标上∞,即l(x)=∞,[x称为己标未查顶点,其它顶点称为未标未查顶 点] 任选一已标未查顶点u,检查其所有尚未标号的邻点 (1)对u的尚未标号的出邻点v(即(l,v)∈A),若c(,v)>f(,v),则给v标号 (v)=min{a)2(u2y)-f(uy)},[称为已标未查顶点] 否则,不给ν标号。 (2)对u的尚未标号的入邻点v(即(v,u)∈A),若f(v,u)>0,则将v标号 l(v)=min{(af(v,a)},[称为已标未查顶点] 否则,不给ν标号。定理 9.2.1 NV x y AC (,,,, )中的流 f 是 N 的最大流当且仅当 N 中不存在 f 可增路。 证明：：必要性：若 N 有 f 可增路，则 f 不是最大流，因为沿 P 按(*)式修改流可得流值更大的流 ˆ f 。 充分性：设 N 中不存在 f 可增路，我们来证明 f 是最大流。令 S vV = ∈ { |从源 x 到 v 有可增路} {} ∪ x ， 则 y ∉ S ，而 x ∈ S ，从而 K SS = (, )是 N 中的一个割(见割定义)。 对 (, ) S S 中的任一条弧 a uv = (,) ，必定 f () () a ca = ，(否则，若 f () () a ca < ，因 u S ∈ ，从 x 到 u 有可增路 P， P a + 是 S 到 v 的可增路，故 v S ∈ ，矛盾)；同理，对于 (,) S S 中任一条弧 a vu = (, ) ，必定 f a() 0 = 。这说明(, ) S S 中每条弧都是 f 饱和的而(,) S S 中每条弧都是 f 零的。由定 理 9.1.1，Val f CapK = ，再由推论 9.1.2 便知 f 是最大流(而且当前的 K 是最小割)。 由定理 9.2.1 的证明立即可知： 推论 9.2.1 (最大流最小割定理，Ford, Fulkerson, 1956) 任一个网络 N 中，最大流的流量等于最小割的容 量。 由推论 9.2.1 又知： 推论 9.2.2 (整值最大流定理)，任一网络中，若所有弧的容量都是整数，则最大流的流值也必为整数。 二、求最大流的 Ford－Fulkerson 标号法 前面已得到求网络 N 中最大流的一种思想：从一个已知流(例如零流)开始，递推地构作流值严格增 加的流序列。在每一个新的流 f 得出之后，若能找到一条 f 可增路 P，则沿 P 修改流的值，得到一个更 大的流 ˆ f ，作为这个序列中的下一个流；若不存在 ˆ f 可增路，则由定理 9.1.1，f 就是最大流，算法终 止。 问题：对一个流 f, 如何找 f 可增路或判断 f 可增路不存在？ 解答：Ford－Fulkerson 标号法： 标号过程描述： 设当前可行流为 f。 从源点 x 开始。首先给 x 标上∞, 即 l(x)＝∞，[x 称为已标未查顶点，其它顶点称为未标未查顶 点]。 任选一已标未查顶点 u，检查其所有尚未标号的邻点。 (1) 对 u 的尚未标号的出邻点 v (即( ) u,v A ∈ )，若cuv f uv (,) (,) > ，则给 v 标号： lv lu cuv f uv ( ) min ( ), ( , ) ( , ) = − { }，[v 称为已标未查顶点]； 否则，不给 v 标号。 (2) 对 u 的尚未标号的入邻点 v (即( ) v,u A ∈ )，若 f vu (, ) 0 > ，则将 v 标号： lv lu f vu ( ) min ( ), ( , ) = { }，[v 称为已标未查顶点]； 否则，不给 v 标号