摘要：

为解决图的Smarandachely邻点可区别边染色问题,提出一种基于多目标优化的染色算法。针对每个子问题分别设置子目标函数向量和决策空间,在颜色迭代、顺序交换和强制交换中,子目标逐渐得到最优解,最终使总目标函数符合图的Smarandachely邻点可区别边染色要求。实验结果表明,在1 000个顶点内该算法能够正确地得到随机图的Smarandachely邻点可区别边色数。

关键词: 多目标优化, 图染色, Smarandachely邻点可区别边染色, 目标函数, 时间复杂度

Abstract: To solve the problem of Smarandachely Adjacent Vertex Distinguishing Edge Coloring(SAVDEC) of graphs,this paper presents a coloring algorithm based on multi-objective optimization.For each sub problem,the sub objective function vector and decision space are set respectively.The optimal solution for sub objectives is gradually obtained during color iteration,sequential switching,and forced switching,making the total objective function meet the requirements of Smarandachely adjacent vertex distinguishing edge coloring ultimately.Experimental results show that,the proposed algorithm is able to get the number of colors for the Smarandachely adjacent vertex distinguishing edge of random graph within 1 000 vertices correctly.

Key words: multi-objective optimization, graph coloring, Smarandachely Adjacent Vertex Distinguishing Edge Coloring(SAVDEC), objective function, time complexity

中图分类号: 

• TP301.6