algorithm - 使用 Kruskal 算法找到图中的最小割点？

Question

We have already seen that spanning trees and cuts are intimately related. Here is another connection. Let’s remove the last edge that Kruskal’s algorithm adds to the spanning tree; this breaks the tree into two components, thus defining a cut (S,S) in the graph. What can we say about this cut? Suppose the graph we were working with was unweighted, and that its edges were ordered uniformly at random for Kruskal’s algorithm to process them. Here is a remarkable fact: with probability at least 1/n^2, (S,S) is the minimum cut in the graph, where the size of a cut (S, S) is the number of edges crossing between S and S. This means that repeating the process O(n^2) times and outputting the smallest cut found yields the minimum cut in G with high probability: an O(mn^2 log n) algorithm for unweighted minimum cuts. Some further tuning gives the O(n^2 log n) minimum cut algorithm, invented by David Karger, which is the fastest known algorithm for this important problem.

• 这难道不是因为有 n^2 种独特的方法可以通过 Kruskal 算法处理图形吗？我的意思是，如果 Kruskal 算法只有 3 种独特的方式来处理具有 10 个节点的图，那么重复该过程 n^2 次将不会产生 n^2 个独特的“最后一条边”。如果独特的最终切割少于 n^2 个(即少于 n^2 个独特的“最后边缘”)，它会如何工作？

• 如果边总数少于 n^2 怎么办？例如，您可能有一个只有 9 条边的 10 个节点的连接图，这意味着无论您重复该算法多少次，您都不会有 n^2 个唯一的“最后一条边”。在这种情况下它会如何工作？

• 循环遍历每条边并检查该边是否是最小切割不是更容易吗？在n个节点的图中，唯一边的最大数量为n + n-1 + n-2 ... + 1条边，小于n^2。考虑到 n^2 小于 n^2 log n，为什么不遍历所有边因为这样更快？

Answer 1

我认为您可能误解了算法的工作原理。该算法的工作原理是运行 Kruskal 算法，直到添加最后一条边，然后在此之前停止。该算法不会尝试建立这些“最后边缘”的集合；相反，重复运行 Kruskal 算法的 O(n²) 次随机迭代，以建立 O(n²) 可能的削减。在所有这些候选切割中取最低切割然后以高概率给出最小切割。换句话说，边数是否少于 O(n²) 并不重要。重要的是最后保留的切割，而不是考虑的最后一个边缘。

希望这对您有所帮助!