图染色问题应用研究

发布时间：2017-04-12 06:04

  本文关键词：图染色问题应用研究，，由笔耕文化传播整理发布。

【摘要】：染色问题是图论研究中一个重要的研究范畴,也是近年来迅速崛起而又应用较为广泛的新学科。图染色问题的研究方法和重要理论在离散数学研究中具有十分重要的地位,也是推动图论和离散数学研究和发展的核心,具有重要的理论价值。同时,染色问题的不断研究成果在很大程度上也影响了我们的实际生活,比如基于图染色问题,它可以帮助我们解决通讯系统的频率分配、化学品储藏、任务调度、学校排课、考试安排等各种问题,具有很大的现实意义和社会意义。本文概述了图染色基础理论,介绍了图的概念、图的分类和图的点染色、边染色和全染色问题,讨论研究了贪心染色算法、Welsh-powell染色算法、基于集合论的点染色算法、传统的直接启发式算法、利用极大独立集的点染色算法、基于二部图的边染色算法、基于点染色的无向图边染色算法,分析了这些算法的优缺点。利用图染色算法,给出了学校排课考试中的一种应用模型,可以帮助解决在排课考试中,教师、班级、学生、教室之间的时间冲突问题,提高了工作效率。利用点染色算法,给出了在农作物栽培技术上的一种应用模型,可解决农作物之间相克现象,提高了农作物的存活率和效益。
【关键词】：边染色 点染色 排课考试 农作物栽培技术
【学位授予单位】：江西师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-7
• 第一章 绪论7-11
• 1.1 研究背景及意义7-8
• 1.2 图染色问题的研究现状8-10
• 1.3 本文的研究内容及组织结构10-11
• 第二章 图染色理论基础11-18
• 2.1 图的基础知识11-13
• 2.1.1 图的二元组定义11
• 2.1.2 关于图的基本概念11-12
• 2.1.3 图的分类12-13
• 2.2 图论染色问题的引入13-14
• 2.3 图的染色14-18
• 2.3.1 图的顶点染色14
• 2.3.2 图的边染色14-15
• 2.3.3 图的全染色15-18
• 第三章 图染色算法18-32
• 3.1 贪心染色算法18-20
• 3.1.1 算法的设计思想18
• 3.1.2 顶点染色贪心算法18-20
• 3.1.3 顶点染色贪心算法的优点和缺点20
• 3.2 Welsh-powell染色算法20-21
• 3.3 基于集合论的点染色算法[26]21-23
• 3.3.1 算法的设计思想21-22
• 3.3.2 算法实例分析22-23
• 3.4 传统的直接启发式算法23-25
• 3.5 利用极大独立集的顶点染色方法25-29
• 3.6 基于点染色的无向图边染色算法29-30
• 3.7 基于二部图的边染色算法30-32
• 3.7.1 算法的设计思想及步骤30
• 3.7.2 算法简单实例30-32
• 第四章 图染色算法在学校排课考试中的应用32-38
• 4.1 学校排课问题32-33
• 4.2 学校排课算法及实例33-35
• 4.3 学校考试安排问题35
• 4.4 学校考试安排算法及实例35-38
• 第五章 点染色算法在农作物栽培技术上的应用38-41
• 5.1 农作物栽培技术38
• 5.2 农作物栽培技术的困难38-39
• 5.3 点染色在农作物栽培技术上一种应用模型39
• 5.4 农作物栽培技术应用实例39-40
• 5.5 结果分析40-41
• 第六章 总结与展望41-43
• 6.1 总结41
• 6.2 展望41-43
• 参考文献43-46
• 致谢46

【相似文献】

中国期刊全文数据库 前10条

1 赵小强;;高考中一类染色问题的推广与应用[J];数学爱好者(高考版);2008年12期

2 刘西峰;;两次捆绑快速解决有关染色问题[J];中学教学参考;2009年26期

3 郭建华;;染色问题解题策略例说[J];青苹果;2009年06期

4 卢建立;任凤霞;;3×n方格染色问题的两个新结果[J];数学通报;2011年12期

5 麦安婵;两类图的全染色问题[J];榆林高等专科学校学报;2002年04期

6 刘蓉;;排列组合中的染色问题[J];科技信息;2011年10期

7 卢建立;任凤霞;马美琳;;项链的若干染色问题[J];科技导报;2012年07期

8 卢家华;吴康;;3×n方格染色问题的再研究[J];数学通报;2014年01期

9 林育青;关于图的染色问题[J];广西大学学报(自然科学版);2000年01期

10 王绍文;;图的染色问题综述[J];北京机械工业学院学报;1995年02期

中国博士学位论文全文数据库 前7条

1 蔡华;平面图的若干染色问题[D];山东大学;2016年

2 李善海;设计的染色及其相关问题的研究[D];上海交通大学;2006年

3 陈敏;运用权转移方法研究图的若干染色问题[D];苏州大学;2011年

4 侯建锋;图上有限制条件的几类染色问题的研究[D];山东大学;2009年

5 胡小兰;极值和染色问题的一些新结果[D];南京大学;2015年

6 董爱君;图的几类染色问题[D];山东大学;2012年

7 梁作松;图的团横贯与团染色[D];上海大学;2013年

中国硕士学位论文全文数据库 前10条

1 庄禧超;特殊1-平面图的列表全染色[D];山东大学;2015年

2 贾西贝;图的若干不完备可区别染色算法研究[D];兰州交通大学;2015年

3 吕春琼;稀疏图的非正常染色问题的研究[D];福州大学;2014年

4 宋立莉;某些特殊图的点染色问题研究[D];山东师范大学;2016年

5 梁政;图染色问题应用研究[D];江西师范大学;2016年

6 朱俊俏;关于图的点可区别染色问题[D];浙江师范大学;2009年

7 王瑞琦;图边单射染色问题的复杂性及算法研究[D];南京师范大学;2014年

8 朱恩强;若干图类的新染色问题[D];兰州交通大学;2010年

9 王辉;满足某些特殊条件的平面图边染色问题研究[D];山东大学;2010年

10 尹琳娟;图论染色问题应用研究[D];西安电子科技大学;2009年

  本文关键词：图染色问题应用研究，由笔耕文化传播整理发布。

本文编号：300839