图的染色问题在排课表中的应用+文献综述(2)
课表安排是一项十分繁重而复杂的工作，它涉及几十甚至上百个专业、几百门课程、几百名教师的合理安排。然而教室、实验室等资源又有限，更给排课增加了难度。在整个排课过程中，自始至终充满了冲突，其中包括上课班级、所开课程、任课教师、上课时间、上课地点等5个方面在排列组合中所发生的冲突与矛盾。班级多、课程门类多、教师少、教室少是发生冲突和矛盾的重要因素。为了减轻劳动强度，提高工作效率，我们考虑用图论中的染色来解决排课问题。
1.2国内外研究现状与发展趋势
1.3基本符号
——表示图 的最大度
——表示完全图
——表示二部图
——表示完全二部图
——表示图 中顶点 的度
1.4基本概念
设 是一个图，我们用 ， ， 和 （或者用简单的 ， ， 和 ）分别表示图 的顶点集合，边集合，最大度和最小度。
顶点的度：在图 中与顶点 相关联的边数（每个环计算二次），称为顶点 的度,记为 。
图 的最大度： ，记为 。
简单图：如果一个图 没有环和多重边，那么称 为简单图。
完全图：每对顶点之间都恰有一条边的简单图。
二部图：若图 的顶点集可划分为两个非空子集 和 ，使得任一条边都有一个端点在 中，另一个端点在 中，则称 为二部图（或偶图），记为 。
边染色：无环图 的一个 边正常染色是指 种颜色1,2,… ，对于 的各边的一个分配，使得相邻的两条边染以不同的颜色。若 有 边正常染色，则称 是 边可染色的。
边色数： 为 边可染色的最小值 ，记为 ，若 ,则称 是 边色的。因此图 的一个 边染色实际等价于图 的边集合 划分为 个边不交的对集。
关联矩阵：设 的顶点集和边集分别为 , 用 表示顶点 与边 关联的次数（0,1或2），称矩阵 为 的关联矩阵。
邻接矩阵：设图 的顶点集为 ,用 表示 中 与 之间的边数。称矩阵 为 的邻接矩阵。
1.5相关定理
定理1[1]：若 是二分图， 。则存在 个互不相交的对集 ，使得 并且对每个
定理2[2]：设 是二部图，则 。
定理3[3~4]（Vizing定理）：对于简单图 ，有 ，其中 为 的最大度点。
引理4：设与 是图 的两个不相交匹配，且| |>| |,则存在图 #的不相交匹配 与 ，使| |=| |-1，| |=| |+1， =
定理5：设 是二部图， ,则存在 的 不相交匹配 ,…,
并且对于 有
Koning定理：在0-1矩阵中，1的最大独立集合最小覆盖包含的元素个数相同，等价地，二分图中的最大匹配数等于这个图中的最小点覆盖数。
二、边染色在排课表中的应用
用染色解决排课表问题，传统的解法是运用边染色对该问题进行求解。在解决排课表问题前，我们先简单的介绍一下边染色以及其经常求解的简单现实模型，并从中体会边染色的运用，使其运用到排课表问题中去。
2.1 边染色的介绍
无环图G的一个 着色是指 种颜色1,2，…, 对于G的各边的一个分配。若没有相邻的两条边有着相同的颜色，则称着色是正常的[5]。
换句话说，一个 边着色可以看做是 的一个分类（ ）,这里 （可能是空的）表示染有颜色 的 的子集，一个正常的 边着色就是每个 均为对集的 边着色（ ）。图1中的图有正常的4边着色
若 有正常的 边着色，则称 是 边可着色的。显然，每个无环图 是 边可着色的；并且若 是 边着色的，则对每个l> ， 亦是l边可着色的。无环图 的边色数 ，则称 是 边色的。可以验证，图1没有正常的3边着色，因此该图是4边色的。
上一篇：整函数的阶型与零点+文献综述
下一篇：线性回归中最小二乘估计的改进