地图四色问题

《地图四色问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、地图四色问题地图四色问题地图四色问题《人民日报》发表了一篇中国著名科学家钱学森所撰写的文章：《现代科学技术》。这是一篇出色的文稿，对于了解中国科学技术现代化会往什么方向前进，该文作了不少的披露。数学爱好者都会注意到钱学森在文章中所提的一件事：“去年数学界哄动一时的一件事，是用电子计算机证明了数学上的四色定理。画地图要求相邻两国不用同一色，一幅地图只需要四种颜色。要证明这个定理很难，数学家经过上百年的努力，证明不了。去年美国数学家用电子计算机证明了。他们看到这个问题要证明并不是不可能，而是证明的步骤、程序很复杂，人一辈子的时间也证不完

2、。他们把程序编好，交给高速的电子计算机去干。高速电子计算机也用了一千多个小时才证出来。美国数学家认为，他们的主要贡献不是在证明了四色定理，而在运用电子计算机完成了这件人没有能够完成的事。”“地图四色问题”在钱学森的文章里已经清楚地解释了。你大概会很惊奇，这甚至连懂得拿起彩笔涂鸦的小孩都会发觉到的问题，确是一个数学问题吗？是的，这是一个数学上著名的难题，许多大数学家曾经尝试想去解决它而不成功，可是这个问题看来又是那么容易明白，好像谁都可以很快解决它似的。我在这里要介绍这个问题的来源，以及美国数学家解决它的经过。害怕数学的读者不必顾虑，

3、我的解释都很浅白，相信你是会看懂的。问题的来源在1852年，英国有一个年青人叫法兰西斯·古特里，他在画英国地图涂颜色时发现：如果相邻两国用不同颜色涂上，地图只需要四种颜色就够了。他把这发现告诉他念数学的哥哥费特里，并且画了一个图给他看。这个图最少要四种颜色，才能把相邻的两部分分辨，颜色的数目再不能减少。他的哥哥相信弟弟的发现是对的，但是却不能用数学方法加以证明，也解释不出其中的道理。　　这年10月23日，费特里拿这个问题向伦敦大学的数学教授奥古斯都·德·摩根请教。德·摩根是当时英国著名的数学家，他也不能马上解释。他于当天写一封信给在

4、三一学院的好朋友威廉·哈密尔顿。他相信像哈密尔顿这样聪明的人——少时就已经会讲八种以上外语，而且数学和物理都很好——是可以帮助他解决这问题的。在信中，他曾这样写道：“今天我的一个学生要我告诉他一个事实的理由，而我却对于这个是否是事实，现在还是不知道。他说如果在面上画一个图，使两个有共同边缘的区域涂上不同颜色，那么或许四种颜色而不需要更多就足够了。请问难道不能够造出一个需要五种或更多颜色的图形出来吗？”很可惜哈密尔顿或许以为这个问题是太浅显了，而不去注意它。过了8年了。1860年4月14日，德·摩根在一本杂志评价一部叫《发现的哲学》的

5、书时写了这样的话：“当一个人画地图——一个国家的地区图，很明显的他需要许多彩色笔使到每对相邻区域涂上不同颜色。但涂颜色图的工人却很早便知道只用四种颜色就足够了。……在一个邻域我们不需要四个颜色，除非有四个区域，这四个区域每一个都和其他三个区域交界，而其中的一个区域一定会完全被其他的区域包围起来。可是这个原理：四个区域不可能在没有一个被其他区域包围的情况下，使到每一个区域都和其他的三个区域交界。我们深信是不足以证明这样明显这样简单的事实：这事实应该像一个公理那样……。”直到1878年英国数学家凯利在英国数学学会以及皇家地理学会提出这个

6、“地图四色问题”，这问题才受人注意。第二年有一个律师肯泊自称发现了证明的方法。可是在1890年一位才29岁的年青人希渥特发现他的证法存有漏洞。希渥特在牛津大学受教育，他主要的研究是这个“地图四色问题”，在以后60年漫长时间，他先后发表这方面七篇重要的论文。他78岁才退休，而在85岁时还向伦敦数学学会提呈他最后一篇关于这问题的研究论文。希渥特在世时没有解决这问题，但他证明了“地图五色问题”是对的。他那种老弥而坚，孜孜不倦，顽强攻关的精神是值得我们学习的。转化成数学问题我们现在把这地图着色问题转化成数学问题来考虑。在特定的地图上，每一个

7、区域当中画一个小圈圈，我们称为顶点。如果一对区域相邻，我们就用一条弧，把其中的顶点连起来。这样我们就得到数学上称为图的东西。例如由图一我们得到底下的图：一个图G称为k可染，如果它的每个顶点可以用k种不同的颜色之一来涂，使得相邻顶点具有不同颜色。如果一个图是k可染而不是可染，我们就说它的染色数是k。例如图三中的图的染色数是4。读者试试验证底下的图分别具有染色数：2，3，2，5。从地图转变出来的数学图，在数学上称为平面图，它是指那些顶点能画在平面上，使到没有两条弧会相交。图三及图四的，，都是平面图，但图四的不是平面图。比方说下面图五是不

8、是平面图呢？你会说不是！因为弧AC和弧BD是相交。可是如果我不要将BD弧那样画，稍微移动一点，使它像图五那样，这时你得到的是平面图了！　　怎么样判断一个图是不是平面图呢？在1930年波兰数学家库拉托斯基发现一个简单的判别法则，那就是：