浅谈平面图五染色的一种算法

· · 个人记录

对于一个平面图，我们要把该图的所有区域进行 5 染色，使得存在边相邻的两个区域颜色不同。

给个例子：

而对于平面图五染色构造方案，现在常见的是一种 O(n^2) 的做法（可能是我孤陋寡闻吧），具体可以百度一下。

本文的目标是介绍一种 O(n \alpha(n)) 的平面图 5 染色的快速染色算法。

四色定理及其探索过程（不想看的可以跳过）

事实上，有一个著名的定理叫做四色定理，内容是对于任意一个平面图，都存在 4 染色。

首先是很久很久之前有个叫古德里的英国大学生发现地图可以 4 染色。

于是他做了一些实验，然后大胆猜想任意一个图都存在 4 染色。

然后他和他的弟弟一起来尝试证明这个结论，结果画了 114514 张草稿纸也没有证明出来（形容数量很多，懂得都懂）。

然后这个问题就传出去了，许多数学家都尝试了，可都没有成功，直到……

肯普登场，于是他“成功”了，他成功的给出了一种假做法。11 年之后，赫伍德成功的找到了肯普证明中的错误，于是这个证明就寄了。

这是给出的一个基于肯普的构造方法的反例：

不过通过赫伍德的分析，肯普其实证明出了一个更弱的定理：五色定理。

后来，又有许多数学家积极投身于四色定理，开始证明区域数小于等于 k 的时候一定有解。

刚开始 k=22，后来推进到了 35,39,50\cdots，但速度仍然很慢。

后来又有一个数学家干了一件至关重要的事情，他证明了如果四色定理不成立，一定是在某些特定的情况中不成立（只有有限种情况），于是随着计算机的发明，美国的两个数学家和一个计算机学家就合作爆搜出了结果，证明了四色定理，当时跑了 1200 个小时……

当然，这肯定不是一个令人满意的证明，数学爱好者们对四色定理的研究，当然不会在此止步。

（这里给一个网上弄来的证明，全英文的，没看懂，当然不保证正确：http://www.ams.org/notices/200811/tx081101382p.pdf）

对偶图转化

这里的平面图和我们 OI 中的图区别比较大，不过我们可以做一点简单的转化，对于每一个区域，看成一个点，然后如果两个区域有边相邻就连边，这样得出的图还是一个平面图（所有边不相交），不过这个时候就是对这些节点进行染色了，这就是我们 OI 中的常见染色模型了。

欧拉平面图定理

有 V-E+D=C+1，其中 V 是点数，E 是边数，D 是边围成的平面数，C 是连通块数。

证明烂大街了，不会自己上网搜。

当然这里我们需要的不仅仅是这个公式，因为里面有很多没用的东西。

我们考虑 V,E 之间的关系，可以得到 E\le 3V-6(V\ge 3)，可以通过刚才的东西变形得到（考虑一个平面最少需要 3 条边围成），当然也可以直接归纳证明。

于是乎我们似乎得到了一个很重要的结论：不存在 K_5（大小为 5 的完全子图）。网上有许多烂大街的伪证大概就是这样得出四色定理成立。

但这并不等价，不能说因为不存在 K_5 就一定满足四色定理，例如下图也不存在 K_5（当然啦，这不是个平面图）：

不过，我们可以快速得出六色定理。

首先一定存在度数小于等于 5 的节点，我们删除这个节点及其相应的边，记录一下删点顺序然后倒着加回来，这样每加入一个点我们就可以染成 1\sim 6 中的一种颜色，于是得证并得出构造方案。

于是考虑向 5 色定理进发。

我们先说一下基于肯普提出的做法。

大概是这样：

每次找到一个度数小于等于 5 的节点，然后删除。

当度数小于等于 4 时这样一点毛病都没有，只有度数为 5 时会出问题，考虑如何解决。

然后用到了很巧妙的一步，考虑此时五个点颜色互不相同，假设颜色和编号均为 1\sim 5，考虑定义两种颜色 (i,j)\;(1\le i<j\le 5) 是可达的，当且仅当存在一条 i 到 j 的路径，满足这条路径上 i,j 两种颜色交错出现。

我们的目标是找到一对 (i,j) 满足 (i,j) 不可达。

首先可以证明一定存在，因为不存在这样的情况，其中两个点有连边表示它们可达：

这也充分体现了平面图的平面性。

然后找到 i,j 之后从 i 开始搜索，如果当前点的颜色为 i 则变成 j，然后去更新和它有连边的颜色为 j 的点，不难发现这样就空出了一个颜色。

不过很遗憾，这种做法复杂度是 O(n^2) 的，现在来讲一种优秀一点的做法。

缩点过程

对于两个点 a,b，考虑这么一个如图所示的缩点过程：

图搞错了，中间不应该有连边，或者说你可以理解为中间那一条黑色的边表示的应该是将这两个点合并的操作。

算法流程

我们还是是每次找到一个度数小于等于 5 的节点，然后删除。当度数小于等于 4 时这样一点毛病都没有，只有度数为 5 时会出问题，考虑如何解决。

首先先把这个点删除，然后我们可以找到两个点，满足这两个点之间不会存在边直接相连（可以证明一定存在），然后对这两个点执行缩点操作，不难发现此时进行完缩点操作之后仍为平面图。

画个图意思意思：

然后递归处理即可，可以证明正确性，回退过程可以顺便构造方案。

可以用线段树合并维护邻接矩阵，做到 O(n\log n)。

其实是可以使用并查集维护缩点操作，可以做到 O(n\alpha(n))，具体实现可能需要一些小技巧（注意这里忽略了某些地方 5 的常数）。

（感觉重点内容就这么一点啊，我是划不住重点吗？）