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

顶点着色

9.2 顶点着色

在这一节中，我们叙述一般图的顶点着色的概念。
定义9．4（顶点着色）设 $G$ 是一个没有自环的图，对 $G$ 的每个顶点着色，使得没有两个相邻的顶点着上相同的颜色，这种着色称为图的正常着色。图 $G$ 的顶点可用 $k$ 种颜色正常着色，称 $G$ 为 $k$－可着色的。使 $G$ 是 $k$－可着色的数 $k$ 的最小值称为 $G$ 的色数，记为 $\chi ( G )$ 。如果 $\chi(G)=k$ ，则称 $G$ 是 $k$ 色的。

例 9.1 （考试安排问题）某学校有 $n$ 门选修课程需要进行期末考试，同一个学生不能在同一天里参加两门课程的考试。问：该校的期末考试至少要几天？

解：建立一个图论模型表示这一问题：设该学校有 $n$ 门选修课 $x_1, \cdots, x_n$ ，构造图 $G(V, E)$ ， $V=\left\{x_1, \cdots, x_n\right\},\left\{x_i, x_j\right\} \in E$ 当且仅当 $x_i$ 和 $x_j$ 被同一位学生选修。

考试需要的最少天数等于 $G$ 的色数 $x(G)$ 。
设 $G$ 是连通，没有自环的图，如果有多重边，则可删去多重边，用一条边代替，因此下面考虑连通简单图 $G$ 。

有几类图的色数是很容易决定的。
定理9．6（1）$G$ 是零图当且仅当 $x(G)=1$ 。
（2）对于完全图 $K_n, x\left(K_n\right)=n$ ，而 $x\left(\overline{K_n}\right)=1$ 。
（3）对于 $n$ 个顶点构成的回路 $G_n$ ，当 $n$ 是偶数时，$x\left(G_n\right)=2$ ；当 $n$ 是奇数时，$x\left(G_n\right)=3$ 。

（4）$G$ 是二分图当且仅当 $x(G)=2$ 。
证明可以由定义很容易地给出。
对于顶点数 $n \geqslant 3$ 的图的着色特征至今没有得出，然而我们可以给出其色数上界。
定理 9.7 如果图 $G$ 的顶点最大度数为 $\Delta(G)$ ，则 $x(G) \leqslant 1+\Delta(G)$ 。
证明：只要证明图 $G$ 是 $1+\Delta(G)$－可着色的。对 $G$ 的顶点数采用归纳法。当 $n=2$ 时，$G$只有一条边，$\Delta(G)=1, G$ 是 2 －可着色的。所以 $x(G) \leqslant 1+\Delta(G)$ 。假设对于 $n-1$ 个顶点的图，结论成立。现在设 $G$ 有 $n$ 个顶点，顶点的最大度数是 $\Delta(G)$ ，如果删去任意一点 $v$ 及其相关联的边，得到 $n-1$ 个顶点的图 $G^{\prime}$ ，它的最大顶点度数至多是 $\Delta\left(G^{\prime}\right)$ ，且 $\Delta\left(G^{\prime}\right) \leqslant \Delta(G)$ 。根据归纳假设，该图是 $1+\Delta(G)$－可着色的，再将 $v$ 及其相关联的边加回该图，得到图 $G$ ，顶点 $v$的度数至多是 $\Delta(G), v$ 的相邻顶点最多着上 $\Delta(G)$ 种颜色，然后 $v$ 着上第 $1+\Delta(G)$ 种颜色。因此，$G$ 是 $1+\Delta(G)-$ 可着色的。

定理 9.7 的上界是很弱的，例如 $G$ 是二分图时，$\chi(G)=2$ ，而 $\chi(G)$ 可以取得相当大。
1941 年，布鲁克斯（Brooks）证明：使 $\chi(G)=1+\Delta(G)$ 的图只有两类：或者是奇回路，或者是完全图。布鲁克斯定理如下，证明从略。

定理 9.8 如果连通图 $G$ 的顶点的最大度数为 $\Delta(G), G$ 不是奇回路，又不是完全图，则 $\chi(G) \leqslant \Delta(G)$ 。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：对偶图

下一篇：平面图的着色

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