着色与划分：最少几种颜色？

Part 3”优”的前三站，我们学习了用最小代价连通所有节点（最小生成树）、在容量约束下输送最大流量（网络流）、以及把节点配成最优对（匹配）。现在来到 Part 3 的第四站——着色与划分：给图的节点涂上颜色，要求相邻节点颜色不同，问最少需要几种颜色？

这个问题听起来像是地图涂色游戏，但它的应用远不止于此。编译器需要把数十个变量塞进少量寄存器——同时活跃的变量不能共用同一个寄存器，这恰好是一个着色问题。大学排考试——有共同学生的课程不能安排在同一时间段，这也是着色。无线通信中，相邻基站不能使用同一频率——还是着色。图着色是”资源冲突消除”的通用数学模型。

算法范式：贪心（贪心着色）、回溯 + 剪枝（精确着色）

核心问题：最少需要几种颜色？

给定一张图 $G = (V, E)$ ， $n = |V|$ 个节点、 $m = |E|$ 条边。合法着色（proper coloring）是一个函数 $f: V \to \{1, 2, \ldots, k\}$ ，满足对每条边 $(u, v) \in E$ 都有 $f(u) \neq f(v)$ ——即相邻节点必须着不同颜色。

色数（chromatic number） $\chi(G)$ 是使图有合法着色的最小颜色数：

$\chi(G) = \min\{k : G \text{ 有合法 } k\text{-着色}\}$

核心问题可以拆成两个层面：

判定问题：给定 $k$ ，图能否 $k$ -着色？（当 $k \geq 3$ 时是 NP-complete）
优化问题： $\chi(G)$ 是多少？（NP-hard）

核心思路：从特殊到一般，从上界到精确

精确计算 $\chi(G)$ 是 NP-hard 的，但并非无路可走：

特殊图有封闭解：二部图 $\chi = 2$ ，完全图 $K_n$ 的 $\chi = n$ ，平面图 $\chi \leq 4$
上界定理告诉我们 $\chi$ 不会太大：贪心着色保证 $\chi \leq \Delta(G) + 1$ ，Brooks 定理加强为 $\chi \leq \Delta(G)$ （除两种极端情况外），其中 $\Delta(G)$ 是最大度
贪心算法在实践中往往给出接近最优的结果——关键是选择好的节点排序策略

思路很清晰：先用特殊结构获得下界和精确解，再用贪心策略逼近上界。

特殊图的色数

二部图 $\leftrightarrow$ 2-可着色

一个图是二部图（bipartite）当且仅当 $\chi(G) = 2$ （忽略孤立节点的情况，即至少有一条边时 $\chi = 2$ ；无边图 $\chi \leq 1$ ）。

回忆 Art. 1 (BFS/DFS) 中的关键结论：图是二部图 $\Longleftrightarrow$ 图不含奇数长度的环。BFS 逐层交替标记颜色（偶数层红色、奇数层蓝色），如果某条边两端同层（同色），则存在奇环，不是二部图。

这是图着色的”甜蜜起点”——判断 2-着色只需 $O(n + m)$ 的 BFS，是多项式时间可解的。但从 $k = 3$ 开始，情况剧变。

完全图 $K_n$

在完全图 $K_n$ 中，每个节点都与其他所有节点相邻。任意两个节点必须不同色，所以：

$\chi(K_n) = n$

这是色数的上界极端： $n$ 个节点的图最多需要 $n$ 种颜色，而完全图恰好需要这么多。

奇环

奇数长度的环 $C_{2k+1}$ （如 $C_3$ 三角形、 $C_5$ 五边形）需要 $\chi = 3$ 。直觉：用 2 种颜色交替着色，走到最后一个节点时它与第一个节点相邻——由于环长度是奇数，最后一个节点和第一个节点会被分配相同的颜色，冲突！必须引入第 3 种颜色。偶环则 $\chi = 2$ ，是二部图。

平面图与四色定理

平面图（planar graph）可以画在平面上使得边不相交。关于平面图的着色，有一个数学史上最著名的结论：

四色定理（Appel & Haken, 1977）：任何平面图都可以 4-着色，即 $\chi(G) \leq 4$ 。

这个定理在 1852 年被猜想，经过 124 年才被证明——而且证明依赖计算机枚举了 1936 种不可约构型，是数学史上第一个计算机辅助证明，引发了”这算不算证明”的哲学争论。

实际意义：任何地图着色问题（国家或行政区的相邻关系自然构成平面图）4 种颜色一定够。

色数小结

