使用Kruskal算法寻找图中的最小切点？

Question

我们已经看到，生成树和切割是密切相关的。这是另一个连接。让我们删除克鲁斯卡尔算法添加到生成树的最后一条边;这将树分成两个部分，从而在图中定义一个切割（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）最小割算法，它是这个重要问题中已知最快的算法。

• 这难道不是依赖于一个事实，即有n^2种处理通过Kruskal算法图独特的方式？我的意思是如果只有克鲁斯卡尔算法处理10个节点的图形的3种独特方式，重复该过程n^2次将不会产生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，为什么不循环遍历所有边，因为这更快？

Answer 1

我认为你可能会误解算法是如何工作的。该算法通过运行Kruskal算法工作，直到最后一个边被添加，然后在此之前停止。该算法不会尝试构建这些“最后边缘”的集合;相反，重复运行克鲁斯卡尔算法的O（n ）随机迭代，以建立O（n ）可能的切割。在所有这些候选剪辑中取最低的剪辑，然后给出具有高概率的最小剪辑。换句话说，如果有少于O（边缘）的边缘，这并不重要。重要的是最后的削减，而不是最后考虑的边缘。

希望这会有所帮助！