图着色与组合优化：从四色定理到 NP-完全性

图着色是组合数学中最深刻、最具应用广度的问题之一。从 1852 年 Guthrie 兄弟在地图着色中发现的四色猜想，到现代无线通信的频谱分配，它始终站在理论计算机科学与工程实践的交汇处。本文系统梳理图着色问题的起源、基本理论、计算复杂性，以及它在现实世界中的关键应用。

1.1 四色猜想的诞生

1852 年，正在为英国各郡地图着色的 Francis Guthrie 向其老师 Augustus De Morgan 提出一个问题：任何平面地图是否仅需四种颜色即可使得相邻区域着以不同颜色？这里的"相邻"指共享一条有限长边界，而非仅共享一个点。

这个问题在 1879 年被 Alfred Kempe 给出了一个看似完整的证明，但在 1890 年 Percy Heawood 发现了 Kempe 论证中的一个关键错误。尽管如此，Heawood 在纠正错误的过程中证明了更强的结论——五色定理：任何平面地图可用至多五种颜色着色。五色定理的证明相对简洁，利用了平面图的欧拉公式 $|V| - |E| + |F| = 2$ 以及度数上界。

1.2 地图着色与图着色的等价性

地图着色与顶点着色之间的等价变换，是将几何问题转化为纯组合问题的关键步骤。具体构造如下：

• 将地图中每个区域映射为图的一个顶点
• 若两个区域共享一条有限长度边界，则在对应顶点之间添加一条边

得到的图是平面图（可以嵌入平面且边之间无交叉）。反之，任何平面图都可以从某个地图中通过上述方式得到。这个等价变换意味着，四色猜想可以重新表述为：

其中 $\chi(G)$ 表示图 $G$ 的色数（chromatic number），即对 $G$ 进行正常着色所需的最少颜色数。

四色定理的等价变换图示

graph LR
    subgraph 地图
        M1["区域 A"]
        M2["区域 B"]
        M3["区域 C"]
        M4["区域 D"]
        M1 --- M2
        M2 --- M3
        M3 --- M4
        M2 --- M4
    end
    subgraph 等价变换
        TF["⇩ 区域→顶点 ⇩"]
    end
    subgraph 图
        G1["顶点 A"]
        G2["顶点 B"]
        G3["顶点 C"]
        G4["顶点 D"]
        G1 --- G2
        G2 --- G3
        G3 --- G4
        G2 --- G4
    end

2.1 顶点着色与色数

设 $\Delta(G) = \max\{ \deg(v) : v \in V(G) \}$ 为图的最大度数。一个平凡的上界是 $\chi(G) \leq \Delta(G) + 1$——按任意顺序逐顶点着色，每个顶点至多与 $\Delta(G)$ 个已着色邻居冲突，因此最多需要 $\Delta(G) + 1$ 种颜色。这个上界通常很宽松。

2.2 Brooks 定理

换言之，除完全图和奇环这两类"极端"图之外，所有图的色数至多是 $\Delta(G)$，而非 $\Delta(G) + 1$。完全图 $K_n$ 需要 $n$ 种颜色，而 $\Delta(K_n) = n - 1$，所以恰好达到 $\Delta(G) + 1$ 的下界。奇环 $C_{2m+1}$ 的 $\Delta = 2$，但需要 3 种颜色。

2.3 边着色与 Vizing 定理

顶点着色是对边添加约束（相邻边不能共端点颜色），边着色是对相邻边添加约束（共享端点的边必须颜色不同）。设 $\chi'(G)$ 为图 $G$ 的边色数。

对于平面图，Vizing 证明所有平面图的边色数至多是 $\Delta(G) + 1$。确定一个图属于哪一类是一个困难的问题（对一般图是 NP-完全的），但 Vizing 定理已经足够精确地限定了范围。

3.1 Appel-Haken 的计算机辅助证明（1976）

1976 年 6 月 21 日，Kenneth Appel 和 Wolfgang Haken 在伊利诺伊大学宣布证明了四色定理。他们的证明方法是不可避免性 + 可约性方法的集大成之作。

整个证明依赖于计算机对 1936 种不可约构型的逐一验证。1989 年，Appel 和 Haken 发表了完整的证明，包含 400 多页的手工推导和大量计算机验证。当时这一证明引发了数学界的激烈争论——首次有数学定理依赖计算机辅助证明且无法人工验证其全部细节。

3.2 Robertson-Sanders-Seymour-Thomas 的简化证明（1997）

1997 年，Neil Robertson、Paul Seymour、Daniel Sanders 和 Robin Thomas 给出了一个显著简化的证明版本。该证明同样基于不可避免性和可约性，但将不可约构型的数量从 1936 减少到 633。尽管这仍然是无法手工逐一验证的数量，但证明的结构更加清晰，算法验证也更加高效。

3.3 定理的机器验证

2005 年，Georges Gonthier 使用通用形式化证明助手 Coq，给出了四色定理的完整形式化验证。这不仅确认了证明的正确性，还意味着证明的每一步都可以在计算机上自动验证，从而回应了关于传统计算机辅助证明可靠性的质疑。

