独立集

图中的独立集是指其中的一族两两不相邻的顶点, 换句话说, 是其补图中的团.

1定义

定义 1.1 (独立集). 图 $G=(V,E,d)$ 中的独立集是指子集 $I\subseteq V$, 使得对任意 $x,y\in I$, $x\ne y$, 不存在 $e\in E$, 使得 $d(e)=[(x,y)]$, 即 $[(x,y)]\notin d(E)$.

图 $G$ 的一个独立集如果不真包含于另一个独立集, 就说它是 $G$ 的极大独立集.

图 $G$ 所有独立集中基数最大者称为 $G$ 的最大独立集.

定义 1.2 (独立数). 图 $G$ 的最大独立集的基数 $\alpha (G)$ 称为图 $G$ 的独立数.

2例子

•	Ramsey 理论告诉我们, 如果有限图 $G=(V,E,d)$ 的顶点个数 $|V|\ge R(s,t)$, 而 $G$ 不含大小为 $s$ 的团, 则 $G$ 一定有大小为 $t$ 的独立集.
•	如果图能进行 $r$-染色使得无同色顶点相邻, 则同色的顶点均构成独立集. 特别地, 如果图 $G$ 的色数是 $\chi (G)$, 则 $\alpha (G)\ge |V|/\chi (G)$.

术语翻译

独立集 • 英文 independent set

独立数 • 英文 independence number