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

来源：计算机工程与应用杂志2017年第15期北京时间：

作者：江红豆，李敬文，曹道通，江世明

单位：兰州交通大学 电子与信息工程学院，兰州 730070

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

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