欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

问最大流-最小割集定理EN

最编程 2024-07-31 20:30:42
...

我理解Ford-Fulkerson求最大流的方法,但我很难理解min如何给出最大流的值。

最大流-最小切割定理指出,从源到汇的最大流量等于最小切割的值。

CLRS中的Min定义为:

网络的最小割集是指其容量比网络的所有割集都最小的割集。

如果容量最小,就意味着存在容量较高的增强路径,那么为什么容量较低的路径会出现最大流量?作者所说的容量是指residual capacity吗?因为这一切都有意义。