backtracking · 对称破缺

精确解：回溯、剪枝与对称

启发式交出的方案只有上界的身份：用色数不超过某个数，但不附带「不能更少」的证明。带证明的 $\chi$ 要靠搜索。本页把这场搜索拆开看：先把优化问题化成一串判定，再给判定套上回溯框架，加一条针对颜色换名的剪枝，最后用实测数字检验剪枝在「回答是」与「证明否」两种结局下的表现。

1 · 色数的判定拆解

直接求 $\chi$ 是优化问题，标准做法是拆成一串判定：固定 $k$ ，问「 $k$ 种颜色够不够」。 $k$ 从下界 $\omega$ （最大团规模，团内各点必须两两异色）起递增，首个判定成功的 $k$ 就是 $\chi$ 。每一层只需回答是或否，回溯搜索天然适配这个形态。

判定版本没有多项式捷径可指望。「图能否 $k$ 着色」在 Karp 于 1972 年列出的 21 个 NP-complete 问题之中 [1]； $k \ge 3$ 时至今没有多项式算法，也普遍相信不存在。

作为起点的下界 $\omega$ 本身也靠不住。Grötzsch 图是现成的活教材：11 个点、20 条边，整张图没有一个三角形， $\omega = 2$ ， $\chi$ 却是 4。判 2 色失败、判 3 色也失败，答案比团下界高出两级；Mycielski 构造还能在保持无三角形的前提下把 $\chi$ 推到任意高。指望某种多项式可算的证书替代搜索，在一般图上走不通， $\chi > k$ 只能靠把 $k$ 色方案试尽来证明。团下界与 $\chi$ 的一般关系见着色：顶点、边、列表与完美图。

2 · 回溯框架

判定的主体是七行伪码，图 2-1 的代码面板与之逐行对应。顶点先按度降序排成固定序，度大的点约束多，先钉住它们能让矛盾尽早暴露；Brélaz 提出 DSATUR 的论文 [2] 里同时给出了精确算法，把静态的度降序换成按饱和度临场挑点，是同一思路的动态版。然后逐点推进：第 $i$ 个点从最小编号的颜色起逐个尝试，与已着色邻居撞色就换下一种；找到可用色就钉上，深入第 $i+1$ 个点；所有颜色试尽仍无出路，就撤销当前点的颜色，退回上一个点换色重来。全部点钉上即判定成功；第一个点的所有颜色都宣告失败，则搜索树穷尽， $\chi > k$ 。

度量搜索开销用两个计数：给某个点尝试一种颜色记一个结点（nodes），一次撤销记一次回溯（backs）。

图 2-1 ·

k

色判定的回溯搜索，逐帧展开，撞色时当前试色与冲突邻居标红。可选样本图与目标

k

，切换对称破缺开关对比 nodes 读数，即 §4 的两组对照数字；Grötzsch 图判 3 色全程 309 帧。

3 · 颜色换名与对称破缺

颜色只是名字。把一个合法方案里的 1 号色与 2 号色整体互换，得到的仍是合法方案，「1 红 2 蓝」与「1 蓝 2 红」是同一个解的两个名字。朴素回溯把它们当成不同分支分别走一遍：第一个点试 $k$ 种颜色，而这 $k$ 个分支两两等价，只是后续所有颜色跟着换名。

对称破缺（symmetry breaking） 的剪法只有一行：第 $i$ 个点试色时，编号至多到「已用最大色 + 1」为止。取旧色不受限制，开新色时只准开编号最小的那一种，反正新色之间可以互相换名，指定一种就够。这样第一个点只剩 1 种选择，第二个点至多 2 种，换名等价的整族分支在源头就不会生成。引擎里颜色从 0 编号，这条上限体现为 exact.ts 中的 limit = Math.min(k, maxUsed + 2)。

4 · 剪枝收益的不对称

写测试前的预期是对称破缺总能省结点，开关一开 nodes 全线下降。实测推翻了一半——判定成功时它一无所获：Grötzsch 图判 4 色，对称破缺开与关都是 24 个结点，一个不多一个不少。回头看原因很直白：试色本来就从小编号开始，一条不回头的成功路径每一步取的都是最小可用色，全程落在对称破缺允许的范围内；被剪掉的换名分支排在成功路径之后，根本轮不到展开。

它的全部威力在证明不可行上。Grötzsch 图判 3 色，开对称破缺 230 个结点，关掉 1371 个；轮图 $W_5$ 判 3 色，开是 15，关是 84。证明 $\chi > k$ 必须穷尽整棵搜索树，每一族换名分支都要逐一走完，剪枝砍掉的正是这棵必须穷尽的树的大半。

同一张 11 点的小图，回答「4 色可行」花 24 个结点，证明「3 色不可行」花 230 个。成本的落差是 NP 类的不对称性落在一张具体的图上的形状：可行的回答自带证书，判 4 色成功时那 24 步走出的着色方案本身就是证明；不可行没有已知的短证书，只能拿穷尽当证明。

5 · 参考文献

Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations (pp. 85–103). Plenum Press.
Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256.