定义94.3设∫是N的一个可行流,如果N中存在一个有向圈C,使得对V(u,v)∈A\4(C),都有 f(u,v)=0,则称∫是N的关于圈C的圈流,记为fC 定义944设f1与∫2都是N中的可行流,定义∫1与f2的和f为: f(u,v)=f1(u,v)+f2(u,v),对v(u,v)∈A 引理944设∫是N上一个流值为0的可行流,且∫不是零流,则∫可表示为N中若干个圈流之和 证明:令A1={(l,v)∈A|∫(u,v)>0} 因∫不是零流,故A1≠φ,设N1是N的由弧集A1导出的子网络,则N的源、汇点∈N1,且 f(u,v)|(a,v)∈A1} 是N1的一个可行流,即在每条弧上满足容量约束且在N1上每个顶点处都满足流量守恒条件。故N1中 每点至少有一条出弧。由引理943知,N1有一个有向圈C1。令:=min{f(u,v)(u,v)∈A(C1)}, 则可定义N中一个圈流∫C和一个新流f如下 6,(u,v)∈A(C1) fc(u, v) 0,(u,1)gA(C1) f(u,v)-8,(u,v)EA(CD) f(u,v)= f(u,v),(u,v)E A(CI) 显然∫=fC+f1,且f至少比∫多一条流量为0的弧 再考虑A2={(,v)∈A|f(,v)>0}在N中的导出子网络N2,重复上述过程,知N2中含有有向 圈C2,使得f=f2+f2,且2又比∫1至少多一条流量为0的弧 如此继续,经有限步后,必须得到f-1=fc+,且是一个零值流。因此 J2+…+Jc 比 定义945设∫是N的一个可行流,C是N(O中的一个有向圈,如果w(C)=∑w(nv)<0 则称C是N(∫)的负费用圈。 定理941设∫是N中流值为v的可行流,则∫是N中最小费用流台N()中没有负费用圈 证:必要性:用反证法。假设∫是N中最小费用v值流,但N(中却有负费用圈C,即 ∑w(u,v)<0 (a,r)∈A(C) 令d=mn{c(u,v)(a,v)∈A(C)},则δ>0。在N(∫)上定义一个圈流fC如下 fc(u,v)= J6,(u, V)EA(C 0, (u,v) A(C)定义 9.4.3 设 f 是 N 的一个可行流，如果 N 中存在一个有向圈 C，使得对∀(,) \ ( ) uv A AC ∈ ，都有 f uv (,) 0 = ，则称 f 是 N 的关于圈 C 的圈流，记为 Cf 。 定义 9.4.4 设 f 1 与 f 2都是 N 中的可行流，定义 f 1 与 f 2的和 f 为： 1 2 f ( , ) ( , ) ( , ), uv f uv f uv = + 对∀(,) uv A ∈ 。 引理 9.4.4 设 f 是 N 上一个流值为 0 的可行流，且 f 不是零流，则 f 可表示为 N 中若干个圈流之和。 证明：令 1 A uv A f uv =∈ > {( , ) | ( , ) 0}。 因 f 不是零流，故 A1≠ φ ，设 N1是 N 的由弧集 A1导出的子网络，则 N 的源、汇点∉ N1，且 1 { ( , )|( , ) } f uv uv A ∈ 是 N1 的一个可行流，即在每条弧上满足容量约束且在 N1 上每个顶点处都满足流量守恒条件。故 N1 中 每点至少有一条出弧。由引理 9.4.3 知，N1有一个有向圈 C1。令： min{ ( , ) | ( , ) ( )} 1 δ = f uv uv AC ∈ ， 则可定义 N 中一个圈流 1 Cf 和一个新流 1f 如下： 1 1 1 , (,) ( ) (,) 0, ( , ) ( ) C uv AC f uv uv AC ⎧δ ∈ = ⎨ ⎩ ∉ ， 1 1 1 (,) , (,) ( ) (,) ( , ), ( , ) ( ) f uv uv AC f uv f uv uv AC ⎧ − ∈ δ = ⎨ ⎩ ∉ 。 显然 1 C 1 f = + f f ，且 1f 至少比 f 多一条流量为 0 的弧。 再考虑 2 1 A uv A f uv =∈ > {( , ) | ( , ) 0}在 N 中的导出子网络 N 2，重复上述过程，知 N 2中含有有向 圈C2 ，使得 2 1 2 C f = + f f ，且 2f 又比 f 1至少多一条流量为 0 的弧。 如此继续，经有限步后，必须得到 1 k k Ck f f f − = + ，且 kf 是一个零值流。因此 CC C 1 2 k f = ff f + +…+ 。 证毕。 定义 9.4.5. 设 f 是 N 的一个可行流，C 是 N f ( ) 中的一个有向圈，如果 (,) ( ) ( ) (,) 0 uv AC w C w uv ∈ ′ ′ = ∑ < ， 则称 C 是 N f ( ) 的负费用圈。 定理 9.4.1 设 f 是 N 中流值为 v0的可行流，则 f 是 N 中最小费用流 ⇔ N f ( ) 中没有负费用圈。 证：必要性：用反证法。假设 f 是 N 中最小费用 v0值流，但 N f ( ) 中却有负费用圈 C，即 (,) ( ) (,) 0 uv AC w uv ∈ ∑ ′ < 。 令 δ = ∈ min{ ( , ) | ( , ) ( )} c uv uv AC ′ ，则δ > 0 。在 N f ( ) 上定义一个圈流 Cf 如下： , (,) ( ) (,) 0, ( , ) ( ) C uv AC f uv uv AC ⎧δ ∈ = ⎨ ⎩ ∉