四色定理详解
1852年,一位年轻的数学家在给英格兰各郡的地图涂色时注意到,似乎四种颜色就足以把相邻的郡区分开来。这对每一幅可能的地图都成立吗?这个问题成为数学中最著名的难题之一,曾引出一个流传了十一年的著名错误证明,最终在1976年得到解决,而解决的方式改变了数学家对“什么算证明”的看法。
问题
弗朗西斯·格斯里曾是奥古斯都·德摩根的学生,他问道:是否任何地图都能用四种颜色着色,使共享边界的国家颜色不同?有两条规则让这个问题变得精确。国家必须是连通的,每个国家都是一整块;只在一个点相接的国家不算相邻。三种颜色显然并非总是够用,因为一个被三个两两相接的国家围成一圈的国家需要第四种颜色。问题在于,是否有时需要第五种颜色。
把地图看作图
在每个国家中标一个点,只要两个国家共享边界,就在对应的两点之间画一条线。结果就是一个图;由于地图位于平面上,这些线可以画得互不交叉:这个图是平面图。给地图着色就是给这个图的顶点着色,使每条边的两个端点颜色不同。可行的最少颜色数叫作色数,四色定理指出,没有任何平面图的色数大于四。
肯普失败的证明
1879年,身兼律师和数学家的阿尔弗雷德·肯普发表了一个证明。其巧妙的想法如今称为肯普链:沿着一条相连的国家链交换两种颜色,从而在需要的地方腾出一种颜色。这个证明被接受了十一年,直到1890年珀西·希伍德发现了其中的漏洞。希伍德的修补证明了一个较弱的结果:五种颜色总是足够的。肯普链保留了下来,并成为最终证明中的一个工具。
为什么五色容易
每个平面图都有一个最多只有五个邻点的顶点;这可以由欧拉公式推出,该公式限定有 n 个顶点的平面图最多有 3n − 6 条边。去掉这样一个顶点,用同样的论证给地图的其余部分着色,再把这个顶点放回去。如果它的邻点用了不到五种颜色,就有一种颜色空闲。如果它们用了全部五种颜色,一次肯普链交换总能腾出一种。若只有四种颜色,同样的交换可能失败,这正是肯普忽略的漏洞。
计算机证明
1976年,伊利诺伊大学的肯尼斯·阿佩尔和沃尔夫冈·哈肯证明了这一定理。他们证明了每幅地图都至少包含一个不可避免集中1936种构形之一,而且每种构形都是可约的:需要五种颜色的最小地图不可能包含它。检验可约性耗费了一千多小时的计算机时间,远远超出人工验证的能力。许多数学家对一个无人能完整读完的证明感到不安,关于计算机辅助证明的争论由此开始。
更简单的证明与完全验证
1996年,尼尔·罗伯逊、丹尼尔·桑德斯、保罗·西摩和罗宾·托马斯发表了一个更系统的证明,包含633种构形,仍由计算机检验,但更容易验证。2005年,乔治·贡蒂耶和本杰明·韦尔纳在 Coq 证明助手中将整个证明形式化,由一个小而可信的程序检查每一个逻辑步骤。如今,四色定理是数学中经过最彻底验证的结果之一。
着色算法
在实际中,为给定地图找到一种四色着色很快,但为一般的图找出最少颜色数却很困难:判断三种颜色是否足够是 NP 完全问题。实用方法包括按度数递减顺序进行的贪心着色、接着总给约束最多的顶点着色的 DSATUR,以及探索各种选择、卡住时撤销选择的回溯搜索。图着色可以安排没有冲突的考试时间表,分配无线电频率使相邻发射机互不干扰,还能在编译器中分配寄存器。
动手探索
打开四色地图涂色器,生成含 4 到 120 个国家的地图,用四种颜色亲手涂色,看冲突以红色显示出来。让贪心着色、DSATUR 或回溯法一步一步地求解地图,显示相邻国家构成的图,并检查这幅地图真正需要的最少颜色数。
常见问题
这个定理对绘制地图的人有帮助吗?
几乎没有。为了清晰,真实的地图通常使用更多颜色,而且其中有海洋、湖泊和由几块组成的国家,这些都不在定理的范围内。它的重要性在于数学:它推动了图论的发展,并引出了什么才算证明的问题。
什么是肯普链?
取两种颜色,比如红色和蓝色,以及一个红色的国家。它的肯普链就是从它出发、只经过红色和蓝色邻国所能到达的全部红色和蓝色国家。在整条链上交换红色和蓝色,着色仍然有效,并且可以为紧挨着这条链的某个国家腾出一种颜色。
为什么由几块组成的国家会使定理失效?
如果一个国家可以由几个分离的区域组成,而这些区域必须同色,那么相邻关系图就不再是平面图,可以构造出需要更多颜色的地图:每个国家由两块组成时,所需颜色数可达不超过 12 的任意值,希伍德在他的“帝国问题”中研究过这一点。
为什么涂色器用点来生成地图?
每个国家都是正方形中离某个随机点比离其他任何点都近的区域,即沃罗诺伊图。这样得到的地图看起来很逼真,国家都是凸的,而且两个国家恰好在它们的区域共享一段边界时才相邻,应用会精确地计算这一点。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开四色地图涂色器