独立集

独立集（independent set）是无向图中的一个顶点集合，其中任意两个不同顶点都不相邻，也称稳定集。它描述一组没有内部冲突的选择：若边表示两项任务不能同时进行，那么独立集中的任务可以在这个冲突模型下同时选取。

在边为 $ab,ac,bc,cd,de$ 的图中，$\{a,e\}$ 是独立集，因为没有边 $ae$；$\{a,c\}$ 则不是，因为边 $ac$ 的两个端点都被选入。判断针对所选顶点之间是否有边，而不是它们在整张图中是否存在连接路径。

a、e构成独立集，尽管它们位于同一个连通分量。

极大独立集与最大独立集

设 $G=(V,E)$ 为有限无向简单图。集合 $I\subseteq V$ 独立，当且仅当诱导子图 $G[I]$ 没有边。若不能再加入任何外部顶点而维持独立，称为极大独立集；大小在全部独立集中达到最大者称为最大独立集，其大小记为 $\alpha (G)$。

每个最大独立集一定极大，否则还能加入一点增大其大小。但逆命题不成立。四叶星图的中心一个点已构成极大独立集，因为每片叶子都与中心相邻；四片叶子的集合却是更大的独立集，所以 $\alpha =4$，中心集合大小只有一。这也说明“再也加不进点”仅是局部停止条件，不是最大性证明。

空集总是独立，单顶点集合也独立；无边的 $n$ 点图有 $\alpha =n$，完全图 $K_n$ 在 $n\ge 1$ 时有 $\alpha =1$。这些结论依赖顶点间是否相邻，不依赖图的平面画法。

主例中的最大性

主图的三角形 $abc$ 内至多选一点，因为任意两点都有边；另两个点 $d,e$ 之间也有边，至多选一点。两块顶点集合分割全图，因此任何独立集至多有两点。已给出的 $\{a,e\}$ 达到二，故 $$\alpha (G)=2.$$ 还可选 $\{a,d\}$、$\{b,d\}$、$\{b,e\}$ 或 $\{c,e\}$，所以最大解不唯一。虽然 $c$ 度最高，选入它也能得到一个最大独立集；“每次挑最低度顶点”或“总排除最高度顶点”都不能仅由度数直觉获得全局正确性。

变式。 删除边 $ab$ 后，集合 $\{a,b,e\}$ 变成独立集。另一方面，剩余图中互不接触的边 $ac,de$ 各限制至多选一个端点，另有顶点 $b$，故独立集至多三，得到 $\alpha =3$。删边可能增加独立数；加边则不可能增加，因为旧有独立条件只会增加限制。

极大性给出的覆盖与数量下界

记 $N[v]$ 为 $v$ 及其全部邻居，称闭邻域。若独立集 $I$ 极大，则每个外部顶点都至少与 $I$ 中一点相邻。否则，若某个 $x\notin I$ 与所有已选点都不相邻，就能将它加入，违背极大性。因此极大独立集也是支配集，并满足 $$V=\bigcup _{v\in I}N[v].$$ 若全图最大度为 $\Delta$，每个闭邻域至多含 $\Delta +1$ 点。并集大小不超过各集合大小之和，得到 $$n\le \sum _{v\in I}\mathrm{\#}N[v]\le \mathrm{\#}I(\Delta +1).$$ 所以每个极大独立集、从而最大独立集都满足 $$\alpha (G)\ge \lceil \frac{n}{\Delta +1}\rceil .$$ 这里不要求邻域彼此不交；重叠只使求和高估并集，不影响上面的不等式。主例 $n=5,\Delta =3$，下界为二，恰与精确值相同。星图中该下界只有一，不保证找到最大的四叶集合。

补图与顶点覆盖

在补图中，原来的每一对不同非邻接点变为邻接点，所以 $I$ 在 $G$ 中独立，当且仅当它在 $\bar{G}$ 中构成团。从而 $\alpha (G)=\omega (\bar{G})$。

又因为独立集内部没有边，其补集 $V\setminus I$ 必至少包含每条边的一个端点，是顶点覆盖；反向同样成立。于是若 $\tau (G)$ 为最小顶点覆盖大小，就有 $\alpha (G)+\tau (G)=n$。主例的最大独立集 $\{a,e\}$ 对应最小覆盖 $\{b,c,d\}$，大小 $2+3=5$。这个互补操作改变的是选取对象的含义，不能把“选尽量多的不冲突点”和“选尽量少的覆盖点”的大小混成同一个数。