图着色问题（Graph Coloring）

图着色问题是一个经典的组合优化问题，其目标是为图中的每个顶点分配一种颜色，使得任意相邻顶点颜色不同，且使用的颜色数尽可能少。最小颜色数称为图的色数（chromatic number）。该问题在NP完全问题中具有重要地位，广泛应用于课程安排、寄存器分配、频谱分配等领域。

1. 问题描述与基本概念

• 输入：无向图 \(G = (V, E)\)，其中 \(V\) 为顶点集合，\(E\) 为边集合。
• 输出：颜色函数 \(C: V \to \{1, 2, ..., k\}\)，满足对任意边 \((u, v) \in E\)，有 \(C(u) \neq C(v)\)。
• 优化目标：最小化 \(k\)（即色数）。

关键术语：

• 合法着色：满足相邻顶点颜色不同的着色方案。
• 色数 \(\chi(G)\)：图 \(G\) 的最小可能颜色数。

2. 贪心着色算法（顺序着色法）

最常用的启发式算法是贪心算法，其核心思想是按顺序遍历顶点，为每个顶点分配可用的最小颜色编号（从1开始）。

步骤：

1. 将顶点按某种顺序排列（如输入顺序、度降序等）。
2. 初始化颜色数组 \(color[]\)，全部设为0（未着色）。
3. 遍历每个顶点 \(v\)：
   • 检查 \(v\) 的所有邻居已使用的颜色，记录不可用的颜色。
   • 从颜色1开始递增，找到第一个未被邻居使用的颜色，分配给 \(v\)。
4. 返回颜色数组及使用的颜色总数 \(k\)。

示例（假设顶点顺序为A, B, C, D）：

图：A-B, B-C, C-D, D-A  
步骤：  
- A着色1  
- B检查邻居A（颜色1），着色2  
- C检查邻居B（颜色2），着色1  
- D检查邻居A（1）和C（1），着色2  
最终使用2种颜色。  

时间复杂度：\(O(|V|^2)\)（需检查每个顶点的所有邻居）。
注意：贪心算法的结果依赖于顶点顺序，可能不是最优解。

3. 回溯法求精确解

若需要精确求解色数，可使用回溯法（暴力搜索的优化版）。

步骤：

1. 从 \(k=1\) 开始尝试，判断图是否可 \(k\)-着色。
2. 递归为每个顶点分配颜色：
   • 若当前顶点所有颜色尝试均冲突，回溯到上一个顶点。
   • 若所有顶点着色成功，返回 \(k\) 作为色数。
3. 若 \(k\)-着色失败，则 \(k\) 增加1，重复过程。

优化技巧：

• 剪枝：当部分顶点着色后，若剩余顶点无法合法着色，提前回溯。
• 顶点顺序：优先着色度高的顶点，减少分支数。

复杂度：最坏情况 \(O(k^{|V|})\)，适用于小规模图。

4. 特殊图的色数性质

• 二分图：当且仅当图中无奇环时，色数为2（可用BFS/DFS检测二分性）。
• 完全图 \(K_n\)：色数为 \(n\)。
• 平面图：根据四色定理，色数 ≤ 4。

5. 应用场景

• 课程安排：顶点代表课程，边代表时间冲突，颜色对应时间段。
• 寄存器分配：顶点代表变量，边代表同时存活冲突，颜色对应寄存器。
• 无线频谱分配：基站为顶点，相邻基站需不同频率。

6. 面试常见变体

1. 判断图是否可二着色：等价于判断是否为二分图（BFS/DFS染色）。
2. 给定 \(k\)，判断是否可 \(k\)-着色：NP完全问题，需回溯或启发式算法。
3. 近似算法：如Welsh-Powell算法（按度降序贪心），可减少颜色数。

通过理解贪心与回溯的权衡，以及实际问题中的约束条件，可以灵活选择解法。