任何地图只需四种颜色就能让相邻区域不同
四色定理断言:平面或球面上的地图,无论多复杂,四种颜色足矣。
到底是怎么回事
四色定理是图论的一个著名结果:任何一张地图(平面或球面),若两个区域有公共边界(不止一个点),则至少需要四种颜色才能保证相邻区域颜色不同。这条定理1852年被提出,但直到1976年才由肯尼斯·阿佩尔和沃尔夫冈·哈肯借助计算机首次证明,成为第一个依赖计算机的著名数学定理。
多知道一点
证明思路是将地图转化为平面图,然后利用图的可平面性质。阿佩尔和哈肯的程序检查了超过1900种不可约构型,耗时1200小时。后来证明被简化,但争议始终存在:数学家们希望找到纯人脑可理解的证明。2013年,格奥尔格·贡蒂尔用Coq证明辅助软件给出了形式化证明。
没想到吧
如果有人给你画一张“需要五种颜色”的地图,那它一定不是画在平面或球面上——比如环形甜甜圈表面(环面)的地图,最多需要七种颜色。另外,四色定理只适用于每个区域都是单连通区域(无飞地),现实中像阿拉斯加与美国本土就需要特殊处理。