定理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 标号
当检查完u的所有邻点之后,u称为已标已查顶点。 反复进行上述标、查过程,最终必出现两种结果之 ()汇点y获得标号,此时已得到∫可增路。沿该路增流。 (i)y点未获得标号,但已没有已标未查顶点(所有已标顶点都已被查,没有更多的新标号顶点) 此时当前的流∫即为最大流[设当前已标已查的顶点之集为S,则(S,S)为最小割 例如:网络M(V,x,y,A,O及其上一个流f,(括号内数字是弧容量)。 35(9) v15(9) 0(5) 0(2)k6为y2c 2379)v2 情况():获得一条∫可增路 情况(i):已得到最大流和最小割 求网络最大流的Ford- Fulkerson标号算法 输入:网络N(V,x,y,A,C) 输出:网络N中一个最大流。 第0步(初始化):对a∈A,令∫(a)=0 第1步:给源点x标号(x,∞)。L:={x},S=Φ。其中L表示已标未査集,S表示已标已查集 第2步:任取l∈L,检查u的每个尚未标号的邻点v (1)若v∈N'(u),w尚未标号且C(u,yv)>f(u,v),则给v标号(u,+,l(v),其中 l(v)=min{(au),C(l,y)-f(l,v)}。令L:=LU{v}。 (2)若v∈N(a),ν尚未标号且f(v,u)>0,则给ν标号(u,-,l(v),其中 l(v)=min{(au),f(v,u)}。令L:=LU{v}。 第3步:重复第2步,直到汇点y被标号,或y未被标号但L=Φ为止。 若是后者,算法结束,当前流是最大流 若是前者,转下步。 2 第5步:若〓的标号为(w,+,l(=),则令f(W,=)=f(,)+l(y) 若的标号为(V,-,l(二=),则令∫(=,w)=f(二,w)-l(y) 注:不论二是哪个点,此处总是l(y),因1⑦)是最大的可增量(沿可增路)。 第6步:若W≠x,则令x=w,转第5步; 否则,去掉所有的顶点标号,转第1步
当检查完 u 的所有邻点之后，u 称为已标已查顶点。 反复进行上述标、查过程，最终必出现两种结果之一： (i) 汇点 y 获得标号，此时已得到 f 可增路。沿该路增流。 (ii) y 点未获得标号，但已没有已标未查顶点(所有已标顶点都已被查，没有更多的新标号顶点)。 此时当前的流 f 即为最大流[设当前已标已查的顶点之集为 S，则(, ) S S 为最小割] 例如：网络 N(V, x, y, A, C)及其上一个流 f,（括号内数字是弧容量）。 情况(i)：获得一条 f 可增路 情况(ii)：已得到最大流和最小割 求网络最大流的 Ford－Fulkerson 标号算法： 输入：网络 NV x y AC (,,,, ) 输出：网络 N 中一个最大流。 第 0 步(初始化)：对∀ ∈a A ，令 f a() 0 = ； 第 1 步：给源点 x 标号(, ) x ∞ 。 L xS : { }, = =Φ 。其中 L 表示已标未查集，S 表示已标已查集。 第 2 步：任取u L ∈ ，检查 u 的每个尚未标号的邻点 v。 (1) 若 vNu( ) + ∈ ， v 尚未标号且 Cuv f uv (,) (,) > ，则给 v 标 号 ( , , ( )) u lv + ，其中 lv lu Cuv f uv ( ) min{ ( ), ( , ) ( , )} = − 。令 LLv : {} = ∪ 。 (2) 若 vNu( ) − ∈ ， v 尚未标号且 f vu (, ) 0 > ，则给 v 标 号 ( , , ( )) u lv − ，其中 lv lu f vu ( ) min{ ( ), ( , )} = 。令 LLv : {} = ∪ 。 第 3 步：重复第 2 步，直到汇点 y 被标号，或 y 未被标号但 L = Φ 为止。 若是后者，算法结束，当前流是最大流； 若是前者，转下步。 第 4 步：令 z y = 。 第 5 步：若 z 的标号为( , , ( )) w lz + ，则令 f (,) (,) () wz f wz ly = + ； 若 z 的标号为( , , ( )) w lz − ，则令 f (, ) (, ) ( ) zw f zw ly = − 。 注：不论 z 是哪个点，此处总是 l (y)，因 l (y)是最大的可增量 (沿可增路)。 第 6 步：若 w x ≠ ，则令 z w = ，转第 5 步； 否则，去掉所有的顶点标号，转第 1 步。 v4 v1 v3 x y v2 7(7) 7(9) 5(8) 0(5) 5(9) 0(2) 0(6) 7(10) 5(5) 2 2 3 3 3 ∞ v4 v1 v3 x y v2 7(7) 9(9) 7(8) 2(5) 5(9) 0(2) 0(6) 9(10) 5(5) 1 1 1 ∞