最大独立集（Maximum Independent Set, MIS）：在无向图中选取两两不相邻的顶点且规模最大，常用“分支限界 + 上界着色 + 位集优化”，或在补图转化为最大团统一求解。
Description: Find a largest set of pairwise non-adjacent vertices (maximum independent set). NP-hard in general; branch-and-bound with bitset and heuristic ordering is common. Equivalent to maximum clique on the complement graph. Time: Exponential in worst case (practical with pruning/bitset)
展开阐述
-
定义与背景
- 独立集：任意两点之间无边的顶点子集；最大独立集要求规模全局最大。
- 与相关概念：在补图中，独立集等价于团；因此 MIS 等价为补图上的最大团问题（见 071-图论-最大团）。
- 应用场景：任务调度的互斥集合选择、频谱分配中的干扰规避、约束满足中的不相容变量子集优化。
-
接口/数据结构（据实现习惯）
- maximumIndependentSet(G)：返回最大独立集的顶点集合（或大小），G 为无向简单图。
- 图表示：
- 用邻接位集（bitset/uint64 块）表示顶点邻接与候选集，支持按位与/与非的快速交并；
- 稀疏场景可用邻接表，但需要小心上界估计与集合维护的常数。
- 状态：当前独立集 C，与之不相邻的候选集 P（即 P 与 C 两两不相邻）。
-
核心流程/要点（两路线：直接搜索 vs 补图最大团）
- 直接搜索（分支限界 + 上界）
- 上界估计：对 P 做贪心着色或其他可行上界估计，得到 upper_bound(P)；
- 剪枝：若 |C| + upper_bound(P) ≤ |best|，则无望超过当前最优，剪枝；
- 选择分支点 v ∈ P（常按度或着色顺序）：递归“取 v”（C←C∪{v}, P←P∩非邻(v)）与“不取 v”（P←P{v}）。
- 补图转化（推荐统一框架）
- 在补图 Ḡ 上运行最大团（同色界框架，参见 071-图论-最大团），可重用成熟实现；
- 由最大团解在原图中直接得到最大独立集。
- 位集优化
- 候选集与邻接操作用位集实现；结合按块统计与快速定位置位位，降低常数。
- 不变式
- P 始终保证与 C 两两不相邻；回溯时需恢复集合语义。
- 直接搜索（分支限界 + 上界）
-
特例与结构性对偶（在二分图）
- König 定理：二分图上 |最小点覆盖| = |最大匹配|，且 |最大独立集| = |V| − |最小点覆盖|；
- 实践路径：先用 067-图论-HopcroftKarp 求最大匹配，再按 075-图论-最小点覆盖 线性恢复覆盖，最终得到 MIS 大小与具体点集；亦可经流模型（如 057-图论-Dinic最大流）求匹配。
-
复杂度与边界条件
- 一般图：NP-难，最坏指数级；色界/主元/位集可显著加速中等规模实例；
- 图要求：无向简单图；自环忽略；重边不影响独立性语义；
- 规模与实现：位集块宽（如 64 位）与顶点上限相关；注意集合扫描顺序与缓存友好性。
-
变体/扩展与关系
- 最大团：补图互换（071-图论-最大团），共用搜索/上界框架；
- 极大结构：若只需“不可再扩展”的集合而非最大规模，可参见极大团/极大独立集的枚举思路（见 070-图论-极大团）。
-
正确性要点与直觉
- 上界安全：着色数为“还能再放入的顶点数”的上界；剪枝不丢最优；
- 对偶一致：补图最大团⇔原图最大独立集；在二分图上还满足与最小点覆盖/最大匹配的数量对偶。
-
与相邻技术的对比与取舍建议
- 需要规模“最大”的独立集：使用本框架或转化到补图最大团（复用 071-图论-最大团）；
- 仅需求“全部极大”而非“最大”：考虑极大团/独立集枚举（070-图论-极大团）；
- 特定为二分图：优先匹配系方法，按 067-图论-HopcroftKarp 与 075-图论-最小点覆盖 得到更强结构与线性恢复。