图论在高校排课问题中的应用研究  

Application of Graphic Theory to University Time-Tabling Problem

作　　者：王仲华[1] 卢娇丽[2] 

机构地区：[1]太原师范学院数学系,山西太原030012 [2]山西大学现代教育技术中心,山西太原030006

出　　处：《太原师范学院学报（自然科学版）》2010年第1期39-42,共4页Journal of Taiyuan Normal University:Natural Science Edition

摘　　要：在深入分析普通高校排课特点和难点的基础上,设计了一种基于图论的排课方法.文章首先根据教学要求构造出排课模型图,然后用图论的边着色理论对课时进行分配.针对教室不够用的情况,根据图论中的相关定理,对排课模型进行了初步优化.之后根据图论的完美对集理论,并结合教学效果对排课模型图中的一些边赋了权值,然后选出权值最大的加权图作为最优的排课方案.通过对高校的实际排课数据进行测试,表明该模型可行且能够有效地提高排课效率.The features and technique difficulties of university time-tabling problem were analyzed,and then a method for time-tabling problem based on graphic theory is proposed. First, a graph is constructed in accordance with requirements of teaching model of time-tabling problem, then the distribution of the class is finished based on edge coloring theory. As for using in the classroom,the article arranged schedule a preliminary optimization on the basis of the relevant graphic theory. Then based on perfect theory and combined teaching effect, there weighted for some edges of the time-tabling model graph, and selected the weighted graph with the largest weight as the most optimal time-tabling programme. Through the actual data for testing,showed that the model is feasible and can effectively improve the efficiency of time-tabling problem.

关 键 词：排课 图论 边着色 加权图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]