需要金币: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 |