动态图染色问题研究

论文摘要

图染色问题是图论中的一个经典问题,且应用广泛,具有极高的研究价值,近年来一直是学术界的热点问题之一。图染色是指对一个连通的无向图的每个顶点指定一个颜色,使得在没有两个邻接顶点颜色相同的前提下,使用最少颜色数进行顶点染色的问题。图染色问题的应用包括生物化学中的核酸序列设计、空中交通管理、无线网络中的频道分配、社交网络中的团体检测等。一方面,由于真实世界的图经常会发生变化,当图频繁变动时,无法使用已有的静态染色方法进行有效的染色。另一方面,使用已有支持动态图的染色方法进行染色,染色效率较差。本论文研究当图动态更新时,如何高效率进行顶点染色,具体研究内容如下。首先,针对现有方法逐个处理被更新边所导致的效率低下问题,本文提出批量处理更新的高效染色方法。该方法不再关心一段时间内图更新的中间状态,而是针对一段时间图更新的状态,一次性处理该段时间累积的更新。同时,提出了高效的顶点剪枝策略来加速计算。和已有算法相比,在保证染色质量的前提下,提高了染色效率。其次,已有方法在进行染色时,需要构建和原始数据图相同规模的索引来维护顶点处理的顺序。针对已有方法索引占用空间较大的问题,提出无需维护额外索引的顶点剪枝策略。该方法针对所有更新边,根据顶点的度来动态维护顶点的处理顺序。在不影响处理效率的前提下,降低了所需的内存空间。最后,本文基于多种真实数据集进行实验,实验结果从染色质量、染色效率、内存消耗等多个方面进行比较,验证本文算法的有效性。

论文目录

文章来源

类型: 硕士论文

作者: 郝元宵

导师: 周军锋,徐凤东

关键词: 图染色,动态图染色,贪心算法,有向无环图

来源: 燕山大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 燕山大学

分类号: O157.5

DOI: 10.27440/d.cnki.gysdu.2019.001522

总页数: 59

文件大小: 1908K

下载量: 17

相关论文文献

• [1].3×n方格染色问题的两个新结果[J]. 数学通报 2011(12)
• [2].一道高考染色问题的创新解法及推广[J]. 中学数学研究 2019(04)
• [3].染色问题的相互转换探究[J]. 福建中学数学 2009(05)
• [4].关于2×n方格的染色问题研究[J]. 中学数学研究 2011(01)
• [5].从染色问题谈两个计数原理的教学[J]. 中学数学 2008(21)
• [6].一道染色问题的妙解[J]. 上海中学数学 2008(01)
• [7].对一类环形染色问题的探究[J]. 中学数学研究 2017(02)
• [8].“无心”和“有心”染色问题[J]. 数学学习与研究 2015(11)
• [9].例谈区域染色问题[J]. 数理化解题研究 2018(07)
• [10].染色问题解题探究[J]. 中学生数理化(学习研究) 2017(07)
• [11].染色问题[J]. 数学大世界(小学五六年级适用) 2013(04)
• [12].两次捆绑快速解决有关染色问题[J]. 中学教学参考 2009(26)
• [13].染色问题解题策略例说[J]. 青苹果 2009(06)
• [14].圆环染色问题的公式解法[J]. 中学生数学 2009(09)
• [15].快速学会对染色问题的彻底处理[J]. 中学生数理化(教与学) 2011(10)
• [16].一类环状染色问题的求解与变式应用[J]. 高中数学教与学 2018(17)
• [17].利用数列递推关系巧解染色问题[J]. 中学数学研究 2010(05)
• [18].计数中一类染色问题的探讨[J]. 中小学数学(高中版) 2015(06)
• [19].高考中一类染色问题的推广与应用[J]. 数学爱好者(高考版) 2008(12)
• [20].通过“染色问题”,培养中学生化归思维[J]. 阴山学刊(自然科学版) 2014(04)
• [21].项链的若干染色问题[J]. 科技导报 2012(07)
• [22].排列组合中的染色问题[J]. 青海教育 2008(04)
• [23].环形染色问题的公式解法[J]. 中学数学杂志 2008(09)
• [24].关于排列组合中染色问题的一种通用解法的研究[J]. 考试(高考数学版) 2012(09)
• [25].关于图的染色问题算法的新研究[J]. 山东轻工业学院学报(自然科学版) 2008(03)
• [26].突破染色问题[J]. 中学生数理化(高三) 2016(03)
• [27].正棱台柱图的染色问题[J]. 阴山学刊(自然科学) 2013(02)
• [28].项链染色问题探讨[J]. 新疆教育学院学报 2012(03)
• [29].排列组合中的染色问题[J]. 科技信息 2011(10)
• [30].染色问题的解法示例[J]. 中学生数理化(高考版) 2011(01)

标签：图染色论文;  动态图染色论文;  贪心算法论文;  有向无环图论文;