最后更新: 2025-01-22 09:37 查看: 140 次纠错评论(0) 课件开VIP

平面图的着色

本节将介绍地图四色问题并证明平面图的五色定理。
地图的四色问题
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－可着色的。下面给出它的一个证明。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：顶点着色

下一篇：五色定理

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