Ford-Fulkerson算法&最大流最小割集定理

Question

嗨，我很难用最大流最小切定理学习福特-富尔克森算法.

根据该定理，最大流量应与被切割边的总重量相同。

然而，看到视频https://www.youtube.com/watch?v=Tl90tNtKvxs，这让我很困惑。这位讲师说，根据福特-富尔克森算法，最大流量为19，但我无法用19的费用找到任何削减。怎么了？

Answer 1

你对最大流量最小切割定理的解释没有什么问题。

最小割集由边SA和CD组成，总容量为19。

要进行削减并计算成本，您可以：

1. 将所有顶点划分为2组，S和D，使得源在S中，漏在D中。
2. 把所有的边从S中的顶点切成D中的顶点。注意，你不需要切割从D到S的边。
3. 把你切割的边的容量加起来。

对于上面的最小割集，S包含顶点s和c，D包含其余的顶点。