首先给vs标号(+∞,此时,V={V}≠={V1…V}。 (3)若V。非空,则反复按以下①②进行,否则按第(5)步: ①在V。中任选v,检查v到V的弧(v,v),或中的点v到v的弧(vV) 满足以下条件者给v标号。 i)对正向弧(vv),若非饱和,则给点V标以(vv),其中 l(V)=min{v)、(wi-fi) 同时把V从V中除去,归入Vo,若V∈V。说明已找出f的增广链μ 按(4) i)对反向弧(vV),若非零流,则给点V标以(-v(V),其中 I(ViFmin(/vi), fi) 同时把从中除去,归入V ②把已检验的点v,归入Vs (4)在增广链μ上调整,得新可行流f。返回(2) (5)写出最大流={}的流量v(f),和最小截集W(V‘,D'),终止。 例用Ford- Fulkerson标号法求下图的最大流 (76) (2,0) (10,4) (84) 调整后为: Vs(0,∞× 30) (20) (7,7) (10,7) (图14) 由于标号进行不下去(即Vo=φ),因此,目前可行流就是最大流。37 首先给 vs 标号(0,+)，此时，Vo={Vs},Vs ={V1…Vt}。 （3）若 Vo 非空，则反复按以下①②进行，否则按第(5)步： ①在Vo中任选vi，检查vi到 Vs 的弧(vi,vj)，或 Vs 中的点vj到vi的弧(vj,vi)， 满足以下条件者给 vj 标号。 i) 对 正 向 弧 (vi,vj) ， 若 非 饱 和 ， 则 给 点 vj 标 以 (vi,l(vj)) ，其中 l(Vj)=min{l(vj),(wij－fij)} 同时把 Vj 从 Vs 中除去，归入 Vo，若 Vt∈Vo 说明已找出 f 的增广链 按(4)。 ii) 对反向弧 (vj,vi) ， 若非 零 流， 则 给点 Vj 标 以 (-vi,l(Vj)) ，其中 l(Vj)=min{l(vj),fij} 同时把 Vj 从 Vs 中除去，归入 Vo ②把已检验的点 vi，归入 Vs （4）在增广链上调整，得新可行流 f。返回(2)。 （5）写出最大流 f *={fij}的流量 v(f* )，和最小截集 W(Vs * , * Vs )，终止。 例 用 Ford—Fulkerson 标号法求下图的最大流 调整后为： （图 14） 由于标号进行不下去(即 Vo=)，因此，目前可行流就是最大流。             V V3 2(us,5) V V5(V4,3) s(0,) V4(V1,3) V1(-V2,3) V2(Vs,2) V3 V V5 s(0,) V1 V4 (7,6) (6,6) (8,3) (3,3) (3,0) (2,0) (10,4) (7,7) (8,4) (7,6) (6,6) (8,6) (3,0) (3,0) (2,0) (10,7) (7,7) (8,7)