图类型	色数 $\chi$	判定/计算复杂度
无边图	1	$O(1)$
二部图	2	$O(n + m)$ （BFS）
偶环 $C_{2k}$	2	$O(n)$
奇环 $C_{2k+1}$	3	$O(n)$
树	2	$O(n)$
平面图	$\leq 4$	四色定理
完全图 $K_n$	$n$	$O(1)$
一般图	NP-hard	精确：指数时间

上界定理

知道 $\chi$ 在什么范围内，比精确计算容易得多。以下两个定理给出了实用的上界。

贪心上界： $\chi(G) \leq \Delta(G) + 1$

贪心着色按某个顺序逐个处理节点，每个节点分配”最小的、邻居没用过的颜色”。任何节点最多有 $\Delta(G)$ 个邻居（ $\Delta(G)$ 是图的最大度），所以邻居最多占用 $\Delta(G)$ 种颜色，第 $\Delta(G) + 1$ 种颜色一定可用。因此：

$\chi(G) \leq \Delta(G) + 1$

这个上界对任何图、任何节点排序都成立。但它通常不紧——大多数图可以用更少颜色。

Brooks 定理： $\chi(G) \leq \Delta(G)$

定理（Brooks, 1941）：如果连通图 $G$ 既不是完全图也不是奇环，则：

$\chi(G) \leq \Delta(G)$

直觉：贪心上界之所以需要 $\Delta + 1$ 种颜色，是因为存在一个节点的所有 $\Delta$ 个邻居恰好用了 $\Delta$ 种不同的颜色。但除了完全图（每个节点都和其他所有节点相邻）和奇环（结构太”刚性”），一般图总有足够的结构灵活性，让我们巧妙安排顺序来避免这种最坏情况。

Brooks 定理的证明构造性地给出了一种着色策略——它选择一个特殊的节点排序，使得贪心着色不超过 $\Delta$ 种颜色。关键步骤是找到两个不相邻的”根邻居”，从它们开始反向 BFS 排序，最后处理根节点。

贪心着色算法

基本贪心框架

贪心着色是最实用的着色方法。核心算法非常简单：

GreedyColoring(G, order):
    for each v in order:
        used = {color[u] : u ∈ N(v) and u already colored}
        color[v] = smallest non-negative integer not in used
    return color

给定 $n$ 个节点的图，遍历一遍节点（按某个顺序），每个节点看看邻居用了哪些颜色，选最小的没被用的。

时间复杂度： $O(n + m)$ ——每个节点处理时遍历其邻居表，总计遍历所有边两次。

空间复杂度： $O(n)$ ——存储每个节点的颜色。

贪心着色的结果完全取决于节点处理顺序。相同的图，不同的顺序可能给出不同的颜色数。

排序策略：顺序决定一切

贪心着色保证不超过 $\Delta + 1$ 种颜色，但好的排序策略可以做得更好。

策略 1：字母/自然序——最简单的基线，不做任何优化。结果完全取决于节点编号的巧合。

策略 2：最大度优先（Largest First）——按度数从大到小排列。直觉：高度节点的约束最多，先处理它们，给后续低度节点留更多灵活性。保证颜色数 $\leq \Delta + 1$ ，但对许多图可以做得更好。

策略 3：DSatur（Degree of Saturation，Brélaz 1979）——这是最重要的启发式。动态地选择下一个节点：每步选择饱和度最高的未着色节点。

饱和度（saturation degree）：一个未着色节点的已着色邻居中，使用了多少种不同的颜色
饱和度相同时，选度数最大的
度数也相同时，选编号最小的（打破平局）

为什么 DSatur 效果好？ 它优先处理”约束最紧”的节点——已经有最多不同颜色邻居的节点。这样可以尽早发现颜色冲突，减少”被迫引入新颜色”的情况。

DSatur 保证对二部图给出 2-着色。对一般图，它在实践中通常比静态排序好得多，虽然最坏情况下仍然可能不是最优的。

走查：三种策略对比

下面的交互组件展示贪心着色在同一张 8 节点图上的完整执行过程。切换不同的排序策略（字母序、最大度优先、DSatur），观察颜色数的变化。

贪心着色走查

排序策略：

步骤 1/10: 初始状态：8 个节点，13 条边。使用字母序策略。

1 / 10

注意关键差异：

字母序可能需要 4 种颜色——因为处理顺序不考虑图结构
最大度优先先处理高度节点 D（度=5），给后续节点更多灵活性
DSatur 动态选择最受约束的节点，往往能找到用更少颜色的方案

平面性与嵌入

着色和平面性紧密相关——四色定理正是关于平面图的。理解什么是平面图、如何判定平面性，是图论中的经典问题。

