建模
c ( e) f ( e) e ∈ P + , 定义 9 设 l ( P) = min l (e) ,其中 l (e) = e∈E ( P ) f ( e) e∈ P (1)若 l ( P ) = 0 ,则称 P 链为 f 饱和链 饱和链； 非饱和链。 (2)若 l ( P ) > 0 ,则称 P 链为 f 非饱和链 定义 10 设 f 是一个流， P 是从源 s 到汇 t 的一条链，若 P 满足(1)在弧 e ∈ P + 上， 0 ≤ f (e) < c(e) ,即 P + 中每条弧都是不饱和弧； (2)在弧 e ∈ P 上， 0 < f (e) ≤ c (e) ,即 P 中每条弧都是非零弧； 则称 P 是关于流 f 的一条增广链 增广链。 增广链 显然一条 f 增广链就是一个从发点 s 到收点 t 的 f 非饱和链。若在 非饱和链。 网络中存在一条 f 增广链，则表明 f 不是最大流。 定理 3f 是网络 N 的最大流的充要条件是 N 不含 f 增广链。