![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Independent_set_graph.svg/langzh-640px-Independent_set_graph.svg.png&w=640&q=50)
独立集
維基百科,自由的 encyclopedia
独立集(英语:Independent set)是图论中的概念。一个独立集(也称为稳定集)是一个图中一些两两不相邻的顶点所形成的集合。换句话说,独立集由图中若干顶点组成,且
中任两个顶点之间没有边。等价地,图中的每条边至多有一个端点属于
。一个独立集的基数是它包含顶点的数目。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Independent_set_graph.svg/640px-Independent_set_graph.svg.png)
如果往图的独立集
中添加任一个顶点都会使独立性丧失(亦即造成某两点间有边),那么称
是极大独立集。如果
是图中所有独立集之中基数最大的,那么称
是最大独立集,且将该基数称为
的独立数,记为
[1]。一般来讲,图
中可能存在多个极大独立集;最大独立集亦如是。最大独立集一定是极大独立集,但反之未必。
给定一张图,寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是NP困难的最优化问题,且即便试图以常数倍近似也是NP困难的。因此,计算机科学家普遍相信不存在解决该问题的高效算法,无论是精确求解还是以常数倍近似求解。