平面图的定义

平面图（planar graph）是可以画在平面上（或等价地，画在球面上）使得边只在端点处相交、不在中间交叉的图。这样的画法称为平面嵌入（planar embedding）。

注意”平面图”不是指”已经画好不交叉的图”，而是”存在一种画法使得不交叉”。同一个图可能有一种画法看起来边交叉，但另一种画法可以完全避免交叉。

Kuratowski 定理

怎么判断一个图是否是平面图？Kuratowski 在 1930 年给出了完美的刻画：

定理（Kuratowski, 1930）：图 $G$ 是平面图当且仅当 $G$ 不包含 $K_5$ （5 节点完全图）或 $K_{3,3}$ （完全二部图 3+3）的子划分（subdivision）。

子划分是在边上插入中间节点。 $K_5$ 的子划分就是把 $K_5$ 的某些边”拉长”（在边中间加节点），但拓扑结构不变。

直觉： $K_5$ 有太多边（10 条连接 5 个节点）， $K_{3,3}$ 的交叉结构使得无论怎么画都无法避免边交叉。任何非平面图都”包含”了这两种结构之一的变体。

为什么平面性重要

平面图在图算法中有特殊地位：

四色定理： $\chi(G) \leq 4$ ，着色变得容易
欧拉公式： $n - m + f = 2$ （ $f$ 是面的数量），由此推出 $m \leq 3n - 6$ ——平面图是稀疏的
分隔定理（Planar Separator Theorem）： $n$ 节点的平面图可以找到一个大小为 $O(\sqrt{n})$ 的节点集，删除后图分成两部分各不超过 $\frac{2}{3}n$ 节点。这使得许多算法在平面图上有更好的复杂度
许多现实图是平面或近似平面的：道路网络、电路板布线、地理区域邻接

平面图判定有高效算法：Hopcroft-Tarjan 算法可以在 $O(n)$ 时间内判定一个图是否是平面图（基于 DFS）。

图划分

着色解决的是”给节点分配颜色”，图划分解决的是一个相关但不同的问题：把节点分成几组，使得组之间的边尽可能少。

最小割划分

最简单的划分是二分：把节点分成 $S$ 和 $V \setminus S$ 两组。组间的边就是割 $\delta(S)$ 。最小化割的大小就是最小割问题——这在 Art. 12: 网络流中已经通过最大流-最小割定理解决了。

但最小割可能给出非常不平衡的划分（极端情况：一个节点 vs 其余所有节点）。实际应用中，我们通常需要平衡划分。

平衡图划分

问题：将 $V$ 分成 $k$ 组，每组大小约为 $n/k$ ，使得跨组的边数最小化。

这是 NP-hard 的——即使 $k = 2$ 的平衡二分（要求两组大小差不超过 1）也是 NP-hard。

为什么难？ 最小割不关心平衡性，加了平衡约束后就没有多项式时间算法了（除非 P = NP）。

METIS：多级方法

面对 NP-hard 问题，实践中最成功的方法是 METIS（Karypis & Kumar, 1998）的多级方法（multilevel method）。它不追求精确最优，而是在合理时间内给出高质量的近似解。

核心思想是三个阶段：

阶段 1 — 粗化（Coarsening）：反复合并节点对（通常选择边权最大的匹配），将图逐层缩小。 $n$ 节点的图可能被缩小到几百个”超级节点”。

阶段 2 — 初始划分（Initial Partitioning）：在最小的粗化图上运行精确或高质量的划分算法。由于图很小（几百个节点），即使用较慢的算法也很快。

阶段 3 — 细化（Uncoarsening + Refinement）：逐层把划分”投影”回更细的图，每层做局部优化（如 Kernighan-Lin 或 FM 算法交换边界节点来改善割的大小）。

为什么多级方法有效？

粗化保持了图的全局结构——合并的节点对通常是紧密相连的，它们本来就该在同一个划分中
在小图上划分避免了大规模精确求解的指数复杂度
逐层细化利用了局部搜索的优势——每次只需改善少量边界节点的归属

METIS 的实际表现惊人地好，可以在几秒内处理数百万节点的图，广泛用于科学计算（有限元网格划分）、并行计算（负载均衡）和 VLSI 电路设计。

图划分与着色的关系

着色和划分解决的是不同但相关的问题：

维度	着色	划分
目标	最少颜色，相邻不同色	最少割边，各组大小均衡
约束	相邻节点必须不同颜色	各组大小接近
优化方向	最小化颜色数	最小化组间边数
典型方法	贪心启发式	多级方法（METIS）
NP-hard?	是（ $k \geq 3$ ）	是（平衡划分）

