冲突建模：从排考到色数

期末有 8 门课要安排考试，时间段越少越好；唯一的硬约束是同一个学生选修的两门课不能排在同一时段。题面里没有「图」字，翻译却只有一步：把课画成顶点，把「有学生同时选了这两门」画成边，时间段就成了涂在顶点上的颜色。本系列后面的每一页处理的都是翻译完成之后的事，本页先把这一步立起来。

1 · 从排考到色数

把对象画成顶点、「不能共用同一份资源」画成边，得到的图叫冲突图 (conflict graph)。在冲突图上给每个顶点分配一种颜色并要求每条边两端异色，这样的分配是一个正常着色 (proper coloring)；能办到的最少颜色数是这张图的色数 (chromatic number)，记 $\chi$。排考问题至此变成一句话：最少时间段数等于冲突图的 $\chi$。

颜色在这套语言里只是「互异资源」的代号，时间段、频段、寄存器都能充当。着色自身的定理体系（$\chi$ 的更多上下界、Vizing 定理、list coloring、完美图）见 着色：顶点、边、列表与完美图；本页只从中取立刻能用的一小截：夹住 $\chi$ 的一对界。

2 · 排考图上的上下界

下界来自团 (clique)：一组两两相邻的顶点必须两两异色，最大团的规模 $\omega$ 于是给出 $\chi \ge \omega$。上界来自最朴素的算法：把顶点排成任意的序，逐个取「邻居尚未占用的最小编号颜色」；轮到任何顶点时，它已着色的邻居至多 $\Delta$ 个（$\Delta$ 是最大度），占掉至多 $\Delta$ 种颜色，编号 1 到 $\Delta + 1$ 里必有空闲。两头合起来：

本页的样本图有 8 门课、11 条冲突边：数学、物理、化学两两冲突，历史、地理、政治两两冲突，生物与化学、地理各有共同考生，英语同时连着数学、历史、生物。两个三角形给出 $\omega = 3$，最大度 $\Delta = 3$ 给出上界 4，两界夹出 $\chi \in \{3, 4\}$。实际 $\chi = 3$，上界不紧：不需要任何聪明的顶点序，按下标序跑一遍贪心就拿到 3 色。

构造这张图时有一处落空的设计。英语被特意连进数学、历史、生物三个互不相干的群体，本意是让它成为把 $\chi$ 顶到 4 的钉子；实测 $\chi$ 仍是 3。回头看并不奇怪：英语的三个邻居两两之间没有边，彼此锁不住对方的颜色，英语总能蹭进某个既有时段。想靠一个顶点抬高 $\chi$，它的邻居自身得先互相牵制——三个邻居若构成三角形，加上这个顶点就是 $K_4$，$\chi$ 才真的到 4。

3 · 建模清单

同一套翻译适用的范围远超排考。判断一个问题能不能建模成着色，要回答的是三件事：顶点是什么对象，边记录哪一种冲突，颜色代表哪一份资源。

后两行各有下文。地图的冲突图是平面图，四色定理把 $\chi$ 压到不超过 4，是「结构让问题突然变容易」的极端例子；寄存器分配则是这张清单里工程味最重的一行：颜色数不再是要最小化的目标，而是硬件给死的常数，装不下时要把变量溢出到内存，着色成了一个更大循环里的一环。

4 · 色数的计算难度

翻译完成不等于问题解决：一般图上计算 $\chi$ 是 NP-hard 的，连「3 个时间段够不够」这样的判定都是 NP-complete。本系列后面的页面分两条路走。启发式一路在多项式时间内换一个不保证最优的用色数，起点是顶点序的实验——贪心的全部变数都藏在「先给谁着色」里；精确一路用回溯与剪枝在小图上求带证明的 $\chi$。排考图上 $\Delta + 1$ 不紧是常态而非例外，两条路回答的是同一个问题：贪心离 $\chi$ 差多远，差出来的部分怎么追回。