9.3 边染色.ppt

以上考虑的问题中有几个教室可供使用 是没有限制的。假定可供上课的教室数给 定，那要安排一张完善的课表需多少课时 呢？ * §9.3 边染色 返回 结束 注：图 的一个 边染色实际等价于图 的边集合 划分为 个边不交的对集。 定义9.3.1 无环图 的一个 边正常染色是指 种颜色 对于 的各边的一个分配，使得相邻的两条边 染以不同的颜色。 若 有 边正常染色，则称 是 边可染色的。 的边色数是指 为 边可染色的最小值 ， 记为 若 ，则称 是 边色的。 返回 结束 证明：分以下几步 定理 9.3.1 二分图 的边色数 。 2。 含有完美对集 ，使得 1。构造 正则二部图 ，使得 。 返回 结束 定理 9.3.2 若 是简单图，则 证明： 只需要证明 。 3。取 ，于是 假设 已经有一个 边正常染色，以下通过对边 的染色调整，最后得到整个图 的 边正常染色。 对 进行归纳。 1。当 时，结论成立。 2。假设结论对于任何具有 条边的简单图成立。 定义 9.3.2 若图 满足 ，则称 为第一类图； 若 满足 ，则称 为第二类图。 由定理 9.3.1可知，二分图是第一类图。 返回 结束 证明： 假设 ，现给 的一个 边正常染色， 由边染色与对集之间的关系可知， 中染以同一种颜色的边 数最多为 ，则 这与给定的条件矛盾。 返回 结束 推论 9.3.3 是 阶图，如果 ，则 为第二类图。 用边染色理论来讨论排课表问题。 排课表问题：在一所学校有 位教师 和 个 班级 。在明确教师 需要给班级 上 节课 后，要求制定一张课时尽可能少的完善的课表。 1。先构造一个二分图 。 2。排课表问题就是把 划分为若干个对集，且使对集个数尽可能少。即，给 的边用尽可能少的颜色去正常染色。 3。由 是二分图得， 。 4。利用定理 9.3.1 的证明过程，可作出相应二分图的 个边不相交的对集。 返回 结束 *