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

五色定理

定理 9.10 任何平面图 $G$ 是 5－可着色的。
证明：不妨设 $G$ 是平面简单图。对 $G$ 的顶点数采用数学归纳法。当 $n \leqslant 5$ 时结论成立。假设 $n-1$ 个顶点的所有平面简单图 $G$ 是 5－可着色的。考虑 $n$ 个顶点的平面简单图 $G$ ，由定理 9．2，在 $G$ 中存在顶点 $v_0$ ，使 $d \left(v_0\right) \leqslant 5$ 。由归纳假设，$G-v_0$ 是 5 －可着色的，在给定 $G-v_0$ 的一种着色之后，将 $v_0$ 及其关联边加回到原图中，得到 $G$ ，分两种情况。
（1）如果 $d\left(v_0\right)<5$ ，则 $v_0$ 的相邻点已着上的颜色小于等于 4 种，所以 $v_0$ 可以着另一种颜色，使 G 是 5 －可着色的。
（2）如果 $d\left(v_0\right)=5$ ，则将 $v_0$ 的相邻点依次记为 $v_1, v_2, \cdots, v_5$ ，并且对应的 $v_i$ 点着第 $i$ 色。
设 $H_{13}$ 为 $G-v_0$ 的一个子图，它是由色 1 和色 3 的顶点集导出的子图。如果 $v_1$ 和 $v_3$ 属于 $H_{13}$ 的不同分支，将 $v_1$ 所在分支中着色 1 的顶点和着色 3 的顶点进行颜色对换，这时 $v_1$ 着色 3 ，并不影响 $G-v_0$ 的正常着色。然后在 $v_0$ 着色 1 ，因此 $G$ 是 5 －可着色的。

如果 $v_1$ 和 $v_3$ 属于 $H_{13}$ 的同一分支，则在 $G$ 中存在一条从 $v_1$ 到 $v_3$ 的路，那么这条路与 $\left(v_1, v_0\right.$ ， $\left.v_3\right)$ 一起构成一条回路，并且该回路或者将 $v_2$ 围在里面，或者把 $v_4$ 和 $v_5$ 围在它里面。因为 $G$ 是平面图，在任何一种情况下，都不存在连接 $v_2$ 和 $v_4$ 的一条路。现在设 $H_{24}$ 为 $G-v_0$ 的另一个子图，它是由着色 2 和色 4 的顶点集导出的子图，则 $v_2$ 和 $v_4$ 属于 $H_{24}$ 的不同分支，所以在 $v_2$ 所在分支中将着色 2 的顶点和着色 4 的顶点进行颜色对换，$v_2$ 着色 4 ，这样导出了 $G-v_0$ 的另一种正常着色。然后在 $v_0$ 着色 2 ，同样得到 $G$ 是 5 －可着色的。

二色定理
定理 9.11 地图 $G$ 是2－面可着色的当且仅当它是一个欧拉图。
证明：$\Rightarrow$ 设地图 $G$ 是2－面可着色的，对于 $G$ 中任意一个顶点 $v$ ，围绕顶点 $v$ 的面必为偶数个，于是可推出 $v$ 是偶顶点，由定理 8.14 ，可知 $G$ 是欧拉图。
$\Leftarrow$ 设 $G$ 是欧拉图，则由定理 8.16 可知 $G$ 可分解成若干个边不相重的回路的并。对图的回路数 $p$ 采用数学归纳法。当 $p=1$ 时，$G$ 是 2 －面可着色的。假设回路数为 $p-1$ 的地图 $G$ 是 2 －面可着色的。对于由 $p$ 条回路构成的地图 $G$ ，由于 $G$ 的每个顶点都是偶顶点，在 $G$ 中删去一条回路，得到图 $G^{\prime}, G^{\prime}$ 的每个顶点的度数也是偶数。根据归纳假设，$G^{\prime}$ 是 2 －面可着色的。再把删去的回路加回到 $G^{\prime \prime}$ 中得到 $G$ ，并且使这条回路外的所有面的颜色保持不变，而回路所围的各面已着两种颜色，将这两种颜色对换，得到 $G$ 是 2－面可着色的。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：平面图的着色

下一篇：边的着色

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