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

边的着色

定义 9.7 （边的着色）设图 $G$ 是没有自环的，若对 $G$ 的边着色，使得没有两条相邻的边着上相同的颜色，称此种着色为正常边着色。 $G$ 的边可用 $k$ 种颜色正常边着色称 $G$ 是 $k$－边可着色。使 $G$ 是 $k$－边可着色的数 $k$ 的最小值称为 $G$ 的边色数，记为 $x ^{\prime}( G )$ 。若 $x^{\prime}(G)=k$ ，则称 $G$ 是 $k$ 边色的。

因为任何一个正常边着色中，每一个顶点关联的边着色不同，所以 $x^{\prime}(G) \geqslant \Delta(G)$ 。若顶点 $v$ 关联的某边上着色 $i$ ，则称 $v$ 点出现颜色 $i$ 。

维津（Vizing）于 1964 年给出了一个重要的定理，指出一个简单图的边色数或者是 $\Delta(G)$ ，或者是 $\Delta(G)+1$ 。定理如下。

定理 9.12 设 $G$ 是一个简单图，它的顶点最大度数是 $\Delta(G)$ ，则 $x^{\prime}(G)=\Delta(G)$ 或者 $x^{\prime}(G)=$ $\Delta(G)+1$ 。

证明从略。
定理 9.12 给出了 $x^{\prime}(G)$ 的上界和下界，即 $\Delta(G) \leqslant x^{\prime}(G) \leqslant \Delta(G)+1$ ，但是图 $G$ 有 $x^{\prime}(G)=\Delta(G)$ （或 $\Delta(G)+1$ ）的充分必要条件是什么？这个问题至今尚未解决。仅知道某些特殊的图 $G$ 有 $x^{\prime}$ $(G)=\Delta(G)$ 或者 $x^{\prime}(G)=\Delta(G)+1$ ，例如 $n$ 个顶点构成的回路 $C_n, ~ \Delta(G)=2$ ；当 $n$ 为偶数时，$x^{\prime}(G)=2$ ；当 $n$ 为奇数时，$x^{\prime}(G)=3$ 。对于二分图 $G, x^{\prime}(G)=\Delta(G)$ 。

定理 9.13 如果 $G$ 是二分图，则 $x^{\prime}(G)=\Delta(G)$ 。
证明：证明方法类似于定理 9．10，对边数进行数学归纳。
边数为 1 的二分图 $G$ 中 $\Delta(G)=1$ ，显然 $x^{\prime}(G)=\Delta(G)=1$ 。
假设对任何 $e-1$ 条边的二分图，命题成立。对于 $e$ 条边的二分图 $G$ ，从 $G$ 中删去任一边 $\{u, v\}$ ，得 $G^{\prime}$ 。根据归纳假设 $G^{\prime}$ 的顶点的最大度数是 $\Delta\left(G^{\prime}\right), \Delta\left(G^{\prime}\right) \leqslant \Delta(G)$ ，那么 $G^{\prime}$ 是 $\Delta\left(G^{\prime}\right)$－边可着色，显然也是 $\Delta(G)$－边可着色，并且在 $u$ 点和 $v$ 点的度数小于 $\Delta(G)$ ，在 $u$ 点至少缺少一种颜色，在 $v$ 点也缺少一种颜色。将边 $\{u, v\}$ 加回得图 $G$ ，这时 $G$ 中边 $\{u, v\}$ 尚未着色。如果 $u$点和 $v$ 点缺少的颜色相同，边 $\{u, v\}$ 着上这种颜色；如果 $u$ 点和 $v$ 点缺少的颜色不同，设 $u$ 点缺少色 $1, v$ 点缺少色 2 ，则可以作一个连通子图 $H$ ，它由 $v$ 点出发的色 1 和色 2 交替边构成的路。因为 $G$ 是二分图，并且子图 $H$ 不包含 $u$ ，所以可在 $H$ 上对换色 1 和色 2 ，这样并不影

响 $u$ 点已经着上的颜色。于是边 $\{u, v\}$ 着上色 1 。因此图 $G$ 是 $\Delta(G)$－边可着色的，并且 $x^{\prime}$ $(G)=\Delta(G)$ 。

例 9.2 （课程表问题）某学校有 $m$ 位教师 $x_1, x_2, \cdots, x_m$ 和 $n$ 个班级 $y_1, y_2, \cdots, y_n$ ，要求教师 $x_i$ 每周给班级 $y_j$ 上课，问如何安排一张周课程表，使所排课时数目尽可能地少？

解：建立一个图论模型表示这一问题：作二分图 $G\left(V_1, V_2\right), V_1=\left\{x_1, x_2, \cdots, x_m\right\}, V_2=\left\{y_1, y_2, \cdots\right.$ ， $\left.y_n\right\}, x_i$ 与 $y_j$ 有边相连当且仅当教师 $x_i$ 给班级 $y_j$ 上了一个课时的课。
利用边的着色理论来解决这一问题。在任何一个课时，一个教师最多只能给一个班级上课，并且每个班级最多只能由一位教师上课。于是课程表问题对应为二分图 $G$ 用尽可能少的颜色对边着色，并使相邻边的颜色都不相同。根据定理 9．13，如果 $G$ 的顶点最大度数是 $\Delta(G)$ ，则 $\chi^{\prime}(G)=\Delta(G)$ 。因此，如果每位教师至多上 $\Delta(G)$ 个课时，并且每个班级至多有 $\Delta(G)$ 个课时，则一定可以安排一张 $\Delta(G)$ 个课时的课程表。在二分图 $G$ 中，同一颜色的边对应于同一课时中教师安排班级上课的情况。

对于完全图的边色数，有下面的定理。
定理 9.14 设 $K_n$ 是完全图，当 $n$ 为奇数并且 $n \neq 1$ 时，$\chi^{\prime}\left(K_n\right)=n$ ，当 $n$ 为偶数时，$\chi^{\prime}\left(K_n\right)=n-1$ 。证明留作习题。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：五色定理

下一篇：没有了

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