地图着色引出的数学问题

作者: 唐雪桃

一张地图,上面标示着许多国家或地区,还有高原、海洋、城市。看上去好似“五颜六色”。但是,你如果仔细观察,就会发现地图的色彩并不多,仅仅4种,为什么4种就够了呢?这一看似非常简单的问题,曾使得许多数学家大伤脑筋,留下了篇篇佳话。

1852年,美国年轻的绘图员法兰西斯·古特里在给英国地图涂颜色时发现,如果相邻两个地区用不同颜色涂上,只需4种颜色就够了。他画了许多不同形状的图形,希望能找到一个必须用5种颜色才能区别的图,但未能成功,他不明白其中的道理,于是就去请教他正在大学数学系学习的哥哥费特里。费特里画了很多图进行验证,证明他弟弟的发现是对的,但是他却不能用数学方法加以证明,也解释不了其中的道理,于是,他就去请教老师和当时的一些知名数学家。

当时,许多数学家都认为地图着色的问题太容易了,未予重视。比如数学家明可夫斯基在一次给学生讲课时,偶尔提到这个问题,他说:“地图着色问题之所以一直没有获得解决,那仅仅是由于没有第一流的数学家来解决它。”说完,他拿起粉笔,要当场给学生推导出来,结果没能成功,第二节课他继续试,还是没有眉目,一连几堂课下来竟毫无结果,数学家非常尴尬。一天,天下大雨,他刚跨进教室,突然雷声轰响,震耳欲聋,他幽默地对学生说:“这是上天在责备我狂妄自大,我证明不了这个问题。”

1878年,英国著名数学家凯莱把这个问题公开通报给伦敦数学学会的会员,取名为“4色问题”,征求证明。顿时,数学界沸腾了。

首先宣布证明了4色问题的是一个叫肯泊的律师,他于1879年公布了自己的证明方法。可是过了 11年,一位29岁的年轻数学家赫伍德成功地使用了肯泊的方法证明出平面地图最多用5种颜色就够了。这就是著名的五色定理。赫伍德一生主要研究的就是4色问题,在以后60年的时间里,他发表了关于4色问题的7篇主要论文。

在随后的近百年里,人们一直在研究4色问题,也取得了一定的成就,但是存在的一个最大困难是数学家提供的方法太复杂。直到1976年,美国数学家阿佩尔与哈肯,用3台高速电子计算机,运行了 1200小时,作了 100亿个判断,终于证明了4色问题是对的。人类第一次依靠机器解决了延续百多年的数学难题。