绘制一张地图，至少需要用几种颜色才能区分不同区域？

百科 2024-09-10 07:21 北京

1852年，毕业于英国伦敦大学并从事地图着色工作的佛朗西斯·格里斯，发现了一个奇怪的现象：无论多么复杂的地图，只要用4种颜色，就可以区分有公共边界的国家和地区。

佛朗西斯觉得这中间一定有着什么奥妙，于是写信向其胞兄佛德雷克询问。佛德雷克对数学造诣颇深，但绞尽脑汁依然不得要领，只好求教于自己的老师，著名的英国数学家奥古斯都·德·摩根（Augustus DeMorgan，1806—1871）。

摩根教授怀着浓厚的兴趣，对此苦苦思索了几个昼夜，觉得无法判定佛德雷克所提的问题是对还是错。于是便写信给挚友，著名的数学家威廉·哈密尔顿（WilliamHamilton，1805—1865）探讨。哈密尔顿才华横溢，当时以发现“四元数”（一种在复数基础上扩展的新数）而饮誉欧洲。

摩根在信中希望哈密尔顿要么能证明“如果一张地图，图上任意分成许多部分，要求有共同边界的两部分涂不同颜色，那么只要4种颜色就够了”，要么构造出一个需要5种或更多种颜色的图来。

然而，智慧超人的哈密尔顿两者都没能做到。他耗费了整整13年心血，终于一筹莫展，抱恨逝去！

哈密尔顿去世后，又过了13年，一位颇有名望的英国数学家阿瑟·凯莱（Arthur Cayley，1821—1895），在一次数学年会上把这个问题归纳为“四色猜想”。并于次年，即1879年，在英国皇家地理会刊的创刊号上，公开征求对“四色猜想”的解答。从此，“四色问题”不胫而走，成为街谈巷议的热门话题。

但上述状态并没有持续很久。在征解消息发出的同年，一位半路出家的数学家肯普，发表了一个关于四色定理的证明。这使曾经出现的一时轰动很快平息下来。人们普遍以为“四色猜想”已经成为历史。不料过了11年，即1890年，一个名叫赫伍德的青年，指出了肯普在证明中的错误。从而使这一沉熄了10年之久的问题，又激发了热议。与此同时，赫伍德匠心独运，利用肯普提供的方法，成功地证明了用5种颜色能够区分地图上相邻的国家。这算是在向“四色猜想”进军中第一个重大的突破！

赫伍德关于“五色定理”的证明其实并不难。首先，他对问题加以简化：

即把下图(a)上的每个顶点，换成围绕顶点的一个小区域。很明显，如果图(b)能够用5种颜色染色，那么图(a)也一定能够用5种颜色染色。所以今后我们就只讨论顶点是3个国家界点的地图。

现在转到证明本身。设f2是边界只有两个顶点的国家数，f3是边界有3个顶点的国家数，……显然，国家总数目

f=f2+f3+f4+…

由于f2这类国家有两个顶点，因而有两条边界，从而这类国家共有2f2条边界。同理f3类国家共有3 f3条边界。如此等等。

又由于每条边界都连接着两个国家。从而，边界总数目e满足：

2e=2 f2+3 f3+4 f4+…

对于顶点总数目v，同理有

3v=2 f2+3 f3+4 f4+…

由上两式得：3v=2e

根据欧拉定理知道：

v+f=e+2

消去e可得：6f=3v+12

即 6(f2+f3+f4+…)=(2f2+3f3+4f4+…)+12

化简为：4 f2+3 f3+2 f4+f5=12+f7+2 f8+…

由于上式右端不小于12，因而左端必有一项大于0。

这样，赫伍德便得到了一个很重要的结论：“每张交点有3个国家相遇的地图，至少有1个国家边界数不多于5。”

接下去赫伍德用了数学归纳法：

证明：当国家数f=2时命题显然成立。

假令f≤k时命题成立。即对所有交点有3个国家相遇，且国家数不多于k的地图，可用5种颜色染色。

则当f=k+1时，根据前面讲的，这样的地图必有一个边数不多于5的国家。不妨令A就是这样的国家吧！

很明显，与国家A相邻的国家和区域，不外乎3种情况（如下图所示）：

(a)是有一个国家与A有两条边界，(b)是与A相邻的两个国家，本身有共同的边界；(c)是最常见的，不存在环形的情况。不难理解，无论上面3种情形的哪一种，在A的邻国中，总存在两个不相邻接的国家，如同图中的A1与A3。

现在去掉A与A1、A3的边界，则新图有k-1个国家，因而这样的图能用5种颜色染色。

设此时(A+A1+A3)染甲色;A2，A4，A5分别染乙、丙、丁色。添上两条边界，变回原图，再让A染上第五种颜色。于是，原图已被5种颜色染色。

这就是说，命题对于f=k+1也成立。

综合上述，根据归纳假设，即针对所有交点有3个国家相遇的地图，只要用5种颜色染色就足够了！

赫伍德就这样证明了五色定理。

