3

嗨，我在使用max-flow min-cut Theorem研究 Ford-Fulkerson 算法时遇到了麻烦。

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

但是，看到视频https://www.youtube.com/watch?v=Tl90tNtKvxs让我感到困惑。讲师说根据 Ford-Fulkerson 算法，最大流量为 19，但我找不到任何削减 19 的费用。出了什么问题？

4

2 回答 2

2

切口意味着您在源极和漏极之间定义切口。该切口不必是直线、曲线或任何其他形状就足够了。

例如，在这里我选择了蓝色切割，这样边缘AB、AD和CD正在通过切割。现在，如果我们查看这些边的分配流，并将它们相加，我们得到4+6+9=19。

例如，另一种切割是绿色的。在这里，我们有“向前”移动的边BT、AD和AC ，以及“向后”移动的边DC 。所以流量的总和是9+6+9-5=19。因此，无论我们采取什么措施，总和始终是 19（当然，我们需要进行适当的簿记，并减去相反方向的流量）。

当然，你可以选择任何你想要的切割（例如，在源之后的切割，或者就在排水管之前的切割），如果算法正确完成，那么所有这些切割的总和总是 19。这是合乎逻辑的，因为如果一个切割的流量将大于（或少于）19，然后存在一个“推进”一个流量为 19 的节点的切割，意味着在该节点中，流量已经消失或出现。

然而，它认为，如果您要遍历所有可能的切割，那么最小切割就是容量总和最大的切割。因此，严格来说，我们可以遍历所有可能的切割，并且每次都跟踪容量的总和，最后选择流量最小的那个。然而，如果简单地迭代所有切割，一种天真的方法将导致O(2 n )算法，与Ford-Fulkerson 算法相比，这当然是不可取的。

算法结束时的两次切割

于 2018-12-02T12:42:30.157 回答
2

您对最大流最小割定理的解释没有错。

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

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

  1. 将所有顶点分成 2 组，S 和 D，使得源极在 S 中，漏极在 D 中。
  2. 剪切从 S 中的一个顶点到 D 中的一个顶点的所有边。请注意，您不需要剪切从 D 到 S 的边。
  3. 将您切割的边缘的容量加起来。

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

于 2018-12-02T15:56:56.907 回答