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

资料分类:精选论文 上传会员:18389978 更新时间:2014-09-25
需要金币1000 个金币 资料包括:完整论文 下载论文
转换比率:金额 X 10=金币数量, 例100元=1000金币 论文字数:10998
折扣与优惠:团购最低可5折优惠 - 了解详情 论文格式:Word格式(*.doc)

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

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

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

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

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

 

目录

摘要

Absract

一、绪论6

(一)课题的意义6

(二)研究现状6

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

三、基本概念8

(一)图与二分图8

(二)顶点的度10

(三)匹配10

(四)边着色11

(五)主要引理13

四、应用案例13

(一)案例一13

(二)案例二18

(三)案例三19

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

六、结论与展望23

参考文献24

相关论文资料:
最新评论
上传会员 18389978 对本文的描述:对于仅仅依靠排课软件或者手工排课的学校来说,这无疑是很大的难题。在手工排课时,不仅需要付出艰巨的脑力劳动,也并未从理论上保证避免冲突,因为需要考虑的约束和资源限制......
发表评论 (我们特别支持正能量传递,您的参与就是我们最好的动力)
注册会员后发表精彩评论奖励积分,积分可以换金币,用于下载需要金币的原创资料。
您的昵称: 验证码: