图书序言
第15章 地图着色
西洋棋盘只需要两种颜色,就能涂满整个盘面,方法是让紧邻(共用一条边线)的两个小方格各涂上不同颜色。有些地图也是一样,只需两种颜色就可以涂满,使相邻的国家有不同的颜色,但是有些地图就做不到了。
为了简单起见,当我们说「能以两种颜色着色的地图」或「两色地图」时,我们指的是只要用两种不同的颜色,就可以把整张地图涂满,而且那些共享至少一条边线的国家,会有不同的颜色。同样的,在本章稍后,我们可能会谈到「用三种不同的颜色涂满地图」或者说「一张五色地图」,都是指:共享一条边线的国家颜色不同。
我们假设前面两张地图,画的都是一个有很多国家的大岛。我们称那些国界的交叉点为「顶点」,而不在海岸线上的顶点则称为「内陆顶点」。而「顶点的次数」是指交会在这个顶点的边线数目。这种观念已经在第7章扮演过关键性的角色。
那些海岛上有众多国家的地图里,由于包围内陆顶点的国家必须交替着上不同的颜色,因此若有个内陆顶点的次数是奇数的,这张地图就没办法用两种颜色来着色。我们因此得到下列定理:
定理1:如果一个海岛上有许多国家的地图能用两种颜色来着色,则每个内陆顶点的次数都是偶数。
至于四色地图的问题,可以回溯到1852年的10月23日,是梅氏(K. O. May)提出的。就在这一天,古斯瑞(Francis Guthrie)把它拿给他的老师,逻辑学家笛摩根(Augustus De Morgan, 1806-1871)看,而笛摩根则写信问哈密顿(W. R. Hamilton, 1805-1865):
我的学生今天就一件事问我原因何在。他认为这件事是一项事实,但我不那么确定,以前也没注意到。他说如果把一个图形随意分割,并且把每块区域涂上不同的颜色,使得同一条边线的两边颜色不同,则只需要四种颜色就一定够了,甚至更少些……
你认为如何?如果真的是这样,你以前知道吗?我的学生说他曾以英格兰的地图来做实验。这件事,我愈想愈觉得它是真确的。