图着色求解器

伪代码

贪心着色只有三行，而且总能给出一种合法的着色。它不保证给出的是最少颜色数，而结点的处理顺序决定了它能接近到什么程度。

贪心着色(图, 顺序):
    颜色 = {}
    对 顺序 中的每个结点 v:
        已用 = { 颜色[n] : n 是 v 的邻居且已着色 }
        c = 不在 已用 中的最小正整数
        颜色[v] = c
    返回 颜色

// Welsh-Powell：按度数从大到小排序
// DSatur：反复选取未着色结点中邻居颜色种类最多的那个
//         （饱和度最高），并以度数打破并列

贪心用到的颜色永远不超过最大度加一，因为轮到某个结点时，它至多有那么多邻居，因此至多有那么多被禁用的颜色。这是一条真实的保证，但它可能离真正的色数很远。DSatur 是务实的改进：优先处理约束最多的结点，正是这条启发式让你不至于把自己逼进死角。

分步示例演算

按字母顺序对一个五元环做贪心着色，再把结果与真正的色数对照。

示例图: 无向环 A-B、B-C、C-D、D-E 和 E-A。

1. 给 A 着色. 此时还没有邻居被着色，因此 A 取颜色 1。
2. 给 B 着色. B 与颜色为 1 的 A 相邻，因此可用的最小颜色是 2。
3. 给 C 着色. C 与 B（颜色 2）以及尚未着色的 D 相邻。颜色 1 是空闲的，因此 C 取 1。
4. 给 D 着色. D 与 C（颜色 1）以及尚未着色的 E 相邻。颜色 2 是空闲的，因此 D 取 2。
5. 给 E 着色迫使出现第三种颜色. E 与 D（颜色 2）和 A（颜色 1）都相邻。两种已有颜色都被占用，因此 E 需要颜色 3。

着色结果为 A 1、B 2、C 1、D 2、E 3，共用三种颜色；穷举验证表明五元环的色数确实就是 3。这里贪心恰好是最优的。之所以需要三种颜色，是因为这个环的长度为奇数：沿环着色必须交替，而奇环会把你带回起点，并要求那里换一种与已有不同的颜色。任何偶环都只需 2 种。

复杂度及其来源

时间: 贪心 O(V + E)，精确求解 NP 困难 · 空间: O(V)

贪心着色对每个结点只考察一次，对每条边从两个端点各检查一次，因此是 O(V + E)，颜色数组占 O(V) 空间。这点代价换来的是一种合法着色，所用颜色不超过最大度加一，但绝不保证最少。计算真正的色数是 NP 困难的；即便只想把它近似到 V 的 1 减 epsilon 次方这个因子之内，同样是 NP 困难的，这个结论异常之强：多数问题都还有某种像样的近似，而着色问题基本上没有。判定二着色是个例外，而且很容易，因为它恰好就是 O(V + E) 的二分性检测。判定三着色则已经是 NP 完全的了。

何时使用图着色，何时不宜

根据你预期需要多少种颜色，以及是否非要真正的最小值来选择。

常见陷阱

• 以为贪心给出的就是色数. 它给出的是合法着色而非最小着色，而且差距可能很大。在冠图上，两部分为 {a1,a2,a3} 与 {b1,b2,b3}，只要 i 与 j 不同就有边 ai-bj；交错顺序 a1,b1,a2,b2,a3,b3 会让贪心用掉 3 种颜色，尽管该图是二分图、2 种就够。把同一个图按 a1,a2,a3,b1,b2,b3 的顺序处理则只用 2 种。
• 忽视结点顺序的分量. 总存在某种顺序能达到真正的色数，而找到它与着色问题本身一样困难。这正是 DSatur 边算边动态挑选、而不是预先固定顺序的原因。
• 把色数与团数混为一谈. 规模为 k 的团至少迫使 k 种颜色，因此团数是一个下界，但两者可能不相等。长度为 5 或更长的奇环需要 3 种颜色，却根本不含三角形。
• 指望存在良好的近似. 与许多 NP 困难问题不同，图着色没有已知的常数因子近似算法，而且很强的困难性结果表明这样的算法多半并不存在。启发式方法在实践中可能表现不错，但对最坏情况不提供任何保证。
• 忘记自环会让着色不可能. 与自身相邻的结点永远无法与自己取不同颜色，因此含有自环的图根本不存在合法着色。请在开始前就拒绝这类输入。

常见问题

什么是图着色？

图着色为每个结点分配一种颜色，使得相邻的两个结点绝不同色。能够奏效的最少颜色数就是该图的色数。它可以刻画任何需要把互相冲突的元素分开的问题，例如安排考试使任何学生都不会同时被安排两场。

什么是图的色数？

进行合法着色所需的最少颜色数。二分图的色数不超过 2，奇环为 3，n 个结点的完全图为 n。一般情形下计算色数是 NP 困难的，不过规模为 k 的团能给出一个简单的下界 k。

贪心算法总能用最少的颜色吗？

不能。它总能给出一种合法着色，所用颜色不超过最大度加一，但这可能超过色数。在冠图这个只需 2 种颜色的二分图上，一个不巧的顺序会让贪心用掉 3 种。总存在能达到最优的顺序，但找到它与原问题一样困难。

贪心着色与 DSatur 有什么区别？

贪心预先固定结点顺序并照此着色。DSatur 则动态挑选下一个结点，始终取邻居颜色种类最多的那个，并以度数打破并列。这种对约束最强结点的关注使 DSatur 在二分图上达到最优、在一般图上也明显更好，代价是 O(V 的平方) 而非 O(V + E)。

图着色有什么用途？

用于编译器中的寄存器分配，其中寄存器就是颜色，生存期相互冲突的变量彼此相邻。此外还用于考试与排班安排、避免邻近发射台相互干扰的无线电频率分配、数独求解，以及任何资源分配问题中把互相冲突的任务分开。