fdh*_*fdh 5 algorithm math minimum-spanning-tree minimum-cut kruskals-algorithm
我们已经看到跨越树木和砍伐密切相关.这是另一种联系.让我们删除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)最小割算法,这是对这个重要问题最快的已知算法.
这是否取决于通过Kruskal算法处理图形的n ^ 2种独特方法的事实？我的意思是,如果Kruskal算法只有 3种独特的方法来处理具有10个节点的图形,重复该过程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,为什么不绕过所有边缘,因为这更快？
我认为您可能误解了算法的工作原理。该算法的工作原理是运行克鲁斯卡尔算法，直到添加最后一条边，然后在此之前停止。该算法不会尝试建立这些“最后边缘”的集合；相反，重复运行 Kruskal 算法的 O(n 2 ) 随机迭代，以构建 O(n 2 ) 可能的切割。在所有这些候选切割中取最低的切割然后以高概率给出最小切割。换句话说，边的数量是否少于 O(n 2 ) 并不重要。重要的是最后保留的切口，而不是考虑的最后一个边缘。
希望这可以帮助！