使用Kruskal算法在图中找到最小割？

Question

使用Kruskal算法在图中找到最小割？

algorithmmathminimum-spanning-treeminimum-cutkruskals-algorithm

5

我们已经看到生成树和割是密切相关的。这里有另一个联系。让我们移除Kruskal算法添加到生成树中的最后一条边；这将把树分成两个部分，从而在图中定义了一个割 (S,S)。我们能说什么关于这个割呢？假设我们处理的图是无权的，并且它的边缘被均匀随机地排序，以便Kruskal算法处理它们。这里有一个引人注目的事实：至少以1/n^2的概率，(S,S) 是图中的最小割，其中割(S, S) 的大小是穿过S和S之间的边数。这意味着重复这个过程O(n^2)次并输出找到的最小割将以高概率产生G中的最小割：对于无权最小割的O(mn^2 log n)算法。一些进一步的调整给出了由David Karger发明的O(n^2 log n)最小割算法，这是已知的解决这个重要问题的最快算法。

这不取决于Kraskal算法有n^2种唯一的处理图形方式吗？我的意思是，如果Kraskal算法只有3种唯一的处理10个节点的图形的方式，那么重复n^2次这个过程将不会产生n^2个唯一的“最后边缘”。如果有少于n^2个唯一的最终割，那该怎么办？
如果总共的边数少于n^2怎么办？例如，您可以有一个由10个节点组成的连接图，其中只有9条边，这意味着无论您重复多少次算法，您都不会有n^2个唯一的“最后边缘”。在这种情况下会怎样？
直接遍历每条边并检查边是否为最小割不是更容易吗？在一个n个节点的图中，最大数量的唯一边缘是n + n-1 + n-2... + 1个边缘，这比n^2少。考虑到n^2小于n^2 log n，为什么不直接循环所有边缘，因为这样更快？

- fdh

这段文本来自哪里？ - Tom Kealy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

我认为你可能误解了算法的工作方式。该算法通过运行Kruskal算法，直到添加最后一条边之前停止。该算法不会尝试构建这些“最后一条边”的集合；相反，它重复运行O(n²)次Kruskal算法的随机迭代，以建立O(n²)个可能的割。在所有这些候选割中选择最小割，则具有高概率的最小割。换句话说，如果边数少于O(n²)，也没有关系。重要的是最终割，而不是考虑的最后一条边。

希望这能帮到你！