基于图论的高校排课问题.doc

图论及其应用
期末论文

姓名： 董明明
学号： 2012111414

基于图论的高校排课问题

如今高校的教务部门，每年都要面对这样一个问题：排课。排课问题是典型的涉及到多类资源的组合与优化的问题。有限的教师、有限的教学场地及特定的教学时间资源，这三者相互制衡相互关联，为达到最佳教学目标，因此要进行综合有效的规划。其实质就是为学校所设置的课程安排一组适当的教学时间与空间，从而使一个学年的整个教学活动能够有计划有秩序地进行。
在排课问题中，其基本任务是：将教师、班级、课程时间，以一个周期的方式进行合理的匹配，使其在时间和空间上不发生冲突。在高校教务部门的实际排课过程中，还要考虑到老师对于授课时间的要求，以及学生对于授课的要求等等。为便于问题的分析，在此先不考虑教师对排课的要求和学生对排课的要求，仅先讨论如何在时间和空间不冲突的情况下，把教师、班级、课程时间合理的安排好。
为了便于用图论的方法分析排课问题，我们把教师，班级，课程进行抽象，其中，把教师和班级分别抽象为一个偶图的两个独立集，课程抽象为此偶图的边。排课问题在时间上的安排实际上就是安排每一个教师在具体的时间段到某个具体的班级去上课。这个安排要求满足下面的条件：同一时间每位教师只能到一个班级去上课；一个班级在同一个时间也只能由一位教师来上课。用图论的知识可以来表示这个问题。例如：有n位教师，有m个班，教师Xi要给班级Yj上课就将Xi与Yj相连形成一条边，如果一周内教师Xi要给班级Yj上2次课，则连两条边，以此类推。其中Xi为表示教师的独立集X中的点，Yj为表示班级的独立集Y中的点，i在1到n中任取，j在1到m中任取。于是，我们创建一个偶图G=(X，Y，E)，其中X=()代表n个教师，Y=()代表m个班级。
因为在同一时间每位教师只能到一个班级去上课，而一个班级也只能由一位教师来上课，所以排课问题，就被抽象为了一个偶图G的边着色问题：对每一条边进行着色，一种颜色代表一个授课的时间段，同种颜色的边代表同一个时间段。
根据图论的边着色理论，k边着色是指k种颜色1,2,…,k对于图中各边的一种分配方案，着色时若没有相邻的两条边颜色相同，则称着色是正常的。如果图G可以用k种颜色实现正常边着色，就说明，从每一个顶点发出的相邻边颜色不同。因此，我们把一种颜色对应一个课时，也就是把偶图G的k边着色方案对应成k个课时的分配方案，为每一次授课分配时间段的过程就是边着色过程，这样可以既保证在一张有课时的课表内，某个教师所代的各班的课不在同一个课时，同时也可以保证每个班级所上的不同教师的课也不在同一个课时。那么，在假定教室足够多的情况下，就可以保证教师、班级和课程等要素不会发生冲突。