多目标优化的图的邻点可区别均匀V-全染色算法
来源：计算机应用杂志2017年第2期北京时间：
作者：曹道通, 李敬文, 江红豆, 文飞
单位：1. 兰州交通大学 电子与信息工程学院, 兰州 730070;2. 兰州交通大学 应用数学研究所, 兰州 730070
摘要：图的邻点可区别均匀V-全染色（AVDEVTC）是指在满足邻点可区别V-全染色的基础上，还要保证每种颜色的使用次数相差不超过1，把完成AVDEVTC所用的最少颜色称为图的邻点可区别均匀V-全色数（AVDEVTCN）。针对图的AVDEVTC问题，提出了一种基于多目标优化的染色算法。设计了一个总目标函数和四个子目标函数，在染色矩阵上通过每个点的颜色集合的迭代交换操作，使得每个子目标函数都达到最优，进而满足总目标函数的要求，完成染色。经过理论分析和实验对比表明，8个顶点以内的所有简单连通图都存在AVDEVTC，且图的AVDEVTCN介于最大度加1与最大度加2之间。实验结果表明，该染色算法能够在较短的时间内正确地计算出1000个顶点以内的图的AVDEVTCN。
关键词：染色算法,目标函数,多目标优化,邻点可区别均匀V-全染色,邻点可区别均匀V-全色数
基金资助：国家自然科学基金资助项目（11461038，61163010，61163037）；兰州交通大学青年基金资助项目（2016014）。
