建模
最大流与最小割的关系：定理 1 设 f 是 N 的流， ( A, A) 是一个割，则： (1) Val f =e∈N + ( A )
∑
f (e )
e∈N ( A )
∑
f ( e)
(2) Val f ≤ C ( A, A) 。 式(1)表明运输网络的一个自源 s 到汇 t 的流值，等于任何分离 s 和 t 的 割中流的净值，即割的自 A 到 A 的弧中的流减去自 A 到 A 的流的总体。 定理 2(最大流最小割定理) (最大流最小割定理) (1)设 f 是流， K 是割，若 Val f = C ( K ) ,则 f 是最大流， K 是 最小割。 (2)网络 N 的最大流的价值等于最小割的容量。 上述定理是图论的重要核心，关于图的许多结果，在适当的选择网络 后，应用这个定理往往能够轻易地获得解决。从这个定理的证明中，可以 引出求网络最大流的一个算法。但这种方法实际做起来有困难，因为没解 决如何寻找增广链的方法。