我们已经看到跨越树木和砍伐密切相关.这是另一种联系.让我们删除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,为什么不绕过所有边缘,因为这更快？
algorithm math minimum-spanning-tree minimum-cut kruskals-algorithm
给定网络G =(V,E),E中的最大流量f和边缘e,我需要找到一个效果算法,以便检测是否存在包含e的一些最小切割.另一个问题是,如果我发现e包含在某些最小切口中,是否可以检测到它是否是切割中最轻的边缘？
我已经考虑过运行Ford-Fulkerson算法,以及增加/减少给定边缘的容量并看看会发生什么,但我还没有提出可能有助于我解决问题的东西.
如果有人能指出我的解决方案,我会很高兴,在此先感谢.
我正在实施Karger的算法.据我所知,最后两个节点之间的边数并不总是Min Cut.我无法理解的是如何实际获得此算法的最小切割.我一直在寻找很多关于概率的东西,但这一切对我来说都是胡言乱语......
根据我的阅读,我认为我需要在图表上多次运行Karger算法.这将使我很有可能成功击中最低限度.我认为？...
有人可以用更简单的方式解释一下吗？如何查找运行此算法的次数？我上面说的甚至是正确的吗？