图着色 · 冲突建模、启发式与精确解
一批考试要排进最少的时间段，同一个学生选的两门课不能同时考；一批变量要塞进最少的寄存器，同时活跃的两个变量不能共用一个。这两个问题是同一个问题：把对象画成顶点、冲突画成边，「资源分配」就成了图着色 (graph coloring)——相邻顶点异色，目标是最少的颜色数，即色数 χ。理论侧的定理体系（χ 的上下界、Vizing、list coloring、完美图）见 着色：顶点、边、列表与完美图；本系列走的是另一条线：χ 怎么算、算不动时怎么近似、以及哪些结构上它突然变容易。
路线分四段。先把「问题→冲突图」的翻译练熟；然后是多项式启发式——贪心着色的全部变数都在顶点序里，从 Welsh–Powell 的度降序、smallest-last 的退化序，到不预排序、按饱和度临场挑点的 DSATUR；接着面对 NP-hard 的本体，用回溯 + 剪枝在小图上求精确 χ，看剪枝把搜索树砍掉多少；最后是两个结构特例：区间图上贪心直接最优（会议室分配），以及编译器寄存器分配把「化简—选色—溢出」做成一个循环。每页的算法都预先展开成帧序列，可单步、可回退、可对照高亮代码行。
着色问题很少以「图」的面目出现；第一步永远是找出「什么与什么冲突」。
冲突建模：从排考到色数
着色问题很少以「图」的面目出现。本页用一张 8 门课的排考图完成第一步翻译：课程是顶点、共同考生是边、时间段是颜色，最少时段数就是色数 χ；再给出下界 ω 与上界 Δ+1 的用法，以及同一套翻译在频段、地图与寄存器上的建模清单。
贪心着色本身没有变数，变数全在「先给谁着色」；两页分别处理静态序与动态序。
顶点序：贪心的全部变数
贪心着色没有可调参数，唯一的输入是顶点序；换一个序，用色数可以差到任意远。本页统计 100 个随机序的用色分布，再考察两种静态启发式：Welsh–Powell 度降序，与保证用色 ≤ degeneracy + 1 的 smallest-last 退化序。
DSATUR：按饱和度临场挑点
静态序在着色开始前就定死，过程中积累的冲突信息全被浪费。DSATUR 每步临场挑饱和度（邻居已占的颜色种数）最大的点上色：二部图上可证恰用 2 色；50 张 9 点随机图上全部命中 χ，下标序贪心只有 36 张。
一般图上算 χ 是 NP-hard；能做的是把指数搜索树剪到可忍受。
精确解：回溯、剪枝与对称
求色数 χ 拆成一串「k 种颜色够不够」的判定，判定版本是 NP-complete，可依赖的只有回溯加剪枝。对称破缺把颜色换名的等价分支整族剪掉；实测它在判定成功时一个结点也不省，全部威力都在证明不可行上。
结构性假设让着色突然变容易——区间图上贪心即最优；寄存器分配则把着色做成工程闭环。
区间图：贪心直接最优
会议是时间轴上的区间，撞期是边，这样的冲突图叫区间图。按开始时间排序做贪心，用房数恰等于最大同时进行数 ω，一般图上 NP-hard 的色数计算在这里塌成一次排序；换成「长会优先」的时长降序，峰值 2 的日程却会开出 3 间房。
寄存器分配：着色的工程闭环
变量是顶点，同时活跃是边，k 个寄存器就是 k 种颜色。样本程序的冲突图是 K₅ 少一条边、χ = 4；Chaitin 化简循环在 k = 3 卡死，按 cost/deg 溢出 n，重建后 3 色装完——图着色在编译器里的工程闭环。
启发式、精确解与结构特例的分工
相关链接
- 着色：顶点、边、列表与完美图 本站 理论侧：χ 的上下界、皇冠图坏序、Vizing 定理、list coloring 与完美图；本系列的算法都在回答那页提出的问题。
- 平面图与四色定理 本站 着色理论最著名的结构特例：平面性把 χ 压到 4。
- Wikipedia — Graph coloring en.wikipedia.org 术语、复杂度结果与应用的索引式总览。
- Brélaz (1979) — New methods to color the vertices of a graph doi.org DSATUR 的出处：按饱和度动态挑点的贪心。
- Chaitin et al. (1981) — Register allocation via coloring doi.org 把寄存器分配建模成图着色的奠基论文；化简循环出自此处。