algorithm - 关于增广路径的问题（Ford-Fulkerson 方法）

Question

我现在正在学习 Ford-Fulkerson 方法。

有些文章说如果 f 是最大流，那么就没有增广路径！ 但是如果没有增广路径，你怎么知道 f 是最大流量？

• 你怎么知道寻找增广路径的方法是正确的？
• 在残差网络中，为什么如果我们不能从 s 到达 t 就没有办法增加流量？你怎么知道？

标签： algorithmoptimizationmathematical-optimizationmax-flowford-fulkerson

Answer 1

这是最大流最小割定理，参见。例如CLRS中的定理 26.6 。要点如下：令S为残差网络中从源可访问的顶点集，令T = V \ S。那么，如果没有增广路径，（S，T）就是一个割，我们发现流的值就是这个割的容量。由于流量值永远不会超过截断能力，因此流量是最大的。