最后更新: 2025-01-22 09:37 ● 参与者查看: 25 次纠错分享参与项目词条搜索

平面图的着色

本节将介绍地图四色问题并证明平面图的五色定理。
地图的四色问题
1852 年，英国青年 Guthrie 在画地图时发现：如果相邻两国着上不同的颜色，那么画任何一张地图只需要四种颜色就够了。这就是地图的四色问题， 100 多年来，许多数学家的证明都失败了，直到 1976 年 6 月美国伊利诺斯大学两位教授阿培尔和哈根使用高速电子计算机，花了 1200 多个小时证明了地图的四色问题，终于解决了这个难题。然而至今仍有许多数学家用通常证明方法来论证四色问题，尚未得到解决。

地图的着色问题如何转化为图论问题来考虑呢？我们先给出图中桥的概念，然后给出地图的定义。

如果图 $G$ 中的边 $e$ 满足 $\omega(G-e)>\omega(G)$ ，则称 $e$ 为 $G$ 的割边（或桥）。
定义 9.5 （地图）一个没有桥的连通平面图称为地图。
地图可以有自环和多重边。地图中的每一边是两个面的公共边。两个面相邻是指两个面至少有一条公共边（而不是公共点），并且使相邻两个面着上不同的颜色，所以地图是没有桥的。

定义9．6（地图的正常面着色）设 $G$ 是一个地图，对 $G$ 的每个面着色，使得没有两个相邻的面着上相同的颜色，这种着色称为地图的正常面着色。地图 $G$ 可用 $k$ 种颜色正常面着色，称 $G$ 是 $k$－面可着色的。使 $G$ 的 $k$－面可着色的数 $k$ 的最小值称为 $G$ 的面色数，记为 $x^*(G)$ 。若 $x^*(G)=k$ ，则称 $G$ 是 $k$ 面色的。

因此，地图的四色问题可以叙述为：任何地图是 4－面可着色的。
对于一个没有自环的平面图，它的对偶是一个没有桥的连通平面图，即地图。可以证明一个没有自环的平面图 $G$ 的顶点着色问题等价于它的对偶图 $G^*$ 的面着色问题。

定理 9.9 设 $G$ 是没有自环的平面图，$G^*$ 是 $G$ 的对偶，则 $G$ 是 $k$－可着色当且仅当 $G^*$ 是 $k$－面可着色。

证明：$\Rightarrow$ 设 $G$ 是没有自环的平面图，$G$ 的对偶 $G^*$ 是一个地图。如果 $G$ 是 $k$－可着色的，则由于 $G^*$ 的每个面恰含 $G$ 中的一个顶点，把 $G^*$ 的每个面着上它所包含的顶点的颜色。因为 $G$ 是 $k$－可着色的，$G$ 中的任何两个相邻的顶点有不同的颜色，所以 $G^*$ 中任何两个相邻的面着上不同的颜色，因此 $G^*$ 是 $k$－面可着色的。
$\Leftarrow G^*$ 是 $k$－面可着色的，由于 $G$ 的每个顶点包含在 $G^*$ 的一个面中，并且 $G$ 的不同顶点包含在 $G^*$ 的不同面上，把 $G$ 中每个顶点着上它所在面的颜色。因为 $G^*$ 中没有两个相邻面着上相同颜色，所以 $G$ 中没有两个相邻顶点着上相同颜色，因此 $G$ 是 $k$－可着色的。

总之，任何没有自环的平面图是 4 －可着色的等价于任何地图是 4 －面可着色的。也就是说， ＂地图的四色问题＂可以转化为证明任何平面图的 4－可着色的。关于＂地图的五色问题＂早在 1890 年就由希伍德（Heawood）解决了，把这个问题化为证明平面图是 5－可着色的。下面给出它的一个证明。

上一篇：顶点着色

下一篇：五色定理

本文对您是否有用？有用 (0) 无用 (0)