地图着色

地图着色(map coloring)是一种组合构形，它是对于地图面集的一种分划，分配地图的每一个面一种颜色，使得相邻的面(指有公共边界边)具有不同的颜色，称这样一种色的分配为这个地图的一个着色，或者说，将地图的面集分划为若干个子集，使得每个子集中的任何两面均不相邻，这样就可以将每个子集中的面用一种颜色着染使得不同子集用的颜色不同，在地图M的所有着色中，使用颜色最少的着色的颜色数目称为地图M的色数，地图的顶点着色，或者说，对于与它同构的图的顶点做正常着色，就是其对偶地图的地图着色1。

基本介绍地图着色是指分配地图的每一个面一种颜色，使得相邻的面(指有公共边界边)具有不同的颜色。

将一个平面图的区域设为顶点，如果两个区域有公共边，用边连接这两个区域所转换的顶点，这样得到的图称为原平面图的对偶图。

图a的对偶图为图b。

定理1 平面图的对偶图必是平面图。

定理2（地图着色的五色定理） 任何一个平面地图都可用至多5种颜色着色。

证 给平面图中各区域着色就相当于给这个平面图的对偶图的各顶点着色。根据五色定理，任意一个平面图都至多可用5种颜色着色，所以，给任意一个平面图的所有区域着色也至多可用5种颜色。这样就得到下面的定理。

定理3（地图着色的四色定理） 任何一个平面地图都可用至多4种颜色着色2。

相关分析地图是由网络划分的一些区域所构成的图形，所谓地图着色，就是给地图的每个区域涂上一种颜色，使得相邻的两个区域涂有不同的颜色。这里规定，每个区域必须由一个单连通域构成，而两个区域相邻是指它们具有一段公共的边界线(而不仅只有一个公共点)。如图1中所示，区域1与3，2与4不能算为相邻，区域1与2，2与3，3与4，1与4才能称为相邻的区域3。

地图着色问题是指：最少需要几种颜色能够完成地图着色。著名的四色猜想为：在一个平面或球面上的任何地图能够只用四种颜色来着色3。

|| ||

为了理解四色猜想问题，我们不妨先分析一下平面或球面上能够组成一组相邻(即两两相邻)的区域数最多是几个。

先来看平面地图，我们先从最少的数目开始排列。两个区域相邻是任何人都知道的；三个区域，要每两个互相相邻，可由图2表示。若是四个区域组成一组相邻区域能行吗?由图3所示，可以做到。

显然，若是再加上一个区域——第五区域，就不能同时与1，2，3，4区域都相邻，因此，五个区域不能组成一组两两相邻的区域组。也就是说平面上能构成两两相邻的区域组里区域最多有四个。

在球面上，构成区域组的区域不会多于四个，这与平面上的情形一样。可是区域分布情形比平面上更单纯，因为在球面上没有围绕与被围绕的区别。例如从人类的立场来说，陆地被海洋围绕，可是从鱼类的立场来看，海洋却是被陆地所围绕。注意，球面上不允许出现环带状的区域，否则球面将分为上下两个不相邻的部分，这不是我们要考虑的情况。因此球面上四个区域组成一组相邻区域，分布如图4(a)所示，区域1以CD，DA，AC为界分别与区域2，3，4相邻，区域2以BD，BC为界与区域3，4相邻，区域3与4以AB为界而相邻，这样一来球面上区域相邻的情形就确定了。图4(b)所示的四面体，四面体的四个面的分布与球面上四个区域组成一组相邻区域的情形是一样。因此，要讨论球面上区域相邻情况只要讨论四面体就行了。

从以上分析的结果看出，平面上或者球面上能够构成相邻情形的区域最多数目都是四个。从这一点来看，地图着色用四种不同颜色足以区别不同的区域。但这种直观的认识是不够用来证明这一著名猜想的。

关于四色猜想问题，一个多世纪以来吸引着许多的学者与专家，普遍的看法是认为猜想是正确的，但是未必可以普谝帅l证明。1976年9月，美国伊利诺斯大学的阿贝尔(K.Appel)和哈肯(W.Hakan)宣布：在计算机的协助下证明了四色猜想。对四色同题的研究，推动了数学的发展，产生了一些新的数学理论和数学计算技巧3。

|| ||

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学