地图四色问题
-女神节图片
地图四色问题
《人
民日报》发表了一篇中国著名科学家钱学森所撰写的文
章：
《现
代科学技术》
。这是一篇出色的文稿，对于了解中国
科学技术现
代化会往什么方向前进，该文作了不少的披露。
数学爱好者都
会注意到钱学森在文章中所提的一件事：
“
去年
数学界哄动一时的一件事，是用电子计算机证明了数学上的
四色定理。画地图要
求相邻两国不用同一色，一幅地图只需
要四种颜色。要证明这个定理很难，数学家经过上
百年的努
力，证明不了。去年美国数学家用电子计算机证明了。他们
看到这个问题要证明并不是不可能，而是证明的步骤、程序
很复杂，人一辈子的时间
也证不完。他们把程序编好，交给
高速的电子计算机去干。高速电子计算机也用了一千多
个小
时才证出来。美国数学家认为，他们的主要贡献不是在证明
了四色定理，而在运用电子计算机完成了这件人没有能够完
成的事。
”
“
地图四色问题
”
在钱学森的文章里已经清楚地解释了。你大
概会很
惊奇，这甚至连懂得拿起彩笔涂鸦的小孩都会发觉到
的问题，确是一个数学问题吗？
是的，这是一个数学上著名的难题，许多大数学家曾经尝试
想去解决它而不成功，可是这个问题看来又是那么容易明
白，好像谁都
可以很快解决它似的。
我在这里要介绍这个问题的来源，以及
美国数学家解决它的
经过。害怕数学的读者不必顾虑，我的解释都很浅白，相信
你是会看懂的。
问题的来源
在
1852
年，英国有一个年青人叫法兰西斯
·
古特里，他在画
英国地图涂颜色时发现：如果相邻两
国用不同颜色涂上，地
图只需要四种颜色就够了。
他把这发现告诉他念数学的哥哥费特里，并且画了一个图给
他看。这个图最
少要四种颜色，才能把相邻的两部分分辨，
颜色的数目再不能减少。他的哥哥相信弟弟的
发现是对的，
但是却不能用数学方法加以证明，也解释不出其中的道理。
这年
10
月
23
< br>日，费特里拿这个问题向伦敦大学的数学
教授奥古斯都
·
德
·
摩根请教。德
·
摩根是当时英国著名的数学
家，他也不能马上解释。他于
当天写一封信给在三一学院的
好朋友威廉
·
哈密尔顿。
他相信像哈密尔顿这样聪明的人
——
少时就已经会讲八种以上外语，而且数学和物理都很好
——
是可以帮助他解决这问题的。
在信中，
他曾这样写道：
“
今天我的一个学生要我告诉他一个
事实的理由，
而我却对于这个是否是事实，
现在还是不知道。
他说如果在面上画一个图，使两个有共同边缘的区域涂上不
同颜色，那么或许四种颜色而不需要更多就足够了。请问难
道不能够造
出一个需要五种或更多颜色的图形出来吗？
”
很可惜哈密尔顿或许以为这个问题是太浅显了，而不去注意
它。
过了
8
年了。
1860
年
4
月
14
日，德
·
摩根在一本
杂志评价一
部叫
《发现的哲学》
的书时
写了这样的话：
“
当一个人画地图
——
一个国家的地区图，很明显的他需要许多彩色笔使到每
对相邻区
域涂上不同颜色。但涂颜色图的工人却很早便知道
只用四种颜色就足够了。
……
在一个邻域我们不需要四个颜
色，除非有四个区
域，这四个区域每一个都和其他三个区域
交界，而其中的一个区域一定会完全被其他的区
域包围起
来。可是这个原理：四个区域不可能在没有一个被其他区域
包围的情况下，使到每一个区域都和其他的三个区域交界。
我们深信是不足以证明这
样明显这样简单的事实：这事实应
该像一个公理那样
……
。
”
直到
1878
年英国数学家凯利在英国数学学会以及皇家地理
学会提出这个
“
地图四色问题
”
，这问题才受人注意。
第二年有一
个律师肯泊自称发现了证明的方法。
可是在
1890
年一位才
29
岁的年青人希渥特发现他的证法存有
漏洞。希
渥特在牛津大学受教育，他主要的研究是这个
“
地图四色问
题
”
，在
以后
60
年漫长时间，他先后发表这方面七篇重要的
论文。他
78
岁才退休，而在
85
岁时还向伦敦数学学会提呈
他最后一篇关于这问题的研
究论文。
希渥特在世时没有解决这问题，但他证明了
“
地图五色问题
”
是对
的。他那种老弥而坚，孜孜不倦，顽强攻关的精神是值
得我们学习的。
< br>
转化成数学问题
我们现在把这地图着色问题转化成数学问题来考虑。在特定<
/p>
的地图上，每一个区域当中画一个小圈圈，我们称为顶点。
如果一
对区域相邻，
我们就用一条弧，
把其中的顶点连起来。
这样我们就得到数学上称为图的东西。
例如由图一我们得到底下的图：
<
/p>
一个图
G
称为
k
可染，
如果它的每个顶点可以用
k
种不同的
颜色之一来涂，使得相邻顶点具有不同颜色。如果一个图是
k
可染而不是可染，我们就说它的染色数是
k
。例如图三中
的图的染色数是
4
。
读者试试验证底下的图分别具有染
色数：
2
，
3
，
2
，
5
。<
/p>
从地图转变出来的数学图，在数学上称为平面图，它是指那
些顶点能画在平面上，使到没有两条弧会相交。图三及图四
的，
，都是平面图，但图四的不是平面图。比方说下面图五
是不是平面图
呢？你会说不是！
因为弧
AC
和弧
BD
是相交。
可是如果我不要将
BD
弧那样画，稍微移动一点，使它像图
五那样，
这时你得到的是平面图了！
怎么样
判断一个图是不是平面图呢？在
1930
年波兰数
学家库拉托斯基发现一个简单的判别法则，那就是：如果一
个图不包含底下两
种图为子图，那么这图就是平面图。
在图六的两个图事实上是
一样的东西，你只要把一些顶点适
当安排，这两个图就可以互相变来变去。就像《西游记
》里
的孙悟空摇身变成土地庙，但本质还是不变，只是外形不一
样，在数学上就称这样的东西为同构。
现在地图四色问题，就
转化为底下的问题：是否地图包含的
所有子图平面图都是
4
可染？如果答案是肯定的话，那么地
图四色问题也就解决了。
反过来说，如果你能构造出一个平面图，它不是
4
可染，而
是具有染色数大于或等于五，那么
“
地图四色问题
”
就被否定
了。
容易解决五色问题
英国数学家希渥特很早就证明了地图六色及五色问题。现在<
/p>
介绍一个比较简单而且有技巧的
“
地图五
色问题
”
的证法。
在这个证明中关键的东西是：在平面图里找一个顶点，它最