第2讲 最大流与最小费用流(10)

建模

最大流与最小割的关系：定理 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 的最大流的价值等于最小割的容量。 上述定理是图论的重要核心，关于图的许多结果，在适当的选择网络 后，应用这个定理往往能够轻易地获得解决。从这个定理的证明中，可以 引出求网络最大流的一个算法。但这种方法实际做起来有困难，因为没解 决如何寻找增广链的方法。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第2讲 最大流与最小费用流(10)在线全文阅读。