DSATUR · 饱和度

DSATUR：按饱和度临场挑点

顶点序：贪心的全部变数把贪心着色的表现全部押在顶点序上，但那里的序（下标、度降序、smallest-last）都在第一个点落色之前就已定死。着色一旦展开，图上会不断产生更贴身的信息：某个点的邻居已经占了几种颜色，它的安全选择还剩几个。静态序对这些信息一概用不上，等于把过程中「谁的处境最危险」白白扔掉。Brélaz 在 1979 年提出的 DSATUR（degree of saturation 的缩写）把挑点推迟到每一步临场进行，用的正是这份实时信息 [1]。

1 · 饱和度与临场挑点

定义 1.1（饱和度） 部分着色下，未着色顶点 $v$ 的饱和度（saturation degree） $\operatorname{sat}(v)$ 是 $v$ 的邻居中已出现的不同颜色数。已着色的顶点退出比较。

DSATUR 的全部改动只在挑点：每步在未着色顶点里挑 $\operatorname{sat}$ 最大者（平手取度大者，再平取下标），给它上邻居未占的最小编号颜色。上色规则与朴素贪心一字不差，换掉的只是「先给谁着色」这个答案的来源：静态序在开局把它一次性算完，DSATUR 每步重新回答。

按饱和度挑点的理由在于它度量的就是危险本身： $\operatorname{sat}(v) = k$ 意味着 $v$ 的调色板已被邻居排除了 $k$ 种颜色，再拖下去最可能被迫开新色的就是它。度只是这种危险的静态代理（邻居多，将来可能被挤得厉害），饱和度是它的实时读数。先处理最危险的点，颜色的碰撞发生在选择尚且宽裕的早期，晚期反而从容。

2 · 单步执行

core/dsatur.ts 的 dsaturFrames 把整个过程预展开成帧序列：每处理一个点出三帧（锁定饱和度最高的点、收集其邻居已占的颜色、上色并更新邻居的饱和度），加上首尾各一帧快照，排考图的 8 个点合计 26 帧。值得盯住的是上色那一帧的连锁反应：只有当新颜色第一次出现在某个邻居的视野里，那个邻居的饱和度才会加一，于是「下一个被挑中的点」常在一次上色之后换人——这是任何静态序都表达不出的行为。

图 2-1 · DSATUR 的单步执行。顶点下方的数字是该点当前的饱和度，橙色圆环是本步选中的点，调色板里 ✗ 为邻居已占、✓ 为本步选用。可切换样本图，观察一次上色如何推高邻居的饱和度、下一个被挑中的点如何随之改变；末帧的结论条把用色数与精确色数 χ 并排。

注 · 平手规则的口径。Brélaz 原文里饱和度平手时比较的是未着色子图中的度，core/dsatur.ts 的实现比较的是全图的度。把平手规则换成剩余度重跑一遍，本页样本图与 §4 那 50 张随机图的用色数没有任何变化，这处口径差异于是原样留下，只在此说明。

3 · 二部图上的已证保证

DSATUR 有一条朴素贪心给不出的保证：

定理 3.1 连通二部图上，DSATUR 恰用 2 色。

证明设第一个点染颜色 1。此后每一步，与已着色集合相邻的未着色点饱和度至少为 1，不相邻的点饱和度为 0；图连通保证前者始终存在，故被挑中的点总与已着色部分相邻，已着色区域自始至终连成一片。对这片区域保持归纳不变量：每个已着色点的颜色由它所在的二部侧唯一决定，与首点同侧者染 1、异侧者染 2。新选中的点，其已着色邻居全部落在对侧、同为一色，最小可用色恰好是本侧的那一种。颜色数从不超过 2。∎

非连通的二部图逐个连通片套用同一论证即可。皇冠图（完全二部图 $K_{m,m}$ 去掉一组完美匹配）是这条保证最有对比度的试金石：顶点序：贪心的全部变数里，同一张图存在把朴素贪心逼到 $m$ 色的左右交替坏序（ $m = 4$ 时实测用满 4 色），度降序也无从解救，因为皇冠图所有点同度、序退化回下标序。坏序的要害是接连处理互不相邻的一对点、让它们共享颜色，此后每处理一对就多一种禁色；而 DSATUR 在首点落色之后只会挑饱和度至少为 1 的点，即与已着色区域相邻的点，那个「不相邻的搭档」饱和度为 0，永远排不到前面。实测 $m = 4$ 与 $m = 6$ 的皇冠图上 DSATUR 都恰用 2 色。理论侧对皇冠图与 $\chi$ 上下界的完整讨论见着色：顶点、边、列表与完美图。

4 · 保证之外的实测

一旦离开二部图，DSATUR 就没有一般的最优性保证，可实测表现却顽固地好。Petersen 图（ $\omega = 2$ 、 $\chi = 3$ ）上它拿到 3 色；Grötzsch 图专为「团下界失效」而构造（无三角形、 $\omega = 2$ 却 $\chi = 4$ ），它也拿到 4 色。更成规模的对照是 50 张随机图 $G(9, 0.45)$ （seed 取 1 到 50）：DSATUR 全部 50 张命中 $\chi$ ，按下标序的朴素贪心只有 36 张命中，其中 14 张被 DSATUR 严格超过。

本页原计划在这批样本里找一张 DSATUR 失手的小图，挂在此节做反例，结果落空：50 张随机图全中，Grötzsch 也没能难住它。反例必然存在：DSATUR 是多项式时间的贪心，而算 $\chi$ 是 NP-hard，除非 P = NP，它不可能在所有图上都命中。但这样的图在 9 点规模的随机抽样里一张也没撞见；让 DSATUR 失手的最小图长什么样、这类图在随机图里的密度有多低，本页没有查到可靠口径，只能存疑。

5 · 参考文献

Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256.