前提条件是这样的：输入一个图（可以是有向图，也可以是无向图，允许平行边存在），我们要做的事情是将这个图切割成两个子图，（切割的定义：将图中的所有顶点分为两个集合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的平方，这是经过数学证明的

尽管如此，这个算法仍然是有用的。

最新文章

1. hibernate 中根据id删除一条记录的语句
2. Query DSL for elasticsearch Query
3. ios播放声音中断后台音乐的问题
4. CSS3实现jquery的特效
5. Learning JavaScript Design Patterns The Constructor Pattern
6. nyoj 214
7. 设置Proxy Server和SQL Server实现互联网上的数据库安全
8. 精通CSS+DIV基础总结(一)
9. Android.mk中的经常使用语法
10. asp.net core中负载均衡场景下http重定向https的问题
11. 快速搭建fabric-v1.1.0的chaincode开发环境
12. Java-HttpServlet
13. BZOJ3252: 攻略 可并堆
14. Dockerfile的 RUN和CMD
15. 美国FLAG和中国BAT的比较（王益）
16. js闭包实例汇总
17. 【Unity】12.1 基本概念
18. magento增加左侧导航栏
19. shell脚本实现无密码交互的SSH自动登陆
20. ANTLR4权威指南 - 第7章 通过特定应用程序代码解耦语法

热门文章

1. APP被应用商店下架了怎么办？
2. BZOJ 1059 [ZJOI2007]矩阵游戏：二分图匹配
3. DIV CSS 笔记
4. C++（五）— 控制保留小数位数
5. HTML5调用百度地图API进行地理定位实例
6. 【leetcode刷题笔记】String to Integer (atoi)
7. bzoj 2733 永无乡 线段树
8. Maven(3)-利用intellij idea创建maven web项目
9. 第二次C语言实验报告
10. Python：正则表达式（二）