图论在高校排课中的应用

摘要：图论是应用数学的一个重要分支,图论可以为二元关系系统提供一个数学模型。排课系统是各高校教务系统的重要部分。按照教学要求运用图论知识构造出排课模型, 然后用图论的边着色原理进行课时分配，利用图论中的相关定理 ,再根据图论的对集理论,对排课模型图中的各个适用边赋权值, 然后选出权值最大的加权图即为最优的排课方案。既减少了各种冲突的可能性, 并且大大提高排课的效率。31180
毕业论文关键词：图论；边着色；对集；赋权
The application of graph theory in university course arrangement
Abstract: Graph theory is an important branch of applied mathematics; it can provide binary relation system with a mathematical model. Universities and colleges in curriculum arrangement system is an important part of educational administration system. In accordance with the requirements for the teaching process constructs the model of utilizing the knowledge of graph theory, and then use the edge coloring principle of graph theory to carry on the class hour, using the related theorem in the graph theory, according to graph theory of set theory, in the process of model diagram, the weighting of each applicable side and choose a weight weighted graph is the largest, the optimal arrangement scheme.Both to reduce the likelihood of conflicts, and greatly improve the efficiency of the process.Both to reduce the likelihood of conflicts, and greatly improve the efficiency of the process.
Key words: Graph theory; Edge coloring; Couple aggregation; Empowerment
目录
摘要 1
引言 2
1.预备知识 4
1.1应用原理 4
1.2常用算法介绍 5
2.问题分析 6
3.图论模型 7
3.1模型建立7
3.2利用图论中边着色理论设计排课模型7
3.3模型的调课问题 11
3.4权值函数的计算 13
3.5排课系统的设计 15
4.图论在高校排课系统中的应用提示 15参考文献 16致谢 17
图论在高校排课中的应用
引言
排课系统是为了实现学校教学资源的合理综合利用，解决资源的组合优化和冲突。特别是在我国高等教育飞速发展的今天，排课系统更有很大的使用价值。排课系统的核心是排课，排课问题的实质是课表问题。1963年Gotlieb对课程表问题做了形式化描述，提出了排课问题的数学模型。1975年美国人S.EVEN等论证了课表问题是NP-complete问题。这说明NP完全问题是一般是可以求出最优解的，但在实际操作过程中我们发现，随着计算量的增多我们不肯能完全得到最优解，或者说是近似解。因此许多学者对此进行了一系列的研究分析和讨论，并取得不少成就，诸如遗传算法，贪心算法，动态规划，图论算法等。20世纪中期国外开始研究课表问题。但是这些理论却只能在理论上做出一定的讨论，无法实际运行或实验来搜集足够的数据去证明。目前大多算法是模仿手工排课的做法和经验，通过计算机的反复对比来避免冲突的发生，排课的过程是直接按照排课的习惯时间和教室的分配，遇到了冲突再设法调整，而每次的调整都有可能照成新的冲突，不能保证最优解的收敛速度，因此效率很低且不能保证最终方案较优。近段时间也出现过利用人工智能如遗传算法，模拟手工排课法、图论方法、遗传算法、模拟退火算法、专家系统方法、回溯算法、优先级算法等方法对排课问题在理论上作近似优化讨论, 但其实验数据较少,其搜索算法或推理过程对于这样已被证明为NP难的问题, 无法从数学角度给出这些方案是否为有效性的证明。特别来说, 有些算法如遗传算法,还可能逐渐偏离全局最优解和不稳定性。
我国国内对课表的研究起源于上世纪80年代我国也有许多学者做出了相应的研究和分析。目前我国各大高校普遍采用计算机进行自动排课，不但是教务人员从繁忙的工作中解脱出来还提高教务管理的工作效率，同时优化了教学资源合理利用，是学校的各项教学工作高效有序的进行。图论在高校排课中的应用:http://www.751com.cn/shuxue/lunwen_27245.html