随机图的邻点可区别Ⅵ-均匀全染色算法

摘要：

邻点可区别VI-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类(点或边)的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别VI-均匀全色数.提出了一种针对随机图的邻点可区别VI-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求.同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别VI-均匀全色数.

关键词：随机图、正常均匀全染色、均匀全色数、邻点可区别VI-均匀全染色

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金11461038,61163037,61163010

在线出版日期：2017-08-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：41-46,67