用图的匹配求解排课的教室安排问题.pdf

南昌高专学报 年第 期（总第 期） 年 月出版 2010 5 90 2010 10 157 Journal of Nanchang College No.5(Sum 90) Oct.2010 用图的匹配求解排课的教室安排问题 蒋 政 （无锡科技职业学院基础部， 江苏 无锡 214028 ） 摘 要：在某一个时间段安排某个班级在某个教室上课有多种选择，但上课班级与教室之间最终应是一个 一一对应的关系。 用图的匹配可以解决如何在多对多的可能对应中确定一一对应的问题。 关键词：图；匹配；教室安排 中图分类号： ； 文献标识码： 文章编号： （ ） O157.6 G473.4 A 1008－7354 2010 05－0 157－02 1 问题的提出 表 需安排教室的与个班主任情况 1 1.1 图的匹配 班级 x1 x2 x3 x4 x5 设 是一个图，边子集 使 中任意两条边 G=(V , E) M M 人数 45 42 45 85 42 都没有公共顶点，则称 为图 的匹配。 匹配中边的端 上课要求 多媒体授课 M G 点称为饱和点，否则称为非饱和点，饱和点也称为是被匹 同时有 个教室 可用， 这 个教室的配 5 y ,y ,y ,y ,y 5 1 2 3 4 5 配覆盖的顶点。 图中边数最多的匹配称为图的最大匹配。 置情况如表 ： 2 覆盖图的所有顶点的匹配称为图的完美匹配。 表2 5 个可用教室配置情况 1.2 排课教室的安排 教室 y1 y2 y3 y4 y5 在排课的过程当中， 其主要任务是将具有多种属性 容量 60 60 90 90 90 的各种资源，如教室、班级、教师、学生、课程、时间等，以 特殊配置 配有多媒体 配有多媒体 配有投影仪 一个周期的方式进行合理的匹配，使其不发生冲突。 事实 根据上课班级与教室的情况分析， 满足以上所说的 上，在排课问题中，每节课可抽象为教师和学生在时间和 两个条件的教室都是可用的， 将每个班级与其可用的教 空间上的统一， 教室的安排实际上就是要求主体即教师 室用边相连，得到图 ：