关于地图着色问题

摘要

<正> 当你打开一幅地图时,就会看到各个不同的区域(如各省、各地区等)着上不同的颜色.早在一百多年前就有人提问:若用不同颜色来区分地图上有公共边界的两个区域,试问最少要用几种颜色才能把任何一幅地图都这样地着色?这就是地图着色问题.容易证明,仅三种颜色是不够的.例如,图1表示一个海岛上有三个区域,它们两两有公共边界,而且又都与海洋相邻接.显然,这样的一张地图要用不同颜色来区分三个区域Ⅰ,Ⅱ,Ⅲ和海洋,就得用四种不同的颜色.