查看“︁独立集”︁的源代码

[[File:Independent set graph.svg|thumb|圖中九個藍色的頂點是{{le|延伸佩特森圖|Generalized Petersen graph}}GP(12,4)中的一个最大独立集]]'''独立集'''（英语：Independent set）是[[图论]]中的概念。一个独立集（也称为'''稳定集'''）是一个[[图 (数学)|图]]中一些两两不相邻的[[顶点 (图论)|顶点]]所形成的集合。换句话说，独立集<math>S</math>由图中若干顶点组成，且<math>S</math>中任两个顶点之间没有[[邊 (圖論)|边]]。等价地，图中的每条边至多有一个端点属于<math>S</math>。一个独立集的[[基数 (数学)|基数]]是它包含顶点的数目。

如果往图<math>G</math>的独立集<math>S</math>中添加任一个顶点都会使独立性丧失（亦即造成某两点间有边），那么称<math>S</math>是'''极大独立集'''。如果<math>S</math>是图中所有独立集之中基数最大的，那么称<math>S</math>是'''最大独立集'''，且将该基数称为<math>G</math>的独立数，记为<math>\alpha(G)</math><ref>{{Cite book|title=''Algebraic Graph Theory''|last=Chris Godsil and Gordon Royle|first=|publisher=Springer|year=2001|isbn=0-387-95220-9|location=New York|pages=p. 3}}</ref>。一般来讲，图<math>G</math>中可能存在多个极大独立集；最大独立集亦如是。最大独立集一定是极大独立集，但反之未必。

给定一张图，寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是[[NP困难]]的[[最优化问题]]，且即便试图以常数倍近似也是NP困难的。因此，计算机科学家普遍相信不存在解决该问题的高效算法，无论是精确求解还是以常数倍近似求解。

== 数学定义 ==
对于图<math>G = (V,E)</math>，如果顶点子集<math>S \subseteq V</math>满足<math>\forall u,v \in S, \{u,v\} \not\in E</math>，则称<math>S</math>为<math>G</math>的一个独立集，称<math>|S|</math>为该独立集的基数。

对于独立集<math>S</math>，如果<math>\forall v \in V \setminus S, \exists u \in S: \{u,v\} \in E</math>，则称<math>S</math>是极大独立集。直观而言，极大意味着<math>S</math>不能单纯通过加入顶点来扩充。

如果<math>|S|</math>是所有独立集中最大的，那么称<math>S</math>是最大独立集，并将<math>|S|</math>称作<math>G</math>的独立数（independence number），记作<math>\alpha(G)</math>。最大独立集一定是极大独立集；若不然，我们总能加入顶点来扩充之，从而与最大的定义矛盾。

== 整数规划形式 ==
计算独立数<math>\alpha(G)</math>的问题可以等价表达成如下的[[线性规划|整数规划]]：

: <math>
\begin{aligned}
	\max \quad &\sum_{v \in V} x_v \\
	\text{s.t.} \quad & x_u + x_v \leq 1 & \forall \{u,v\} \in E \\
	& x_v \in \{0,1\} & \forall v \in V
\end{aligned}
</math>

其中，变量<math>x_v</math>取1代表把顶点<math>v</math>放入独立集，取0则反之。第一条线性约束表达了每条边的两个端点不能同时放入独立集中。

== 与其它图论对象的联系 ==

=== 与顶点覆盖的关系 ===
图的一个[[覆盖 (图论)|顶点覆盖]]（vertex cover）是顶点集的一个子集，使得图中每条边都与其中某点相邻。基数最小的顶点覆盖称为图的最小顶点覆盖。独立集与顶点覆盖的定义互补，因此不难看出，<math>S</math>是图<math>G</math>的独立集当且仅当<math>V \setminus S</math>是<math>G</math>的顶点覆盖。于是，<math>\alpha(G)</math>就等于<math>G</math>的顶点数减去<math>G</math>的最小顶点覆盖的基数。

=== 与团的关系 ===
在图论中，[[團 (圖論)|团]]（clique）是一个与独立集密切相关的概念。图<math>G = (V,E)</math>的一个团指的是一个顶点子集<math>C \subseteq V</math>，使得<math>C</math>中顶点两两相邻。用图论的语言，团即一个[[完全图|完全]]的[[子图]]。<math>G</math>的最大团的基数称作<math>G</math>的团数（clique number），记作 <math>\omega(G)</math>。 如果说独立集是一种水火不容的顶点集，那么团就是一种息息相关的顶点集。不难看出，一个图的团是其补图的独立集，反之亦然。这个一一对应关系使得二者性质能够相互转述，而与二者相关的问题往往等价。例如，图的团数等于其补图的独立数，即 <math>\omega(G)=\alpha(\overline{G})</math>。类似地，图<math>G</math>中团的总数等于补图<math>\overline{G}</math>中独立集的总数。

对于一般的图而言，寻找最大团是NP困难的，从而寻找最大独立集也是NP困难的。计算机科学家普遍相信没有算法能在确定性多项式时间解决之。但是，对于[[二分图]]这一特殊情形，则有多种方法可以高效地求解。例如，可以求解松弛后的[[线性规划]]并对结果作整数化处理，也可以使用[[匈牙利算法]]求出最小顶点覆盖后再转化为最大独立集。

