- 上一篇：整函数的阶型与零点+文献综述
- 下一篇：线性回归中最小二乘估计的改进
很明显，在任何正常边色数中，和任一顶点关联的各边必须分配以不同的颜色。由此推之，
参照图1的例子，可知在(2.1)式子中允许出现严格的不等式。而在 是偶图的情况下，等式成立（定理2）[1]
偶图，即二部图，指若图 的顶点集可划分为两个非空子集 和 ，使得任一条边都有一个端点在 中，另一个端点在 中，则称 为二部图（或偶图），记为
下面我们运用边染色的概念以及其基本定理对排课表问题进行求解。
2.2 排课表问题的介绍
2.2.1 排课表问题的背景介绍
在一所学校里，有 位教师 ，…， 和 个班级 ，…， 。已知教师 给班级 上 课时， = 称为教学要求矩阵。假定只有 个教室可供利用。要求制订一张完善的课表 ,使得需要的课时数尽可能少(用 表示其中最小者) , 同时在一节课时内最多占用的教室数量也尽可能少(用 表示其中最小者) 。这样的课表称为最优课表。
上述问题，通常称之为排课表问题[6]。
排课表的基本要求是避免冲突，防止教学事故，但由于没有好的算法，在手工排课时，需要付出很多的劳动，即便如此，也不能从理论上保证不会冲突。因此，随着教学资源、师资力量和招生规模的变化，每次需要多大的工作量、多长时间能排出来以及能不能正常安排教学过程都难以定论。在排课表时，需要考虑的约束和资源限制太多，有时即使排出的课表能够使用，也不能保证方案是效果最好的。
冲突限制主要表现在同一时段既不能一个老师给两个班上课（合班除外），也不能有两个老师给同一个班级上课；合班课不能跟小班课冲突，即某个班的小班课不能跟它与其他班的合班课排在同一时段内。资源约束是指实验室和合班教室一般都属紧缺资源，排课时应该针对每个时间段平均分配使用的班级。除冲突限制以及资源的约束外，排课时还应该考虑相邻两次课不能排的太近，排在一天或相邻的两天都不能符合要求。比如每周4个学时的课程，排在星期一、三或星期二、四或星期三、五都是可以的，每周6个学时的课，排在星期一、三、五则是比较理想的。为满足这方面的要求，需要在模型中设计效果优化算法。
排课模型中的关键是避免排课冲突的排课算法。目前大多数算法是模仿手工排课的做法和经验，通过计算机反复对比来避免冲突的发生，排课的过程是直接按照排课的习惯进行时间和教室的分配，遇到了冲突再设法调整，而每次的调整都可能造成新的冲突，不能保证最优解收敛的速度。因此效率低下。另外这种方法不能保证最终方案最优。
解决排课表问题，可以运用图论中的边染色。将教师 与班级 之间的授课关系转化成二部图的边染色[7]，如下图2所示每一个对应的授课用一条边来表示， 要给 班级上 节课，那么 与 之间用 条线连接，然后用正常的边染色。使用同一种颜色的边代表可以在同一课时进行。从而安排出一个课表计划。
图2
边染色理论可以从根本上避免手工排课的不确定性，它可以在保证不冲突的前提下，分配授课时段，也可以对方案进行优化。我们用常用模型对高校排课问题进行简化和边染色计算。
2.2.2 排课表问题是一个NP完全问题
设有 位教师和 个班级和 个教室，其中教师 要给班级 上 节课。应如何在最少节次 内排完所有的课。这问题可转化为：给定一偶图 其中 ={ , ,…, }, ={ , ,…, }, ={ } 与 间有 条边，应如何将边集 划分成互不相交的 个匹配（ ,…, ），且使 为最小?由边染色问题知，只要求出偶图 的 = =∆-边着色即可。