排课问题中图论知识的应用_应用数学专业.rar

摘要：作为数学分支之一的图论，一直以来以其简单基础为初学者所喜爱，并为我们解决科学问题提供了一条新的思维路径。图论以“图”为研究对象，在图论中对“图”的定义是这样的：由一些既定的点及连接两点的线所构成，这种图形通常用来描述某些事物之间的一种特定关系，我们用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。凡有二元关系的系统，均可以由图论提供出一种数学模型，进而转化为数学问题得以解决，所以图论在学术应用中能够为我们提供有价值的参考依据，应用面极其广阔，诸如化学、电路分析、生物学、物理、社会学、以及语言学，都是图论的应用领域。

　　　在实际生活中，许多排列分配、资源整合问题都涉及到将特定对象的集合按规则分类，比如公司执勤排班、大学排课、火车时刻表、信用管理等。其中，排课问题是各个大学必须解决的关键问题，也是本文研究解决的主要问题。

　　　排课问题是教务管理系统的核心问题，对于有效管理并且充分利用校园资源有着举足轻重的作用。排课问题是典型的多类资源组合优化问题，其主要任务即将具有多种属性的各种资源例如教师、教室、班级、学生、课程、时间等，以一个周期为循环进行合理的规划，使其各行其职且互不冲突，达到时间和空间上的统一，这亦是难办之处。幸运的是，图论中的图染色理论可以比较完美的解决此问题。所谓图染色理论，就是对图中的顶点、边等元素按一定的规则进行分类，对象不同或规则不同，则有各式各样的染色结果。图染色理论中的边着色理论可以巧妙地避免手工排课的不确定性，在保证不冲突的前提下，合理分配上课时段、对方案进行优化，从而使资源达到最佳的效用。

　　　本文从模拟情况出发，运用边着色理论对模拟数据进行了计算与排列，得到结果并与传统方法所得结果进行了一系列的比较，验证了图论在排课问题中应用的有效性。

关键词：排课 资源分配 课表优化 图论 边着色

目录

摘要

Absract

一、绪论6

（一）课题的意义6

（二）研究现状6

二、高校排课中的问题分析7

三、基本概念8

（一）图与二分图8

（二）顶点的度10

（三）匹配10

（四）边着色11

（五）主要引理13

四、应用案例13

（一）案例一13

（二）案例二18

（三）案例三19

五、排课表的效用评价及优化21

六、结论与展望23

参考文献24