若给一个可行流f},称网络中f=c的弧为饱和弧， 称f≤c,的弧为非饱和弧，称f=0的弧为零流弧，称f>0 的弧为非零流弧。 增广链：设(f)是可行流，u是v,到v,的一条链，若满足下 列条件，则称为关于f的增广链。（注意：f=f)}) 1°对于任何(，)∈+，0≤<c(前向弧为非饱和弧) 2°对于任何（，)∈，0<f≤c(后向弧为非零流弧) 如图7-15中，={v,v0}就是一条增广链。 定理：可行流是最大流，当且仅当不存在关于f的增广链。 证明：必要性：设f是最大流，若存在关于的增广链u,令 9=mm-fg到 则0>0，令 f0, （,y)∈u+ f*- f*-0, (v,∈0 ,y)∈u若给一个可行流｛f ij｝，称网络中 f ij =cij 的弧为饱和弧， 称 f ij＜ cij 的弧为非饱和弧，称f ij =0的弧为零流弧，称f ij＞0 的弧为非零流弧。 增广链：设｛f ij｝是可行流，μ是vs 到vt 的一条链，若μ满足下 列条件，则称μ为关于 f 的增广链。（注意： f =｛f ij｝） 1°对于任何（vi ,vj）∈μ＋ ，0≤ f ij ＜ cij （前向弧为非饱和弧） 2°对于任何（vi ,vj）∈μ -，0 ＜ f ij ≤ cij （后向弧为非零流弧） 如图7-15中，μ=｛vsv2v1v3vt｝就是一条增广链。 定理：可行流 f﹡是最大流，当且仅当不存在关于 f﹡的增广链。 证明：必要性：设f﹡是最大流，若存在关于 f﹡的增广链μ，令 则θ ＞0，令 +θ， （vi ,vj）∈μ＋ = -θ， （vi ,vj）∈μ - ， （vi ,vj）∈μ                          =  −    +  −                 ij vi v j μ ij ij vi v j μ θ min min c f , min f  fij fij fij fij