图论算法：极大团与独立集

约 732 个字 预计阅读时间 2 分钟

本页面笔记可能超过了正常《运筹学》课程所教授的图论的范畴。放在这里更多是为了自我总结与概念速查。

团的概念｜极大团

在图论中，“团”（Clique）是一个节点的集合。其定义为：

一个无向图 \( G = (V, E) \) 节点的子集 \( C \subseteq V \)，若其中任意两个不同的顶点都通过一条边直接相连，则称 \( C \) 为图 \( G \) 的团。

• 完全子图：团对应的子图是一个完全图（所有顶点两两相连）。
• 大小：团的大小是其中包含的顶点数量。

概念	定义
极大团（Maximal Clique）	不被其他更大的团包含的团，即无法通过添加新顶点来扩展为更大的团。
最大团（Maximum Clique）	图中顶点数量最多的团。其大小称为图的团数（Clique Number），记为 \( \omega(G) \)。

比如，一个三角形的三个顶点就构成了一个团。若图是二分图，同一个集合内的点之间互不相连，那么这个图极大团的大小为2（仅边连接的顶点对）。

---

独立集

你可以把独立集视为某种“团”的对偶。我们对图中的独立集 (Independent Set) 给出定义。

对于一个无向图 \(G = (V, E)\)，如果一个节点集合 \(C \subseteq V\)，同时这个节点集合中的任意两个节点间都没有边相连，那么 \(C\) 就构成了一个独立集 。

有了这个定义，我们可以引出更多的概念：

最大加权独立集（Maximum Weight Independent Set, MWIS）

在加权图 \( G = (V, E, w) \) 中 （每一个节点都有一个权重），寻找一个顶点子集 \( S \subseteq V \)，满足：

1. \( S \) 是独立集（任意两顶点间无边）；

2. \( S \) 的权重和 \( \sum_{v \in S} w(v) \) 最大。

最大加权团（Maximum Weight Clique, MWC）

在加权图 \( G = (V, E, w) \) 中，寻找一个顶点子集 \( C \subseteq V \)，满足：

1. \( C \) 是团（任意两顶点间有边）；

2. \( C \) 的权重和 \( \sum_{v \in C} w(v) \) 最大。

如果你的注意力比较集中，你或许发现了什么 ...

我们定义“补图”(Conplementary Graph)。什么意思呢。就是对于原来一个图而言，我们让所有的节点都保持不变，并且将这些节点两两相连，构成完全图。

然后，对这张完全图，如果原先图中两个节点之间存在边，则在完全图中，这一条边就要删去；如果原先图中两个节点之间不存在边，那么在完全图中，这两个节点之间就有一条边相连。

一个三个节点的图，\(\{1,2,3\}\)，边为 \(\{(1,2), (1,3)\}\)，那么它的补图中的边就是 \(\{(2,3)\}\)

原图的加权最大团，与补图的加权最大独立集实际上是等价的。

补充 ...