首页 > 代码库 > 图的最小切隔问题Minimum Cuts
图的最小切隔问题Minimum Cuts
前提条件是这样的:输入一个图(可以是有向图,也可以是无向图,允许平行边存在),我们要做的事情是将这个图切割成两个子图,(切割的定义:将图中的所有顶点分为两个集合A和B,要求这两个集合非空)假设这个图中的顶点数为n,边的条数为m,这样一来就总共有2的n次方减2种切割方案,(每个顶点有两种选择,要么选集合A,要么选集合B,同时保证两个集合非空),要找到一种切割方案,使得切割经过的边最少(仅仅指从左边的集合A到右边的集合B的边,忽略有向图中从右边到左边的边)
这就引入了一种算法,叫Rand Contraction算法,这个算法的核心是一个while循环
只要图中的顶点数大于2,就进入循环
1,随机选择图中的一条边,假设边的两个顶点为u和v
2,将这两个顶点u和v融合成一个单独的顶点
3,如果有自循环,就删除掉
最后循环体外,按照只剩下两个顶点的情况进行切割
直接看例子:
其中红线圈表示每次while循环迭代选择的边,该例子中此种切割方案经过的边最少,为2
下面我们来看另外一种切割方案
在第二次迭代的时候,我们选择了一条不同的边,这样我们就得到了不同的结果,毫无疑问,这种切割方案并不是最优的
很多情况下,最优的切割方案并不是只有一种,例如二叉树,切割任意一条边都是最优的切割方案,还有没有对角线的多边形
事实上这种算法成功的概率,(我指的是直接找到的是最小切割方案,忽略其它不是最优切割方案的情况),仅仅是大于等于1/n的平方,这是经过数学证明的
尽管如此,这个算法仍然是有用的。
图的最小切隔问题Minimum Cuts
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。