070-图论-极大团

核心概述

极大团（Maximal Cliques）是无法再添加顶点使之仍为完全图的顶点集合；常用 Bron–Kerbosch（带主元与退化序）在无向图上枚举所有极大团，最坏 O(3^{n/3})，实际常更快。

原文引述

Description: Enumerate all maximal cliques in an undirected graph using the Bron–Kerbosch algorithm with pivoting (Tomita) and optionally degeneracy ordering. Time: Worst-case O(3^{n/3}); typically much faster in practice

展开阐述

定义与背景

• 团（clique）：图中任意两点相互连边的顶点子集。
• 极大团（maximal clique）：在当前图中无法再加入其他顶点仍保持完全图的团；与“最大团（maximum clique）”不同，后者指规模最大的团，仅输出一个。
• 目标：输出图中所有极大团 C，无重复且两两不可扩展。

适用场景：

• 社区/社交网络分析中的紧密子群检测；
• 约束满足/可满足性中的变量强关联子集识别；
• 补图上的“极大独立集”枚举（见关系一节）。

接口/数据结构（据常见实现）

• maximalCliques(G, report)
  • G：无向图，可用邻接表（vector）或位集（bitset/uint64_t 块）表示；
  • report(C)：回调，接收每个极大团的顶点集合；
• 若采用位运算：
  • 用位集表示候选集与邻接；交集与差集均为按位与/与非，能显著提升稠密图性能；
  • 对 64 位块进行分组以提升常数。

核心流程/要点（Bron–Kerbosch + 主元 + 退化序）

• 框架维护三集合 (R, P, X)：
  • R：当前构造中的团；
  • P：可扩展的候选顶点（与 R 全连）；
  • X：已处理过、需避免重复的顶点。
• 终止与输出：
  • 当 P 与 X 同时为空时，R 为一个极大团，调用 report(R)。
• 主元选择（Tomita/pivoting）：
  1. 在 P∪X 中选择主元 u，使 |P \ N(u)| 最小；
  2. 仅对 P \ N(u) 中的顶点递归展开：对每个 v∈P\N(u)，递归 BK(R∪{v}, P∩N(v), X∩N(v))，随后将 v 从 P 移至 X；
  3. 该剪枝能显著减少分支数量，改善平均性能。
• 退化序（degeneracy ordering）：
  • 先按退化序（每次剥离度最小顶点）遍历顶点，令每次递归中的 P 尺寸更小，从而进一步提升性能；
  • 该技术对稀疏图尤为有效。

实现细节：

• 集合结构选择：
  • 稀疏图：使用有序容器/数组，交集通过双指针或标记；
  • 稠密图：使用位集，交与差均摊为字宽操作；
• 递归顺序：
  • 对 P\N(u) 的遍历可按启发式排序（如度数）降低平均分支；
• 去重保证：
  • 通过 X 集合确保同一极大团不会被重复输出；
• 回调式输出：
  • 极大团数量可能为指数级，建议即时输出或流式处理，避免存储爆炸。

复杂度与边界条件

• 时间复杂度：最坏 O(3^{n/3})；加入主元与退化序后，实际表现通常远优；
• 空间复杂度：O(n) 递归栈 + O(n)～O(n^2) 集合存储（取决于表示与密度）；
• 输入约束：
  • 图需为无向、无自环；重边可忽略为单边；
  • 空图返回空集（无团或仅空团，通常不输出空团）；
• 工程边界：
  • n≈60–200 量级时位集实现常可接受（依机器与常数）；更大图需利用稀疏性与强剪枝或转化问题。

变体/扩展与关系

• 与“最大团（maximum clique）”：
  • 若仅需规模最大者，采用分支限界/位运算优化的最大团算法（见 071-图论-最大团）；
• 与“最大独立集”：
  • 在补图中，最大独立集等价于最大团；极大独立集枚举等价于补图的极大团枚举（见 072-图论-最大独立集）；
• 与覆盖/染色问题：
  • 极大团可作为上界/下界构造的一部分；与染色上界/团数下界有经典联系；
• 与匹配/点覆盖：
  • 问题性质不同；二分图中“最大匹配—最小点覆盖—最大独立集”存在对偶结构（参考 067-图论-HopcroftKarp、075-图论-最小点覆盖），但一般图上不再成立。

正确性要点与不变式

• R 的团性质不变式：递归中 R 始终是团；P 与 X 中的顶点均与 R 全连；
• 完备性：当 P∪X=∅ 时，R 已无法扩展，必为极大团；
• 无重复性：每一步将处理过的 v 从 P 移至 X，避免重复输出相同的团；
• 主元正确性：限制扩展到 P\N(u) 不会遗漏任何极大团（Tomita 证明）。

与相邻技术的对比与取舍建议

• 需要“全部极大团”：选 Bron–Kerbosch（主元+退化序+位运算）；
• 只需“最大团”：选分支限界的最大团算法（071-图论-最大团）；
• 需要“极大独立集”：在补图中应用同样流程（072-图论-最大独立集）。

关联节点

• 071-图论-最大团
• 072-图论-最大独立集
• 067-图论-HopcroftKarp