最大团（Maximum Clique）：在无向图中寻找规模最大的完全子图，常以“分支限界 + 贪心着色上界（Tomita/色界法）+ 位集加速”实现以在实际数据上获得高效表现。
Description: Maximum clique via branch-and-bound with greedy coloring upper bounds (Tomita-style algorithm). Time: Worst-case O(3^{n/3}); typically much faster
展开阐述
-
定义与背景
- 团（clique）：任意两点均有边相连的顶点子集。
- 最大团 vs 极大团：最大团要求规模全局最大；极大团仅要求“不可再扩展”。两者语义不同，极大团可能有多个且不保证最大（参见 070-图论-极大团）。
- 应用背景：社区挖掘中的高密度子群、约束满足中强耦合变量集、作为图着色/覆盖/独立集问题的下界或对偶参考。
-
接口/数据结构（据实现习惯）
- maxClique(G)：返回最大团的顶点集合（或其大小），G 为无向简单图。
- 图表示：
- 稠密图：邻接位集（bitset/uint64 块）更高效，交/差/与非为按字并行；
- 稀疏图：邻接表也可，但上界估计与交集维护需小心。
- 状态维护：当前团 C，候选集 P（与 C 完全相邻的顶点）。
-
核心流程/要点（分支限界 + 主元/退化序 + 位运算）
- 贪心着色上界（色界）
- 对候选集 P 做一次顺序着色（按度序或启发式顺序）；得到每个点的颜色编号，上界 upper_bound(P) 为所用颜色数。
- 剪枝：若 |C| + upper_bound(P) ≤ |best|，则本分支不可能超过当前最好解，直接回溯。
- 分支顺序与主元选择
- 典型策略：按着色编号从大到小（或逆序）取点 v ∈ P 优先搜索“希望带来更大上界改善”的分支；
- 主元/退化序可减少分支数量，提升剪枝命中率。
- 递归扩展与回溯
- 选择 v 后：C ← C ∪ {v}，P ← P ∩ N(v)；递归求解；
- 回溯时将 v 自 P 移除，尝试下一个候选。
- 位集优化
- P 与各 N(v) 用位集表示；交集/差集均为字级与/与非；
- 结合按块统计/快速找第一个 1，可显著降低常数。
- 终止与更新
- 递归叶子处更新全局 best；返回时保持不变式：P 始终为“与 C 完全相邻”的集合。
- 贪心着色上界（色界）
-
复杂度与边界条件
- 理论最坏 O(3^{n/3})；实际在有力剪枝与位运算加速下通常远小于此；
- 图要求：无自环；重边对团性质无影响；
- 稠密/稀疏：稠密图更适合位集；极稀疏图可先做度约简；
- 数值与规模：位运算实现需注意块大小（如 64 位）与图规模上限的块数管理。
-
变体/扩展与关系
- 与最大独立集：在补图中，最大独立集等价于最大团（见 072-图论-最大独立集），两者可共用“色界 + 分支限界”框架；
- 与极大团：若需求是“枚举所有极大团”，应切换到 Bron–Kerbosch 及其主元/退化序优化（见 070-图论-极大团）。
-
正确性要点与不变式
- 不变式：候选集 P 保证与当前团 C 完全相邻；
- 上界正确性：顺序着色所得颜色数为可扩展大小的上界（每色至少取 1 个）；
- 剪枝安全性：当 |C|+upper_bound(P) 不可能超过 |best| 时剪枝不丢最优解。
-
与相邻技术的对比与取舍建议
- 仅需“最大规模的一个团”：使用本算法；
- 需要“全部极大团”：选 Bron–Kerbosch（070-图论-极大团）；
- 需要“最大独立集”：转到补图按同一框架处理（072-图论-最大独立集）。