多目标优化的图的邻点可区别均匀V-全染色算法

Adjacent vertex-distinguishing equitable V-total coloring algorithm of graph based on multi-objective optimization

图的邻点可区别均匀V-全染色(AVDEVTC)是指在满足邻点可区别V-全染色的基础上,还要保证每种颜色的使用次数相差不超过1,把完成AVDEVTC所用的最少颜色称为图的邻点可区别均匀V-全色数(AVDEVTCN)。针对图的AVDEVTC问题,提出了一种基于多目标优化的染色算法。设计了一个总目标函数和四个子目标函数,在染色矩阵上通过每个点的颜色集合的迭代交换操作,使得每个子目标函数都达到最优,进而满足总目标函数的要求,完成染色。经过理论分析和实验对比表明,8个顶点以内的所有简单连通图都存在AVDEVTC,且图的AVDEVTCN介于最大度加1与最大度加2之间。实验结果表明,该染色算法能够在较短的时间内正确地计算出1 000个顶点以内的图的AVDEVTCN。

Adjacent Vertex-Distinguishing Equitable V-Total Coloring （AVDEVTC） of a graph means on the basis of adjacent vertex-distinguishing V-total coloring, the differences between every two colors used in coloring are no more than one. The minimum number of colors used for completing AVDEVTC is called Adjacent Vertex-Distinguishing Equitable V-Total Chromatic Number （AVDEVTCN）. A multi-objective optimization coloring algorithm was proposed to resolve the problem of AVDEVTC of the graph. A main objective function and four subobjective functions were designed according to the conditions of AVDEVTC. Every subobjective function was optimized to meet the requirements of the main objective function by the iterative exchange operation of the color set of every vertex on the coloring matrix, thus completed the coloring. Theoretical analysis and experimental comparison show that all of the simple connected graphs within eight vertices have the AVDEVTC, and their AVDEVTCN are between the maximum degree plus 1 and the maximum degree plus 2. The experimental result indicates that the proposed coloring algorithm can correctly calculate the AVDEVTCN of graphs within 1 000 vertices in a short period of time.