四色定理地图涂色器
无论地图多么复杂,四种颜色总能把它涂好,让共享边界的国家永远不同色。这个命题简单到孩子用蜡笔就能检验,证明它却花了一个多世纪,还动用了计算机。亲手给一幅随机地图涂色,看看哪些边界发生冲突,再观看三种方法完成着色:从有时需要第五种颜色的快速贪心规则,到总能用四种颜色完成的回溯搜索。 选一种颜色,点击国家为其涂色;两个相邻国家颜色相同时,它们之间的边界会变红。只在一个角上相接的国家可以同色。也可以交给计算机:选择一种方法,按“求解”观看全过程,或按“单步”一步一步地跟着看。“最少颜色”会检查这幅地图是否用三种甚至两种颜色就够了。“新地图”会生成另一幅地图,“显示相邻关系”会画出共享边界的国家之间的网络。
它是如何运作的
- 选择国家数量并按“新地图”,或者从当前显示的地图开始。
- 选一种颜色,点击国家为其涂色,留意相邻国家冲突时出现的红色边界。
- 选择一种方法,按“求解”或“单步”观看它为地图着色;按“最少颜色”查看这幅地图需要几种颜色。
从地图到图
在每个国家里放一个点,两个国家共享边界时,就把对应的两个点连起来。地图就变成了一个图,给地图着色等同于给这些点着色,使相连的点颜色不同。由于地图画在平面上,这些图是平面图:可以画得没有任何交叉的线。只在一个点相接的国家(比如在一个角上相会的四个正方形)不算相邻。四色定理指出,每个平面图都可以用四种颜色着色。打开“显示相邻关系”,即可看到当前地图的图。
三种着色方法
贪心着色逐个处理国家,邻国最多的先处理,并给每个国家分配其邻国尚未使用的第一种颜色。它速度快但目光短浅,在某些地图上会用到第五种甚至第六种颜色。DSATUR 由丹尼尔·布雷拉于1979年提出,它总是接着选择邻国已呈现出最多不同颜色的那个国家,通常能避开上述陷阱。回溯法依次尝试各种颜色,当某个国家已无颜色可用时,就撤销最近的选择并重新尝试;它总能找到四色着色方案,有时要回退许多次。
常见问题
为什么四种颜色总是足够?
至今没有人找到简短的理由。肯尼斯·阿佩尔和沃尔夫冈·哈肯在1976年给出的证明表明,每幅地图都必定包含1936种小构形之一,而且每种构形都可以先移除、之后再恢复着色;检查全部构形耗费了一千多小时的计算机时间。1996年,尼尔·罗伯逊、丹尼尔·桑德斯、保罗·西摩和罗宾·托马斯给出了一个更简单的计算机证明,只需633种构形;2005年,乔治·贡蒂耶用 Coq 证明助手完整地验证了一个证明。
有些地图需要全部四种颜色吗?
是的。四个两两相邻的国家(比如一个国家被另外三个国家围成一圈)就需要四种颜色。不过,许多地图三种颜色就够了,“最少颜色”可以为屏幕上的地图找出答案。一般而言,判断一幅地图能否用三种颜色着色是一个困难问题,属于 NP 完全问题,尽管四种颜色总是足够的。
为什么贪心方法有时会用五种颜色?
它给每个国家只着色一次,从不改变主意。早先的一个选择可能让后面的某个国家被全部四种颜色包围,唯一的出路就是第五种颜色。回溯法则会退回去,修改早先的选择。
这个定理在其他曲面上成立吗?
在球面上成立:球面和平面是一样的。在环面(甜甜圈的表面)上,有些地图需要七种颜色,而七种颜色总是足够的,这是珀西·希伍德证明的。如果一个国家可以由几个分离的部分组成(比如拥有殖民地的国家),四种颜色就不再够用了。
会有数据发送到服务器吗?
不会。地图、着色方法和检查都在你的浏览器中运行。你的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器