关于增强路径的几个问题(Ford-Fulkerson法)

Question

我现在在学习福特-富尔克森的方法。

有些文章说，如果f是最大流，那么就没有增强路径！但是如果没有增强路径，您如何知道f是最大流？

• 你怎么知道如何找到正确的路径？
• 在剩余网络中，如果我们不能从S到达t，为什么没有增加流量的方法？你怎么知道的?

Answer 1

这是最大流最小切定理。例如CLRS中的定理26.6。其基本思想是:设S是残差网络中从源到的顶点集合，T=V_S，如果没有增强路径，则(S，T)是一个截，发现流的值就是这个截的容量。由于流量值永远不能超过切割能力，因此流量是最大的。