网易首页 > 网易号 > 正文 申请入驻

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

0
分享至

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种颜色足够了!)


本文转载自《原点阅读》微信公众号

《物理》50年精选文章

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

/阅读下一篇/

国际液晶学会的创立

返回网易首页 下载网易新闻客户端
相关推荐
热点推荐
我62岁,和53岁林女士再婚,体验到了男人的第二春

我62岁,和53岁林女士再婚,体验到了男人的第二春

杨木林
2024-01-03 10:48:22
柯志恩:只要去过台湾的大陆人,回去后不会再提统一、更不提武统

柯志恩:只要去过台湾的大陆人,回去后不会再提统一、更不提武统

联友忆史
2025-01-06 16:28:00
父亲过世我不再回老家,前天侄子结婚回了老家,走到家门口愣住了

父亲过世我不再回老家,前天侄子结婚回了老家,走到家门口愣住了

岁月静好2023
2025-01-06 04:16:39
美国以色列信誓旦旦:胡塞收了中国好处,才对中国商船网开一面?

美国以色列信誓旦旦:胡塞收了中国好处,才对中国商船网开一面?

老高风云
2025-01-08 11:16:26
塔图姆:我爱死威少了 他是有史以来最出色的球员之一

塔图姆:我爱死威少了 他是有史以来最出色的球员之一

直播吧
2025-01-08 17:20:10
塔利斯卡社媒告别广州队:愿你能以更强大的姿态归来

塔利斯卡社媒告别广州队:愿你能以更强大的姿态归来

直播吧
2025-01-08 19:31:32
“韦神让我很不舒服”,北大学生评价韦东奕:老师就不该搞成网红

“韦神让我很不舒服”,北大学生评价韦东奕:老师就不该搞成网红

妍妍教育日记
2025-01-06 18:04:00
网传:某人民医院一外科医生跳楼自杀

网传:某人民医院一外科医生跳楼自杀

医务之声
2025-01-06 22:17:23
越南突然反水了?中越铁路刚有新进展,越南高层就对华露出真面目

越南突然反水了?中越铁路刚有新进展,越南高层就对华露出真面目

听风者说
2025-01-08 20:48:16
上海127-114战胜北控,赛后迎来四个好消息,王哲林越来越好了!

上海127-114战胜北控,赛后迎来四个好消息,王哲林越来越好了!

篮球资讯达人
2025-01-09 01:28:24
村委会回应给山泉水焊上钢板:喝出问题谁负责?

村委会回应给山泉水焊上钢板:喝出问题谁负责?

映射生活的身影
2025-01-08 20:40:27
中日重工巨头对比:三菱重工年营收325亿美元,三一重工多少

中日重工巨头对比:三菱重工年营收325亿美元,三一重工多少

野山历史
2025-01-08 11:55:02
彭德怀悲剧的根源:周恩来1951年的一个决定,给他的人生埋下隐患

彭德怀悲剧的根源:周恩来1951年的一个决定,给他的人生埋下隐患

拙言问史
2024-12-24 16:11:10
宝格丽晚宴合影:刘亦菲站C位尽显排面,孟子义李昀锐同框太甜了

宝格丽晚宴合影:刘亦菲站C位尽显排面,孟子义李昀锐同框太甜了

星寒新影视
2025-01-08 22:41:02
安徽富婆被割器官虐死,死前哀求:我什么都给你,只求放过我

安徽富婆被割器官虐死,死前哀求:我什么都给你,只求放过我

老黄有话
2024-08-22 08:00:03
奥斯卡入籍后近况曝光!胖得判若两人,才加盟一个月,身材就发福

奥斯卡入籍后近况曝光!胖得判若两人,才加盟一个月,身材就发福

小金体坛大视野
2025-01-08 14:43:55
是谁制止了韩国闹剧?美国出手成就了一个人,力挺尹锡悦渡劫闯关

是谁制止了韩国闹剧?美国出手成就了一个人,力挺尹锡悦渡劫闯关

大风文字
2025-01-07 17:31:20
乌军打响绝境反攻,14个旅猛攻库尔斯克,俄军炸得真过瘾!

乌军打响绝境反攻,14个旅猛攻库尔斯克,俄军炸得真过瘾!

派大星纪录片
2025-01-08 11:31:30
当71年妈妈迷上年轻人的打扮,被全网夸:不是扮嫩、是真的好看!

当71年妈妈迷上年轻人的打扮,被全网夸:不是扮嫩、是真的好看!

疯说时尚
2024-11-15 08:00:32
原公司回应“演员星星泰国失联”:他在演员通告群接到招募信息,我们也是上网才知道

原公司回应“演员星星泰国失联”:他在演员通告群接到招募信息,我们也是上网才知道

上游新闻
2025-01-06 14:52:09
2025-01-09 04:44:49
中国物理学会期刊网 incentive-icons
中国物理学会期刊网
最权威的物理学综合信息网站
3526文章数 21796关注度
往期回顾 全部

科技要闻

李开复第一个讲了出来,不再追求 AGI

头条要闻

38岁群演曾被骗至缅甸家属花百万救回:诈骗手段已升级

体育要闻

消失3年后,国乒冠军成为一名大学老师

娱乐要闻

星星女友传来好消息:已和星星见面

财经要闻

2025年,年轻人的抠门远远不止反向消费

汽车要闻

10万元级无图智驾 悦也PLUS全路况实测

态度原创

本地
时尚
数码
健康
公开课

本地新闻

韩国人来中国旅游,已经吃不了兜着走了

这3套亮眼又高级的风格,真的很好穿!

数码要闻

无线耳机狂卷CES:运动与AI成两大主旋律,听得清只是基本功

抑郁症患者称好的“乌托邦”宝地

公开课

李玫瑾:为什么性格比能力更重要?