国家数量
边界
已用颜色
冲突

更多关于四色定理

四色定理地图涂色器

无论地图多么复杂,四种颜色总能把它涂好,让共享边界的国家永远不同色。这个命题简单到孩子用蜡笔就能检验,证明它却花了一个多世纪,还动用了计算机。亲手给一幅随机地图涂色,看看哪些边界发生冲突,再观看三种方法完成着色:从有时需要第五种颜色的快速贪心规则,到总能用四种颜色完成的回溯搜索。 选一种颜色,点击国家为其涂色;两个相邻国家颜色相同时,它们之间的边界会变红。只在一个角上相接的国家可以同色。也可以交给计算机:选择一种方法,按“求解”观看全过程,或按“单步”一步一步地跟着看。“最少颜色”会检查这幅地图是否用三种甚至两种颜色就够了。“新地图”会生成另一幅地图,“显示相邻关系”会画出共享边界的国家之间的网络。

它是如何运作的

  1. 选择国家数量并按“新地图”,或者从当前显示的地图开始。
  2. 选一种颜色,点击国家为其涂色,留意相邻国家冲突时出现的红色边界。
  3. 选择一种方法,按“求解”或“单步”观看它为地图着色;按“最少颜色”查看这幅地图需要几种颜色。

从地图到图

在每个国家里放一个点,两个国家共享边界时,就把对应的两个点连起来。地图就变成了一个图,给地图着色等同于给这些点着色,使相连的点颜色不同。由于地图画在平面上,这些图是平面图:可以画得没有任何交叉的线。只在一个点相接的国家(比如在一个角上相会的四个正方形)不算相邻。四色定理指出,每个平面图都可以用四种颜色着色。打开“显示相邻关系”,即可看到当前地图的图。

三种着色方法

贪心着色逐个处理国家,邻国最多的先处理,并给每个国家分配其邻国尚未使用的第一种颜色。它速度快但目光短浅,在某些地图上会用到第五种甚至第六种颜色。DSATUR 由丹尼尔·布雷拉于1979年提出,它总是接着选择邻国已呈现出最多不同颜色的那个国家,通常能避开上述陷阱。回溯法依次尝试各种颜色,当某个国家已无颜色可用时,就撤销最近的选择并重新尝试;它总能找到四色着色方案,有时要回退许多次。

常见问题

为什么四种颜色总是足够?

至今没有人找到简短的理由。肯尼斯·阿佩尔和沃尔夫冈·哈肯在1976年给出的证明表明,每幅地图都必定包含1936种小构形之一,而且每种构形都可以先移除、之后再恢复着色;检查全部构形耗费了一千多小时的计算机时间。1996年,尼尔·罗伯逊、丹尼尔·桑德斯、保罗·西摩和罗宾·托马斯给出了一个更简单的计算机证明,只需633种构形;2005年,乔治·贡蒂耶用 Coq 证明助手完整地验证了一个证明。

有些地图需要全部四种颜色吗?

是的。四个两两相邻的国家(比如一个国家被另外三个国家围成一圈)就需要四种颜色。不过,许多地图三种颜色就够了,“最少颜色”可以为屏幕上的地图找出答案。一般而言,判断一幅地图能否用三种颜色着色是一个困难问题,属于 NP 完全问题,尽管四种颜色总是足够的。

为什么贪心方法有时会用五种颜色?

它给每个国家只着色一次,从不改变主意。早先的一个选择可能让后面的某个国家被全部四种颜色包围,唯一的出路就是第五种颜色。回溯法则会退回去,修改早先的选择。

这个定理在其他曲面上成立吗?

在球面上成立:球面和平面是一样的。在环面(甜甜圈的表面)上,有些地图需要七种颜色,而七种颜色总是足够的,这是珀西·希伍德证明的。如果一个国家可以由几个分离的部分组成(比如拥有殖民地的国家),四种颜色就不再够用了。

会有数据发送到服务器吗?

不会。地图、着色方法和检查都在你的浏览器中运行。你的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器