最后更新: 2025-01-21 18:19 查看: 224 次纠错评论(0) 课件开VIP

平面图的五色定理

定理7－6．3 任意一个简单的连通平面图点着色至多五色
首先，我们证明 $G$ 中一定存在一个顶点，其度数小于等于 5。用反证法，若每一个顶点度数均大于 5 ，所以 $d ( v ) \geq 6$ ，即有 $\sum d ( v ) \geq 6|V|$ ，即 $2|E| \geq 6|V|$ ，即 $|E| \geq 3|V|$ 。但 $G$ 是简单的连通平面图，由定理2有 $|E| \leq 3|V|-6$ ，显然产生矛盾。矛盾说明，原图至少有一个顶点度数小于等于 5 。
下面对图的顶点用归纳法来证明五色定理。
当 $n=|V| \leq 5$ 时，结论显然成立。
归纳假设对小于等于 $n-1$ 顶点的图，定理成立。
下面看有 n 个顶点的图。
证明：
由前面知，此图一定有一个顶点记为 $v_0, d\left(v_0\right) \leq 5$ 。从图 $G$中擦去 $v_0$ 得一个 $G$ 的子图，它有 $n-1$ 个顶点，且是连通的平面图，并可以 5 着色。我们对它施行一种着色，使得它用红 ，白，黄，蓝，黑五种颜色刚好对这个子图的每一个顶点着上一种颜色，且相邻接顶点着不同颜色。

若 $d\left(v_0\right)<5$ ，或 $d\left(v_0\right)=5$ ，但与 $v_0$ 邻接的这些顶点仅着了四种颜色，则 $v _0$ 可着第 5 种颜色，定理成立（见下图）。
 ![图片](/uploads/2025-01/a89b6b.jpg)
 
 若 $d\left(v_0\right)=5$ ，且和 $v _0$ 邻接的 5 个顶点着的是 5 种不同颜色，如图。
$v _1$ 着黄色，与 $v _1$ 相邻的其余顶点中，一定有一个着白色的，否则 $v _1$ 可以改着白色，而 $v _0$ 着黄色，定理得证。
 ![图片](/uploads/2025-01/513042.jpg)

设 $v_{i 1}$ 和 $v_1$ 相邻，且 $v_{i 1}$ 着白色，与 $v_{i 1}$ 相邻接的顶点中，一定有着黄色的，否则 $v _{i 1}$ 着黄色， $v _1$ 着白色， $v _0$ 着黄色．．．。由上我们可以得到图中一条黄白两色顶点交错的线。这条线若最后可以通到 $v_3$ ，则得到一条从 $v_1$ 到 $v_3$ 的封闭的黄白交错的圈（包括 $v _0$ ），也有可能这条线无论怎样都走不到 $v _3$ 。

如果黄白线无论怎样都走不到 $v _3$ ，此时我们可以把这条线的顶点着色改一下，着黄色的改为着白色，着白色的改为着黄色。此时 $v _0$ 可着黄色。
 ![图片](/uploads/2025-01/3fcf9d.jpg)
 
 如果黄白线走到 $v _3$ ，我们看 $v _2$ 与 $v _5$ ，如法炮制，从 $v _2$ 出发产生蓝红线。若蓝红线无论怎样都走不到 $v _5$ ，此时我们可以改动这一条线上顶点着色，v2改着红，把着红改为着蓝，着蓝的改为着红。此时，v0可着蓝色。
  ![图片](/uploads/2025-01/3a93d9.jpg)
  
  如果蓝红线也走到 $v _5$ ，即我们得到一条从 $v_2$ 到 $v_5$ 的封闭的蓝红交错的圈（包括 $v _0$ ）。此时，黄白线与红蓝线一定相交，因为是平面图，交点也是顶点，则交点着色产生矛盾，即交点在黄白线上应着白色或黄色，又交点在红蓝线上应着红色或蓝色。矛盾说明此情况不可能发生。定理得证。
   ![图片](/uploads/2025-01/2fc89f.jpg)

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：四色定理

下一篇：韦尔奇·鲍威尔(WelchPowell)着色法

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