独立集 独立集英语Independent set是图论中的概念一个独立集也称为稳定集是一个图中一些两两不相邻的顶点所形成的集合换句话说独立集 S displaystyle S 由图中若干顶点组成且 S displaystyle S 中任两个顶点之间没有边等价地图中的每条边至多有一个端点属于 S displaystyle S 一个独立集的基数是它包含顶点的数目 如果往图 G displaystyle G 的独立集 S displaystyle S 中添加任一个顶点都会使独立性丧失亦即造成某两点间有边那么称 S displaystyle S 是极大独立集如果 S displaystyle S 是图中所有独立集之中基数最大的那么称 S displaystyle S 是最大独立集且将该基数称为 G displaystyle G 的独立数记为 α  G  displaystyle alpha G 一般来讲图 G displaystyle G 中可能存在多个极大独立集最大独立集亦如是最大独立集一定是极大独立集但反之未必 给定一张图寻找其中一个最大独立集的问题被称为最大独立集问题该问题已知是NP困难的最优化问题且即便试图以常数倍近似也是NP困难的因此计算机科学家普遍相信不存在解决该问题的高效算法无论是精确求解还是以常数倍近似求解