两者的联系： $k$ -着色把节点分成 $k$ 组（同色一组），但着色不要求平衡，也不关心组间边数。平衡划分关心组间边数，但不要求同组内无边。

NP-hard 确认

3-着色问题是 NP-complete——给定一个图 $G$ ，判断 $\chi(G) \leq 3$ 是 NP-complete 的。

NP-complete 意味着什么？

验证一个 3-着色方案只需 $O(m)$ 时间——检查每条边两端颜色不同即可（所以在 NP 中）
但找到这样的方案（或证明不存在）在最坏情况下需要指数时间
除非 P = NP，否则不存在多项式时间算法

精确算法：最快的已知精确着色算法基于动态规划（Lawler, 1976），时间复杂度为 $O(2.443^n)$ ，对于 $n > 50$ 的图基本不可行。

实践中的策略：

对于小图（ $n < 30$ ），可以用回溯 + 剪枝精确求解
对于中等规模的图，使用贪心启发式（DSatur 等）获得近似解
对于大规模图，使用禁忌搜索、模拟退火等元启发式方法

关于 NP-hard 问题的系统讨论和近似策略，详见 Art. 15: NP-hard 与近似。

复杂度对比表

问题/算法	时间复杂度（最坏）	空间复杂度	适用场景
2-着色判定（BFS）	$O(n + m)$	$O(n)$	二部图判定
贪心着色（任意序）	$O(n + m)$	$O(n)$	快速近似着色
DSatur 贪心	$O(n^2)$ （朴素）或 $O(n(n+m))$ （精确）	$O(n)$	高质量近似着色
精确着色（DP）	$O(2.443^n)$	$O(2^n)$	小图精确求解
精确着色（回溯）	指数（最坏）	$O(n)$	小图，带剪枝
平面图判定（Hopcroft-Tarjan）	$O(n)$	$O(n)$	平面性检测
图划分（METIS 多级方法）	$O(n + m)$ （实践近似）	$O(n + m)$	大规模图划分
平衡二分（精确）	NP-hard	—	小图精确求解

关键洞察：2-着色是多项式的，3-着色就跳到 NP-complete——复杂度的”相变”发生在 $k = 3$ 。

应用场景

图着色不是纯理论——它是一系列实际问题的数学核心。

编译器寄存器分配

这是图着色最经典的应用之一（Chaitin, 1981）。

在编译器的代码生成阶段，程序中的变量需要映射到 CPU 的物理寄存器。但寄存器数量有限（x86-64 有 16 个通用寄存器，ARM 有 31 个），而变量可能有数百个。

建模：

每个变量是一个节点
如果两个变量同时活跃（live ranges 重叠），在它们之间连一条边——它们不能共用同一个寄存器
这样构成的图称为干涉图（interference graph）或冲突图
用 $k$ 种颜色着色（ $k$ = 寄存器数量），每种颜色代表一个寄存器
如果 $\chi(G) \leq k$ ，则所有变量都能分配到寄存器
如果 $\chi(G) > k$ ，某些变量必须”溢出”（spill）到内存

GCC 和 LLVM 都使用基于图着色的寄存器分配器。LLVM 的实现使用了 Chaitin-Briggs 算法——一种改进的贪心着色，先尝试”乐观着色”，只在确实需要时才溢出变量到内存。

考试/课程排期

大学需要安排期末考试时间表。每门课程是一个节点，如果两门课有共同的学生（学生需要参加两门考试），就在它们之间连边。用 $k$ 种颜色着色就是把课程分成 $k$ 个时间段。

目标：最小化时间段数 = $\chi(G)$ 。

MIT 的考试排期系统就使用图着色算法。典型规模：200-400 门课程，冲突图有数千条边，DSatur 通常在几毫秒内给出接近最优的排期。

频率分配

无线通信中，相邻基站如果使用相同频率会产生干扰。频率分配问题就是给基站分配频率，使得相邻基站频率不同，同时最小化使用的频率数（频谱资源宝贵）。

建模：基站 = 节点，干扰范围内的基站对 = 边，频率 = 颜色。

由于基站的地理分布通常是近似平面的，干扰图往往是平面图或接近平面图——四色定理保证 4 个频率就够，实践中通常用 3-7 个频率即可覆盖。

地图着色

四色定理的原始动机：给地图上的国家/地区着色，使相邻区域颜色不同。这是图着色的”原型应用”。地图的邻接关系天然构成平面图，四色定理保证 4 种颜色永远够用。

🔁 迭代机器视角 — Greedy ColoringCST: 约束满足

