地图为什么用4种颜色色标示?

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/02 08:45:08
地图为什么用4种颜色色标示?

地图为什么用4种颜色色标示?
地图为什么用4种颜色色标示?

地图为什么用4种颜色色标示?
1852年,英国伦敦大学学生弗兰克林.格思里首先提出了这个问题.即:一切地图,都只需要四种颜色,即可标示出所有国家的边界,根本就不需要第五种颜色
1976年美国的阿普尔(K.Appel),黑肯(W.Hakan)和考齐(J.Koch)等三人依靠计算机证实了四色猜想.将每个区域用一个圆圈(通常称它为结点)表示,结点间的连线表示这两个区域相邻,则图4所示的图(网)状结构很好地表达了图所示地图中行政区的相互关系.
将行政区图抽象成图状结构之后,着色问题就成了:如何为顶点着色使每条边的两个端点具有不同的颜色.求着色问题的最优解是很困难的,但有一种简单的求近似解的方法:先用一种颜色给尽可能多的互不相邻的结点(即不是同一条连线的两个端点)着色.然后用另一种颜色在未着色结点中给尽可能多的结点着色,如此反复直到所有结点都已着色为止.用这种方法对图4着色,可以得到以下的一组解.
(1)红色 A C E (2)黄色 B D F(3)绿色 G I (4)蓝色 H