第8章 收尾攻坚：着色与独立集

第 8 章 · 收尾攻坚：着色与独立集

章节摘要：前几场的战役都有"一口气跑到底"的多项式算法，本章的攻坚对象却换了一副面孔：给图的顶点着色，使相邻者异色、颜色数还要最少——判断"能否用很少的颜色着完"这类问题，计算难度陡增，成了理论计算机科学的分水岭。与之共舞的是独立集与顶点覆盖：选出彼此不相邻的顶点、或用最少的顶点触到所有的边，它们与着色同属"极值子集"家族，彼此之间又以补图与对偶关系环环相扣。本章把这些问题的定义、局部性质、精确求解与近似策略讲透，并借四色定理的故事呈现"计算机辅助证明"这一现代数学事件。

本章知识点清单

读完本章，下列考核点应当能对答如流：

1. 给出色数与正常着色的定义，计算路、圈、完全图、二分图的色数并说明理由。
2. 用贪心着色求得着色上界，解释"顶点次序不同结果不同"及最坏情形的界。
3. 区分色数判定类问题与多项式可解问题的复杂度差异，陈述判断性问题的表述方式。
4. 证明"最大团等于补图的最大独立集"，并在团与独立集之间互相翻译。
5. 证明二分图上最大匹配与最小顶点覆盖的对偶等式（第 7 章 König 定理的收口）。
6. 用分支限界或近似策略求解中小规模的着色与覆盖实例，说明近似保证。

核心概念速览

金句：着色问题的难，不在于颜色多贵，而在于"最少"二字——它问的是整个解空间的下确界，而非一条可行解。

子章节导航

第 1 节"图着色：冲突调解与四色悬念"从排冲突的实务场景切入，建立色数概念，手算各类经典图的色数，实现贪心与回溯两种求解器，最后讲四色定理的故事——一段横跨世纪的悬案与计算机辅助证明的争议。

第 2 节"独立集与顶点覆盖：哨所选址的权衡"处理"选点"问题：互不冲突的顶点最多选多少（独立集）、触达全部边的顶点最少要几个（覆盖）。两者一补一素，与着色、团问题构成极值子集的家族谱系，本节把谱系图补完整。

两节之间的攻防线

一句话论点：着色是"分组不冲突"，独立集是"选点不冲突"，覆盖是"设卡不断链"——同一族极值问题，难处同源，解法互通。

   图 G                    补图
   │                        │
   ├─ 最大独立集 ←──互补──→ 最大团
   │        ↑补集
   │   最小顶点覆盖
   │
   └─ 着色 = 把顶点切成若干独立集
              （每种颜色内部即一个独立集）
              → 着色是独立集的"打包出售"
​

前置知识与后续延伸

前置：第 1 章的图类词汇（完全图、二分图、补图）、第 7 章的 König 定理（本节为其收口）、基本的组合计数直觉。复杂度相关的严谨定义属于理论计算机科学课程，本章按"计算难度的分水岭"的直觉层面讲授，够用即止。

后续延伸：着色是寄存器分配、排课、频谱分配的模型；独立集与覆盖支撑设施选址、纠错码、网络安全等场景；本章建立的"难解问题 + 近似策略"工作流将在第 10 章的工程检阅里接受实战检验。想深入计算复杂性理论的读者，本章是通往归约与难解性专题的第一级台阶。读本章尤其要管理好心理预期：前面各章的算法都有"一次跑通"的爽快，本章的精确解却常常要靠回溯与剪枝硬啃——这不是退步，而是抵达了问题难度的真实地形。学会与难解问题共处（近似、特款、参数化、启发式四件套轮番上阵），是本章比任何具体算法都重要的收获。