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

Algorithm for adjacent vertex distinguishing VI-equitable total coloring of random graphs

作　　者：江红豆 李敬文[1] 曹道通 江世明[1] JIANG Hongdou;LI Jingwen;CAO Daotong;JIANG Shiming(School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《计算机工程与应用》2017年第15期41-46,67,共7页Computer Engineering and Applications

基　　金：国家自然科学基金(No.11461038;No.61163037;No.61163010)

摘　　要：邻点可区别VI-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类(点或边)的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别VI-均匀全色数。提出了一种针对随机图的邻点可区别VI-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别VI-均匀全色数。The adjacent vertex-distinguishing VI-equitable total coloring of graph G is that adjacent edges of a graph havedifferent color,the sizes of its color classes(vertex or edge)differ by at most one,and no two adjacent distinct verticeshave the same color sets,the minimum number of used colors is called the adjacent vertex distinguishing VI-equitabletotal chromatic number.In this paper,a heuristic algorithm is presented for the adjacent vertex distinguishing VI-equitabletotal coloring of random graphs,which has designed three objective functions and one main function by the constraints,with exchange rules to find the optimum solution,the iterative exchange hasn’t finished until the coloring results satisfythe requirements of main function.At the same time,this paper gives the detailed algorithm steps and the conductedmassive testing and analysis.The experimental results show that this algorithm can find the minimum adjacent vertexdistinguishing VI-equitable total chromatic number which the vertices have given efficiently.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]