正因为五色定理的证明不很难，所以与对待费马猜想及哥德巴赫猜想态度不同，有不少数学家小看了四色猜想。相对论的创始人，伟大物理学家爱因斯坦的数学导师赫尔曼·闵可夫斯基（Hermann Minkowski，1864—1909）教授，就是其中最为典型的一个。他认为四色猜想之所以没有解决，是因为世界上第一流的数学家还没有空去研究它。

有一次，闵可夫斯基教授给学生上课，他偶然间提到这个问题，随之即兴推演，似乎成竹在胸，写了满满一个黑板，但命题仍未得证。第二次上课，他又继续推演，结果仍旧是满怀信心进教室，垂头丧气下讲台。如此这般折腾了几个星期之后，教授终于精疲力竭。一天，他走进教室，疲惫地注视着依旧挂着“证明”的黑板。此时适逢雷电交加，他终于醒悟，并愧疚地承认：“上帝在责备我，四色问题我无能为力！”这以后，全世界数学家都掂出了“四色猜想”的沉重分量。

人类智慧面对着又一个世界难题的挑战。在正面失利之后，数学家们决定从侧面进军！

1922年，有人证明了当国家数f≤25时四色猜想成立；1938年，国家数f推进到32；1969年又推进到45。47个春秋，仅仅使国家数推进了20。主要困难是构形的可能性太多，需要做200亿次的逻辑判定，这远不是一个人的力量所能做到的！

就在这时，科学的地平线上出现了一道曙光！电子计算机的运用，使四色猜想的证实有了希望。然而在20世纪70年代初，即使是电子计算机，也要连续算上11年多！这是何等艰难的目标，但人类并没有放弃这种机会，科学家们通力合作，一面不断改进方法减少判断次数，一面继续提高计算机的计算速度，使问题的解决终于有了眉目。

1976年9月，美国伊利诺伊大学的数学家阿沛尔和哈肯教授，运用每秒计算400万次的电子计算机，在运转1200小时后，终于成功地完成了“四色定理”的证明工作。电波传来，寰宇震动！数学史上的三大难题之一，在人与计算机的“合作”之下，终于被征服了。

为纪念这一历史性的时刻与史诗般的功绩，在宣布“四色定理”得证的当天，伊利诺伊大学邮局加盖了以下邮戳：“Four colors suffice！”（4种颜色足够了！）

来源：《给孩子的数学故事书》

作者：张远南张昶

部分图源于网络

版权归原作者所有

编辑：张润昕

猜你想读

点击文章标题，可直接阅读哦~

1.科学家研究两个多世纪还没有研究出：冰为什么很滑？

2.质疑牛顿却被骂“疯子”，这位全能型科学家都经历了什么？

3.叫不同科室的医生每人给你一句忠告，他们都会说啥？

4.无穷集合之间可以相互做比较吗？

5.18k金和24k金有啥区别？为啥首饰很少用纯金打造？

原点阅读入驻小红书啦！

每天更新科普小知识

↓ 识别二维码直达主页 ↓

点个关注哟！

欢迎加入清华原点阅读和小伙伴们微信读者群

请联系微信mashuo577044（添加时请注明来意）

原点阅读

清华大学出版社科普图书品牌，全国科普阅读推广联盟会员。致力于科学普及和科技文化类图书出版，传播科学知识、科学精神、科学方法和科学理念。为读者提供客观、理性、多维、优雅的阅读产品，展现科学的迷人。

最新文章

数学怎么就越来越抽象了？

古代冬至节的基本操作

一个被数学耽误的诗人

数学史上最年轻的孤勇者

冬天的六个节气

爱因斯坦的忘年交

堪比达芬奇的天才，活出了匪夷所思的癫狂人生

好好过春节，就是珍惜我们的文化遗产

《自然-医学》：这些人的大脑比实际年龄老得更快

109年前的今天，爱因斯坦度过了一生中最焦虑的时光

解密青蛙的“语言”

小蝌蚪“变形记”

白居易的“得意”之处

高斯惊人的数论成就

为什么说他是撑起爱因斯坦的巨人

十月十五下元节：祭祀炉神送寒衣

他在野外进行大地测量，竟开创出新的数学分支

他连中学文凭都没有，却被顶级数学家极力推荐

为什么说白居易是应试达人

第二优美的数学公式

牛顿晚年沉迷于神学50余年？真相你绝对想象不到！他到底发现了什么？

日本庭园的自然主义

史上最牛中学老师

女生不擅长理科吗？来看看超越时代的数字魔女

为什么发现个无理数，就引发了数学危机

如今的人工智能，还比不上一只乌鸦吗？人工智能教父却另有担忧

常见花窗纹样辨析：芝纹&芝花纹

2024物理诺奖背后，改变历史的故事

重阳节 | 登高共醉菊花会

他的不完备定理让全世界开始反思

探索计算的极限

版贸佳作｜“丝路书香工程”项目《营建的文明：中国传统文化与传统建筑》波兰文版面世！

江南园林花窗的结构特点

天才的画作竟然与数学悖论有关