4.1 图着色判定问题的复杂性

图着色判定问题（Graph Coloring Decision Problem）可以表述为：给定图 $G = (V, E)$ 和整数 $k$，判定是否存在 $G$ 的一个正常 $k$-着色？记为 $k$-COLORING。

• 当 $k = 2$ 时，判定图是否是二部图（bipartite graph），可以在多项式时间内通过 BFS 或 DFS 完成
• 当 $k \geq 3$ 时，问题是 NP-完全的

4.2 从 3-SAT 到 3-色的归约

为了证明 3-COLORING 的 NP-完全性，需要从已知的 NP-完全问题（通常选择 3-SAT）进行多项式时间归约。归约的核心思想是为每个 3-SAT 实例构造一个图，使得该公式可满足当且仅当构造的图可以用 3 种颜色着色。

归约构造图示

graph TB
    subgraph 构造组件
        VAR["变量 Gadget
v_i — v_i' 与 B 构成三角形"]
        OR["OR Gadget
5 个辅助顶点"]
        BASE["全局基础顶点
T — F — B 三角形"]
    end
    subgraph 3-SAT 实例
        F["公式 (x₁ ∨ ¬x₂ ∨ x₃)"]
    end
    subgraph 构造结果
        G["图 G
可 3-着色 ⟺ 公式可满足"]
    end
    F --> VAR
    F --> OR
    VAR --> G
    OR --> G
    BASE --> G

具体构造包含以下组件：

1. 变量 gadget：对每个变量 $x_i$，创建两个顶点 $v_i$ 和 $v_i'$（表示 $x_i$ 和 $\neg x_i$），它们与一个公共基础顶点 $B$ 形成一个三角形。这一约束强制 $v_i$ 和 $v_i'$ 分别着两种不同的颜色，从而对应 TRUE 和 FALSE 的语义。
2. 句 Gadget：对每个子句 $c = (u \vee v \vee w)$，构造一个 OR-gadget，包含 5 个辅助顶点，通过特定的连接方式确保：若三个文字 $u, v, w$ 的对应顶点全部为 FALSE（即都被着色为与 FALSE 对应的颜色），则 OR-gadget 的输出顶点无法合法着色。
3. 全局颜色框架：引入三个特殊的全局顶点 T、F、B，形成一个三角形。这三个顶点强制所有颜色被限制在恰好三个不同的颜色类中。

因此，3-COLORING 是 NP-完全问题。由于 3-COLORING 是 $k$-COLORING 的特例，一般的 $k$-COLORING（$k \geq 3$）也是 NP-完全的。

4.3 近似的困难性

图着色问题的近似算法同样面临严峻的困难。在最优颜色数的近似比上，已知结果为：除非 $\text{P} = \text{NP}$，对任意常数 $\varepsilon > 0$，不存在多项式时间近似算法能在 $O(n^{1 - \varepsilon})$ 的近似比内逼近最优色数。这与许多其他 NP-困难问题（如独立集）类似，APPROX-COLORING 的问题在理论上几乎是不可改进的。

5.1 贪心着色算法

最朴素的图着色算法是贪心着色（Greedy Coloring）：按任意顺序遍历图中的顶点，每次为当前顶点分配它所遇到的第一个可用颜色。

贪心着色算法流程图

graph TD
    A["开始：输入图 G"] --> B["将顶点排成序列
v₁, v₂, ..., vₙ"]
    B --> C["i = 1"]
    C --> D{"i ≤ n?"}
    D -->|"是"| E["为 vᵢ 分配最小可用颜色
（未被邻居使用的最小颜色）"]
    E --> F["i = i + 1"]
    F --> D
    D -->|"否"| G["输出着色方案"]
    G --> H["结束"]

时间复杂度：$O(|V| + |E|)$。使用颜色数的上界为 $\Delta(G) + 1$。

5.2 Welsh-Powell 算法

Welsh-Powell 算法（1967）是最早的改进贪心策略之一，其核心思想是优先处理高度数顶点：

1. 按度数降序排列所有顶点
2. 按此顺序进行贪心着色

直觉：高度数顶点的约束最多，先处理它们可以避免后期颜色冲突。通过优先消除高约束顶点，算法通常能在较少颜色数内完成着色。对大多数图，这一策略显著优于随机顺序，但仍然无法保证接近最优色数。

5.3 DSatur 算法（分支限界法）

饱和度（saturation degree）定义为：一个顶点当前已着色的邻居所使用的不同颜色的数量。DSatur（Degenration + Saturation）算法使用分支限界搜索，在每一步选择饱和度最高的顶点进行着色：

1. 计算所有未着色顶点的饱和度
2. 选择饱和度最大的顶点 $v$（若多个顶点饱和度相同，按度数打破平局）
3. 尝试为 $v$ 分配每一种可能的颜色（剪枝：当剩余可用颜色数已不足以处理剩余子图时跳过）
4. 递归或迭代直到找到完整着色或证明不可行

DSatur 是精确算法（最坏指数时间），但在实际应用中通过良好的剪枝策略，可以求解规模相当大的实例。它是组合优化中分支限界法（branch and bound）思想的具体应用，通过选择最"紧张"的位置进行搜索，以最大化剪枝效果。

6.1 定义与基本性质

色多项式的研究动机来自两个方面：其一，它编码了图的所有着色方案的信息；其二，色多项式的研究直接导致了 Tutte 多项式的发现，后者是图不变量理论的核心对象。

6.2 删除-收缩递推

色多项式的核心计算工具是删除-收缩递推公式（Deletion-Contraction Recurrence）：

删除-收缩递推图示

graph LR
    G["原图 G
边 e = uv"] --> D["删除操作
G \\ e"]
    G --> C["收缩操作
G / e"]
    D --> P1["P(G \\ e, k)
移除了边 e 的约束"]
    C --> P2["P(G / e, k)
合并 u 和 v"]
    P1 --> R["P(G, k)
= P(G \\ e) - P(G / e)"]
    P2 --> R

其中：

• $G \setminus e$ 表示从 $G$ 中删除边 $e$（保留端点）
• $G / e$ 表示收缩边 $e$（合并其两个端点为一个顶点，删除自环，合并平行边）

递推终止条件：当 $G$ 无边时，$P(G, k) = k^{|V|}$，因为每个顶点可以独立选择任意一种颜色。

6.3 完全图的色多项式

完全图 $K_n$ 的色多项式具有极为简洁的形式：

这正是因为完全图中每对顶点相邻，任何两个顶点不能同色，因此着色方案等价于从 $k$ 种颜色中选取一个无重复排列，即 $k$ 的 $n$-排列数。

6.4 色多项式系数的意义

色多项式 $P(G, k)$ 可以展开为：

其中 $e_i$ 为第 $i$ 个系数。

色多项式的研究揭示了图的结构性质与计数性质之间的深层联系。例如，若两个图的色多项式相同（色同构），它们在着色计数意义上不可区分，但可能具有完全不同的拓扑结构。

7.1 无线通信频谱分配

现代无线通信系统（4G/5G 蜂窝网络、Wi-Fi、卫星通信）需要为大量发射设备分配频率信道。频谱分配的核心约束是同频干扰：若两个相邻（距离足够近）的基站使用相同的频率，信噪比将严重下降。

这一问题的图模型天然对应图着色：将每个基站（或访问点）建模为一个顶点，若两个顶点之间的距离低于干扰阈值，则它们之间连边。频率分配方案对应图的顶点着色——相邻基站不能使用同一信道（即同一颜色），不同颜色代表不同的频谱信道。

7.2 考试排期

考试排期问题（Exam Timetabling）的约束来源于：一个学生不能同时参加两场考试。这同样可以建模为图着色：每个考试对应一个顶点，若某个学生参加了考试 $A$ 和考试 $B$，则在对应顶点之间连一条边。排期方案对应一种着色——同一时间段（颜色）内安排的考试集合必须两两无冲突。

教育系统中实际的考试排期是大型组合优化问题，一个拥有 3 万名学生的大学可能需要安排数千场考试。图着色模型结合启发式算法（如基于约束的搜索、遗传算法）是这类问题的标准求解手段。

7.3 编译器中的寄存器分配

在编译器优化中，寄存器分配是一个核心问题：编译器需要将程序的无限多个临时变量映射到有限数量的 CPU 寄存器中，使得同一时间活跃的变量不共享寄存器。

这个问题可以建模为冲突图：图的顶点代表程序中的临时变量（或"虚拟寄存器"），两个顶点之间有边当且仅当相应变量在同一时间点同时活跃（即生命期交叉）。寄存器分配对应冲突图着色——每个颜色代表一个物理寄存器。

7.4 地图着色

虽然四色定理在理论上已解决，但在地理信息系统（GIS）和其他视觉化场景中，地图着色仍然是一个实践问题。当地图包含飞地、碎片状区域或需要考虑更多约束（如不同区域可能有不同的优先级）时，问题可能超越经典四色设定的范畴。此外，艺术化地图着色可能需要满足美学约束（如颜色和谐、对比度），这些问题在图着色框架中可以通过加权着色或约束编程加以扩展。

图着色问题横跨纯数学与计算科学两个维度。在纯数学层面，四色定理的证明标志着计算机辅助证明时代的到来，色多项式的研究引出了 Tutte 多项式这一图论与统计物理的统一框架。在计算科学层面，图着色的 NP-完全性揭示了组合优化中固有的计算困难，而 DSatur、Welsh-Powell 等算法则提供了在实践中可用的近似工具。

从无线频谱分配到编译器寄存器分配，从考试排期到地图可视化，图着色作为组合优化的核心模型，持续为工程实践提供理论框架和算法基础。理解图着色的理论边界与算法能力，是每一个从事算法设计或运筹优化的研究者必备的基础。