|
作者：白启光
【转贴者按：本篇摘录自台湾新竹市青草湖社区大学的自然科学科普课程教材，2002年7月版的《数学嘉年华》之八。编著者为台湾交通大学应用数学系教授白启光。让我们拜读台湾学者的四色科普教材，一窥前人智慧的结晶。】
4.三色地图
接下来我们考虑三色地图的着色问题。对于这个问题我们并没有很完整的结果。1941年，布鲁克林（R. L. Brooks）证明了：“如果图中有至少5个国家，而且每一国都有三个邻国，则这张地图可以用三色或更少的颜色来着色。”在此我们不证明这个定理，但是你可以试试下面这张地图（记得外面也要着色）：
 
除此之外，坎普（A. B. Kempe）于1880年发现了另一个三色地图问题的结果：“如果每个区域（包括最外面的区域）都有偶数条边，而且每个点的秩都是3，亦即每三个区域交会于一点，则此地图正好可用三种颜色来着色。”
下图中，每个区域（包括最外面的区域）都有偶数条边，而且每个点的秩都是3，你是否能找到一个方法只用三种颜色来着色？
若我们从这张地图的一个中央区域开始着色，则因为它有偶数条边，表示它的周围有偶数个区域，所以这些区域可以交替用剩下的两色着色。如下图：
局部可以用三色着色并不能保证整张地图都可以用三色着色，但是在这里我们的确有一种方法可以顺利用三种颜色将整张地图涂满。
首先，我们分别用顺时针方向与逆时针方向的小圆圈将图中所有的点圈起来。之前我们谈过：“如果每个区域（包括最外面的那一区）都有偶数条边，则图中的点可以被涂成红色或蓝色，而且相邻的两点有不同的颜色。”因此我们知道这张图中的点可以用被涂成红色或蓝色，使得每条边所连接的两个点有不同的颜色。所以，我们可以将红色的点画上顺时针小圆圈，蓝色的点画上逆时针小圆圈。如下图：
接着，以顺时针小圆圈的点为例，我们就以顺时针方向将它所连接的三条边分别涂上黄、紫、蓝三种颜色。
  或  或 
我们也可以用类似的方法替逆时针小圆圈周围的三条边着色。
  或 或