=== 与点连通度的关系 ===
图的[[连通图|点连通度]]<math>\kappa(G)</math>定义为：最少需要删除<math>\kappa(G)</math>个顶点方能使得图不复连通。独立数与点连通度有着简单关系

: <math> \kappa(G) \leq n - \alpha(G) </math>

原因是：设<math>S</math>是一个最大独立集，把<math>V \setminus S</math>的顶点全部删掉以后，残余下来的正是独立集<math>S</math>，而它自然是不连通的。

=== 与着色数的关系 ===
图的[[图着色问题|着色]]（proper colouring）即为每个顶点染上一种颜色，使得任意相邻顶点颜色均不同（但不相邻顶点颜色可以相同）。对图<math>G</math>进行着色所需的最少颜色数被称为<math>G</math>的[[着色数]]，记作<math>\chi(G)</math>。独立数和着色数之间存在以下关系：

: <math> \frac{n}{\alpha(G)} \leq \chi(G) \leq n - \alpha(G) + 1 </math>

其中<math>n</math>是<math>G</math>中的顶点数。{{Collapse top|title=证明}}
'''左侧不等式'''：设着色<math>f: V \to [\chi(G)]</math>是一个使用颜色最少的方案，我们构造<math>\chi(G)</math>个集合<math>S_1, \dots, S_{\chi(G)}</math>如下。<math>S_i := \{v \in V \mid f(v) = i\}</math>。也就是说，把颜色相同的节点放入同一个集合。这些集合构成了顶点集的一个划分，所以<math display="inline">n = \sum_{i=1}^{\chi(G)} |S_i|</math>。注意到每个集合都各是一个独立集（因为相同颜色的顶点之间不允许有边），所以<math>|S_i| \leq \alpha(G)</math>对它们均成立。代入先前等式便有<math display="inline">n \leq \chi(G) \cdot \alpha(G)</math>

'''右侧不等式'''：设<math>S</math>是一个最大独立集，我们据此构造一种着色<math>f</math>。首先，<math>f</math>给<math>S</math>中所有顶点均染上颜色1（这必定不会造成冲突）。其次，<math>f</math>给其余顶点分配互异且非1的颜色。容易看出<math>f</math>仅仅使用了<math>1 + |V \setminus S| = 1 + n - \alpha(G)</math>种颜色，因此着色数必定不少于该数。
{{Collapse bottom}}

== 计算复杂性 ==
求最大独立集是[[计算机科学]]中的重要问题，因为许多现实场景可以抽象成该问题。例如，人们希望组织一场会议，候选的某些演讲者之间或有嫌隙，不愿同时出席。可以将这种候选人之间敌意关系抽象成一张图，两个候选人间有边当且仅当二者不和。那么，最终的演讲者名单就应当是这张图的一个独立集。会议组织者希望邀请尽可能多的演讲者以充实内容，也就相当于寻找图中的最大独立集。

然而，[[计算复杂性理论]]在以下两方面的进展暗示该问题难以求解。

=== 判定版本的NP完备性 ===
考虑最大独立集问题的判定版本：给定一张图和一个目标<math>I</math>，图中是否''存在''一个独立集的基数不小于<math>I</math>？在先前的例子中，相当于：会议组织者预先设定了一个目标邀请人数，问这个目标能否实现？其实，判定版本并不比原始版本简单。假设我们能够高效解决判定版本，那么也可以借助自归约性质（self-reducibility），相对高效地解决原始版本。

最大独立集问题的判定版本是[[NP完备]]的，这意味着，除非<math>\textsf{P} = \textsf{NP}</math>（而人们普遍相信这是不可能的），否则不存在确定性多项式时间算法解决之。其完备性的证明可以参见<ref>{{Cite book|title=''Introduction to the Theory of Computation'', Third Edition|last=Sipser|first=Michael|publisher=Cengage Learning|year=2013|isbn=978-1-133-18779-0|location=|pages=pp. 311-313}}</ref>。

=== 优化版本的不可近似性 ===
考虑最大独立集问题的优化版本：给定一张图<math>G</math>，计算<math>\alpha(G)</math>。该问题是[[MAXSNP]]完备的，这意味着，除非<math>\textsf{P} = \textsf{NP}</math>，否则不存在确定性多项式时间算法能以任意精度近似之（PTAS）。

还可以证明：假若存在某个高效算法能以某常数<math>c > 0</math>为[[近似比]]计算该问题，那么就能据此构造出一个以任意精度近似计算该问题的高效算法（PTAS）。结合前面的结论可知：除非<math>\textsf{P} = \textsf{NP}</math>，否则不存在高效算法能以常数倍近似计算该问题。<ref>{{Cite book|title=''Computationaly Complexity''|url=https://archive.org/details/computationalcom0000papa|last=Papadimitriou|publisher=Addison Wesley Longman|year=1994|isbn=0-201-53082-1|pages=pp. 309-322|first=Christos H.|location=}}</ref>

==参考资料==
<references />
[[Category:图论]]
[[Category:NP完全问题]]