图论期末论文顶点着色.doc

附件1 论文编号 《图论》课程 专题论文 论文题目： 基于顶点着色理论的 期末考试时间安排问题 专 业：数学与应用数学 班 级：2012级数学与应用数学班 组 长：张正中 姓名 张正中 马晓晨 余铁方 李斌 唐毓春 杨昌天 马福贵 学号 P121713337 P121713347 P121713348 P121713357 P121713338 P121713354 P121713342 成绩 年 月 日 论文评价指标与鉴定意见 论文题目 基于点着色理论的期末考试时间安排问题 完成人 张正中、马晓晨、李斌、唐毓春、余铁方、杨昌天、马福贵 专业及班级 2012级数学与应用数学班 指标 论文评价 （对表格中的各栏，用“√”表示意见） 优 良 中 差 论文选题 基础理论与 专门知识 语言的表达水平 创新性 学术价值 应用价值 总体评价 A（86—100分） B（70—85分） C（60—69分） D（0—59分） 鉴定意见 评阅人签名： 成绩 评阅人 职 称 专 业 附件2 分工情况 论文题目 基于点着色理论的期末考试时间安排问题 专业年级 2012级数学与应用数学班 组长 张正中 电话QQ号 1098758179 完成人 分工情况 完成度（%） 张正中 摘要、论文整合 15 马晓晨 顶点着色在期末考试时间安排中的应用 15 李 斌 数据收集、整合 14 余铁方 顶点着色应用的实际意义 14 杨昌天 考试时间安排问题的发展现状 14 唐毓春 顶点着色理论及其算法的发展现状 14 马福贵 顶点着色理论及其算法的发展现状 14 摘要 随着Internet的发展和我国高校校园网的普及,采用计算机网络进行考试安排的需求非常迫切,而考试冲突问题又是考试安排的核心,使用顶点着色算法设计一个高效的考试安排系统,解决考试冲突问题,使考务工作适应信息化的需求,实现管理的科学化、自动化,最大程度为教师和同学们提供方便是本论文研究的重点 本文应用图论的原理将数学与计算机科学学院2014级考试安排问题转化为对图的顶点着色问题。提出用求图的极大独立集的方法求解图的点色数，并用布尔方法计算图的极大独立集, 有效的避免了相同班级的不同考试科目在同一时间进行考试的问题 关键词 顶点着色问题 考试安排 布尔算法 ABSTRACT With the development of Internet and the popularization of campus network in Colleges and universities in China. It is urgent to use computer network to carry out the test arrangement and the examination conflict problem is the core of the examination arrangement. Using vertex coloring algorithm to design an efficient examination arrangement system, solve the conflict problem of examination examination work, to meet the needs of informationization, the realization of scientific management and automation, the greatest degree for teachers and students to facilitate the research focus of this paper. In this paper, the principle of graph theory is applied to the problem of 2014 levels of the computer science college. It is proposed to solve the problem of the same class of different test subjects in the same time by using the maximal indepen