于是依照这样的规则，在图中任选一点开始，一一将边线着上颜色。如下图：
仔细观察一下，每一块区域的边线都恰恰好只用了两种颜色。这是巧合吗？让我们看看一般的情况：
红点四周的边线颜色会依顺时针方向排列，蓝点四周的边线颜色则依逆时针方向排列。假设我们自a点开始着色如下图：
对于黄色区域而言，现在已经有颜色1与颜色3的边界。接着看f点，由于它附近的边线颜色排列方向与a点附近的相反，结果使得黄色区域的第三边仍然是颜色3，而不会是颜色2：
b点也是类似的情形，于是我们得到黄色区域的第四边是颜色1：
以此类推，最后整个黄色区域的边线颜色必是1, 3互相交替出现。其它区域的情形也是一样。而且既然黄色区域的边线颜色是1, 3，则其它邻近区域的边线颜色一定是2, 3或1, 2，否则的话，会发生相邻两条边用同一种颜色的情形，如下图：
或
既然每一区域的边线都只有两种颜色，而且相邻两区域的边线颜色不完全一样，所以我们只要将该区域涂上第三种颜色，就大功告成了。
上面的讨论，包括了我们所知有关三色地图问题的大部分规则。但目前为止，还没有人发现，可决定一张地图是否只用三色就能涂满的通则。
让我们看看下面几个图形需要多少种颜色才能完成着色？
1.下图中，两两相邻的三个区域一定得用三种颜色。
2.下图中，两两相邻的三个区域一定得用三种颜色。
3.如下面的中图所示，红线所围起来两两相邻的三个区域一定得用三种颜色。同理可推得下面的右图中红线所围区域可涂的颜色。于是我们发现蓝色所围区域同时与三种颜色的区域相邻，所以它必得用第4种颜色方可涂。
4.如下面的中图所示，红线所围起来两两相邻的三个区域一定得用三种颜色。同理可推得下面的右图中红线所围区域可涂的颜色。于是我们发现蓝色所围区域同时与三种颜色的区域相邻，所以它必得用第4种颜色方可涂。
5.在下面的台湾岛地图中，两两相邻的三个区域一定得用三种颜色。
5.四色地图
任意一张分区地图，最少需要多少种颜色来涂，使得相邻的区域都涂上不同颜色？就下图而言，我们很清楚地知道至少需要4种颜色：
任意一张分区地图，只用4种颜色来着色够吗？一百多年前，就有人针对这个问题提出了一个臆测：“任意一张分区地图，都只需要4种颜色来着色。”
是谁首先提出四色问题的？没人知道。但最先有记录可寻的是1852年，英国数学家摩根（A. de Morgan）给爱尔兰数学家汉弥顿（W. Hamilton）的一封信。信中他提到有个学生（F. Guthrie）跟他提起地图着色的问题；学生说四色就够了，但摩根找不到任何的证明。
四色问题在当时并没有立即引起大家的注意。一直到26年后，英国数学家凯利（A. Cayley）发现事情并不如大家所想的那么简单，四色问题才引起了热烈的讨论。
次年，康沛（A. Kempe）宣布他证明了四色定理。但是11年后，希悟（P. Heawood）却发现了康沛证明中的一个漏洞，四色定理又变回了四色问题。
数学家们继续努力了将近一个世纪，在1976年，美国伊利诺大学的两位数学教授阿倍尔（K. Appel）及哈根（W. Haken）才利用计算机的辅助将这个问题解决。
虽然当时康沛所发表的四色定理证明有一些瑕疵，但是却使希悟利用它证明了五色定理：“任何平面地图都能以五种颜色来着色”
这个五色定理也可以转换成另一种型式的五色定理。我们以点代表原地图的区域，两点间有边相连代表原图中两区域相邻，得到一个新的图，则五色定理就变成了：“对于任何平面图上的点而言，我们都能用五种颜色来着色，使得相邻的两点不同色。”
让我们先讨论一些平面连通图的性质：这里我们讨论的图都是正规图，所谓正规图是指图中任两点间没有重复的边，也没有两端连在同一点上的边。也就是说下面的两种情形
或
是不允许的。
1.平面图 (planar graph)：
一个图如果可以画在平面上使得所有的边都互不跨越（端点除外），即为平面图。虽然下图中的红边横跨蓝边，但是利用图的同构性质，我们可以将红边拉出来，从外面走，便得到一个平面图：
在图论中，我们称上面这两个图的关系为同构（isomorphism）。两个同构的图，它们点数相同，边数相同，点与边的关系也相同——如图中的红点，都以两条黑线与另一红点相连，并以一条绿线与绿点相连，而绿点则是分别以一条绿线与两个红点相连。
2.尤拉公式
若G为一连通平面图，则
v + f = e + 2
其中v代表G中点的个数，f 代表G中面的个数，而e是G的边数。
3.如果图 G 是一个连通的平面图，则图中的边数 (e) 一定小于等于点数 (v) 的3倍减6，即 e 3v – 6。
如果f > 1，也就是说图中有至少两个面，则每个面的边界都有至少3个边。否则就会产生下面的状况：
或
这是正规图中所不允许的。所以我们知道图中至少有3f条边界。
接着，以上图为例，由于每一条边都属于一个或两个面，但是对于红色边来说，在计算黄色区域的边界时还是被算了两次，因此
2e ≥ 3f → 2/3e ≥ f = e – v + 2（尤拉公式：f + v = e + 2）
→ 1/3e ≤ v – 2
→ e ≤ 3v – 6
4.任何正规的平面连通图都有一个点的秩小于等于5。
如果我们可以找到一个每个点的秩都大于6的正规图，则
2e = 所有秩的和 ＞ 6v → 3v ＜ e
又 e ≤ 3v–6，所以3v ＜ e ≤ 3v–6，产生矛盾。
所以任何正规图都一定有一个秩小于等于5的点。
至于五色定理“任何平面地图都能以五种颜色来着色”，我们可以用数学归纳法来证明：
我们这里只须要考虑连通图的情形，因为任意一个不连通图都可以分成几个小的连通图，若这些小连通图都能用五色来着色，则表示原本的不连通图也可以用五种颜色来着色。
首先，一个只有一个点的图一定没问题。
假设所有n – 1（n 2）个点的平面图都可以用5种颜色着色。那么对于任何n个点的平面图G，由性质4得知图中一定有一个秩小于等于5的点x。将x自G中拿掉就可以得到一个n – 1个点的图，并由归纳法假设知道，这个新图可以用5种颜色着色。
现在我们再把x放回去，若x的秩小于等于4的话，表示我们一定可以用一个颜色为x着色，而不会使得x和其它相邻的点同色。
同样地，如果x的秩等于5，但是有两个或两个以上的邻居是涂同一种颜色，则我们还是可以轻易地为x上色。
所以最后只剩下下图这种情况，x有5个邻居，每个邻居的颜色都不一样，这时x就没办法上色了。
上图中的英文字母表示点，数字表示颜色。
首先我们考虑自a出发的路径中，所有由颜色为1的点与颜色为3的点交替形成的路径—称之为1-3路径，并且假设没有这样的路径连接a与c两点。于是我们可以将这些路径中的颜色1与3互换，使得a的颜色变成3。如下：
既然c不在这样的路径上，所以c的颜色仍然是3，于是我们现在可以放心地将x涂上颜色1，而不会使x与相邻的五个点同色。
另一方面，若是a, c之间存在一条1-3路径，那么我们就考虑自b出发的路径中，所有由颜色为2的点与颜色为4的点交替形成的路径—亦即2-4路径。我们发现a, c之间这条1-3路径再加上(x, a)与(x, b)这两条边会形成一个循环，这使得b, d之间不可能有2-4路径。
因此我们可以将所有自b出发的2-4路径上的颜色2与4交换，b的颜色就变成了4，于是我们只要将x涂上颜色2，即完成这个五色图。
由数学归纳法原理，我们证明了五色定理。
四色定理的证明和五色定理的证明有点类似，但复杂得多。阿倍尔和哈根探讨平面图的结构，建构了大约1500个“不可避免的形态”，使得任何一个平面地图都可以变成点数较少的平面地图。因为形态数目过多，在证明的过程中必须利用计算机来帮忙。
下面两幅图都需要四种颜色来涂。
|