Graph	原图
State[v]	color(v)
SELECT	按某种序遍历节点
COMBINE	分配最小可用颜色（不与邻居冲突）
TERMINATE	所有节点已着色
求解方法	GS

贪心着色不保证最优——结果依赖于节点遍历顺序。对于一般图，最优着色是 NP-hard

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — DSATURCST: 约束满足

Graph	原图
State[v]	color(v) + saturation(v)
SELECT	PQ-max（饱和度最大优先）
COMBINE	分配最小可用颜色 → 更新邻居饱和度
重入	无
TERMINATE	所有节点已着色
求解方法	FI

💡 对比: Greedy Coloring: DSATUR 用 PQ 选择饱和度最高的节点 → 通常使用更少颜色

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — Graph Partitioning (Kernighan-Lin)OPT: 优化目标

Graph	原图（二分区）
State[v]	分区归属 + gain 值
SELECT	增益最大的交换对
COMBINE	计算交换增益 → 执行最优交换
重入	到不动点（每轮内无正增益交换）
TERMINATE	无正增益交换
求解方法	FI

Kernighan-Lin 是局部搜索的经典实例——在解空间上迭代改进

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文建立了图着色和图划分的核心框架：

色数 $\chi(G)$ ：合法着色所需的最少颜色数。2-着色 = 二部图判定（ $O(n+m)$ ），但 3-着色就是 NP-complete
特殊图：二部图 $\chi = 2$ ，完全图 $K_n$ 的 $\chi = n$ ，平面图 $\chi \leq 4$ （四色定理），奇环 $\chi = 3$
上界定理：贪心保证 $\chi \leq \Delta + 1$ ，Brooks 加强为 $\chi \leq \Delta$ （除完全图和奇环）
贪心着色： $O(n + m)$ 的实用方法，节点排序策略决定质量——DSatur（最大饱和度优先）是最重要的启发式
平面性：Kuratowski 定理（ $K_5$ 和 $K_{3,3}$ 的子划分是唯二的禁止结构），平面图判定 $O(n)$
图划分：平衡划分是 NP-hard，METIS 多级方法（粗化→划分→细化）是实践中的标准方案
应用：寄存器分配、考试排期、频率分配、地图着色——本质都是”冲突消除”

图着色是 NP-hard 问题的代表之一——不存在精确的多项式算法。下一篇 Art. 15: NP-hard 与近似将系统讨论：当问题是 NP-hard 时，我们有哪些武器——近似算法、LP 松弛、启发式搜索。

实现指引

算法	库	函数/方法
贪心着色（多种策略）	NetworkX	`nx.coloring.greedy_color(G, strategy='DSATUR')`
色数上界	NetworkX	`len(set(nx.coloring.greedy_color(G).values()))`
二部图判定	NetworkX	`nx.is_bipartite(G)`
平面图判定	NetworkX	`nx.is_planar(G)`
平面图嵌入	NetworkX	`nx.check_planarity(G)`
贪心着色	igraph	`g.vertex_coloring_greedy(method='dsatur')`
图划分	METIS (PyPI)	`import metis; metis.part_graph(G, nparts=k)`
图划分	NetworkX	`nx.community.kernighan_lin_bisection(G)` (KL 二分)
图划分	scipy	`scipy.sparse.csgraph.reverse_cuthill_mckee(graph)` (带宽缩减)
平衡分割	Neo4j GDS	`gds.graph.partition(graph, k)`

核心问题：最少需要几种颜色？

核心思路：从特殊到一般，从上界到精确

特殊图的色数

二部图 ↔\leftrightarrow↔ 2-可着色

完全图 KnK_nKn​

奇环

平面图与四色定理

色数小结

上界定理

贪心上界：χ(G)≤Δ(G)+1\chi(G) \leq \Delta(G) + 1χ(G)≤Δ(G)+1

Brooks 定理：χ(G)≤Δ(G)\chi(G) \leq \Delta(G)χ(G)≤Δ(G)

贪心着色算法

基本贪心框架

排序策略：顺序决定一切

走查：三种策略对比

平面性与嵌入

平面图的定义

Kuratowski 定理

为什么平面性重要

图划分

最小割划分

平衡图划分

METIS：多级方法

图划分与着色的关系

NP-hard 确认

复杂度对比表

应用场景

编译器寄存器分配

考试/课程排期

频率分配

地图着色

总结

实现指引

二部图 $\leftrightarrow$ 2-可着色

完全图 $K_n$

贪心上界： $\chi(G) \leq \Delta(G) + 1$

Brooks 定理： $\chi(G) \leq \Delta(G)$