计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

图的Smarandachely邻点可区别边染色算法

曹道通 a,李敬文 a,文飞 b   

  1. (兰州交通大学 a.电子与信息工程学院; b.应用数学研究所,兰州 730070)
  • 收稿日期:2016-07-15 出版日期:2017-09-15 发布日期:2017-09-15
  • 作者简介:曹道通(1990—),男,硕士研究生,主研方向为智能计算、组合优化;李敬文,教授;文飞,博士。
  • 基金项目:
    国家自然科学基金(11461038,61163037,61163010);兰州交通大学青年基金(2016014)。

Smarandachely Adjacent Vertex Distinguishing Edge Coloring Algorithm of Graphs

CAO Daotong a,LI Jingwen a,WEN Fei b   

  1. (a.School of Electronic and Information Engineering; b.Institute of Applied Mathematics,Lanzhou Jiaotong University,Lanzhou 730070,China)
  • Received:2016-07-15 Online:2017-09-15 Published:2017-09-15

摘要:

为解决图的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

中图分类号: