摘要: 题目有点长,就贴过来好了. 计算一张给定的图的最大独立集不是一件容易的事情. 它往往需要一个比较高的复杂度来实现. 因此, 我们经常使用随机的办法来试图求出独立集:随意一个点的排列, 按顺序考察每个点. 如果将当前的点纳入独立集中不会引起冲突(即不存在某条边的两端均入选的情况), 则将这个点加入独立集中. 按照这种办法得到的独立集可能不是点数最多的, 所以我们经常将上面的操作重复进行多次, 从中...阅读全文