团与独立集

形式陈述 ​

设 $G=(V,E)$ 是有限简单无向图。顶点集 $C\subseteq V$ 称为团，若任意不同的 $u,v\in C$ 都有 $uv\in E$；等价地，$C$ 诱导的子图公理库子图Subgraph顶点集和边集分别取原图子集且保持端点关系所得的图。是完全图公理库完全图Complete graph任意两个不同顶点之间都有边的简单无向图。。顶点集 $I\subseteq V$ 称为独立集，若任意不同的 $u,v\in I$ 都有 $uv\notin E$。最大团与最大独立集的大小分别记为

$$\omega (G)=max\{|C|:C\text{ 是 }G\text{ 的团}\},\alpha (G)=max\{|I|:I\text{ 是 }G\text{ 的独立集}\}.$$

“极大”与“最大”必须分开：团或独立集若不能再加入任何顶点而保持性质，称为极大的；最大对象则在所有同类对象中基数最大。每个最大对象都极大，反向一般不成立。若 $\bar{G}$ 是在同一顶点集上把边与非边互换得到的补图，那么

$$C\text{ 是 }G\text{ 的团}⟺C\text{ 是 }\bar{G}\text{ 的独立集},\omega (G)=\alpha (\bar{G}).$$

此外，$I$ 是独立集当且仅当 $V\setminus I$ 是顶点覆盖，因此有限图还满足 $\alpha (G)+\tau (G)=|V|$，其中 $\tau (G)$ 是最小顶点覆盖大小。

直觉 ​

团与独立集问的是同一件事的两个极端：挑出一组顶点，只观察组内关系，能否做到每一对都有边，或每一对都没有边。补图把“有联系”与“无联系”逐对翻转，所以两种对象并非松散类比，而是严格对偶。这个视角也解释了为什么团与连通子图差别很大：连通只要求任意两点之间能沿若干条边抵达，团却要求每一对顶点直接相邻，中间人不能弥补缺失的边。

极大性则是局部停止条件：眼前没有一个顶点可加入。最大性是全局最优条件：不存在规模更大的另一种选择。贪心地不断加入合法顶点总能得到某个极大集合，却没有理由得到最大集合；二者之间的落差正是最大团、最大独立集等优化问题困难性的来源。

例子与边界 ​

在五点路径 $P_5$ 中，每条边都形成大小为 $2$ 的团，且不存在三角形，所以 $\omega (P_5)=2$；隔点选择第 $1,3,5$ 个顶点得到大小为 $3$ 的独立集，故 $\alpha (P_5)=3$。五圈 $C_5$ 没有三角形，也不能选出三个两两不相邻的点，因此 $\omega (C_5)=\alpha (C_5)=2$；它与自己的补图同构，正好显出上述对偶。

若完全二分图 $K_{m,n}$ 的两侧均非空，跨侧任意两点相邻，同侧任意两点不相邻，所以最大团只有一条边的两个端点，而任一整侧都是独立集，$\alpha (K_{m,n})=max\{m,n\}$。在三点路径 $P_3$ 中，只取中点是极大独立集：两个端点都不能再加入；但两端点组成大小为 $2$ 的最大独立集。这给出了“极大不等于最大”的最小直观反例。

空集按定义同时是团和独立集，单点集也同时具有两种性质。这里的独立集专指图论对象，不应与拟阵中满足遗传与交换公理的独立集混为一谈；图的边集确实可诱导图拟阵，但那里的元素是边，概念层级不同。

推论与应用 ​

色数公理库色数Chromatic number使图存在合法顶点着色所需的最少颜色数。可等价看成把顶点集分割成尽量少的独立集，因此 $\omega (G)\le \chi (G)$：一个团中的顶点必须使用不同颜色。任意 $K_t$ 都迫使树分解公理库树分解与树宽Tree decomposition · Treewidth用按树组织的顶点袋覆盖图，并以最小最大袋大小衡量图偏离树结构的程度。的某个 bag 同时容纳这 $t$ 个顶点，故 $\mathrm{tw}(G)\ge \omega (G)-1$。顶点覆盖公理库顶点覆盖Vertex cover与每条边至少一个端点相交的顶点子集。与独立集的补集关系连接两种优化目标，Ramsey 定理公理库Ramsey 定理Finite Ramsey theorem足够大的有限结构中必然出现给定大小的同质子结构。则说明大图不可能同时避开大团与大独立集。

在应用中，社交网络里的两两相识群体可建模为团，互相冲突的任务中可同时选择的一组任务可建模为独立集。不过模型是否可信取决于边的含义：相关性、可达性或共同邻居都不能自动替代“两点之间确有一条边”。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，§1.1 与补图、团、独立集相关内容。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，Chs. 1 and 5，independent sets, cliques, coverings, and colorings。