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

发布时间：2019-05-17 10:29

【摘要】：图的邻点可区别均匀V-全染色(AVDEVTC)是指在满足邻点可区别V-全染色的基础上,还要保证每种颜色的使用次数相差不超过1,把完成AVDEVTC所用的最少颜色称为图的邻点可区别均匀V-全色数(AVDEVTCN)。针对图的AVDEVTC问题,提出了一种基于多目标优化的染色算法。设计了一个总目标函数和四个子目标函数,在染色矩阵上通过每个点的颜色集合的迭代交换操作,使得每个子目标函数都达到最优,进而满足总目标函数的要求,完成染色。经过理论分析和实验对比表明,8个顶点以内的所有简单连通图都存在AVDEVTC,且图的AVDEVTCN介于最大度加1与最大度加2之间。实验结果表明,该染色算法能够在较短的时间内正确地计算出1 000个顶点以内的图的AVDEVTCN。
[Abstract]:The adjacent point of the graph can be distinguished from uniform V-full dyeing (AVDEVTC), which means that on the basis of satisfying the distinguishing V-full dyeing of the adjacent points, it is also ensured that the number of use times of each color is not more than 1, and the minimum color used for completing the AVDEVTC is called the adjacent point of the map to be distinguished from the uniform V-panchromatic number (AVDEVTCN). In order to solve the problem of AVDEVTC, a dyeing algorithm based on multi-objective optimization is proposed. A total objective function and four sub-objective functions are designed, and the iterative switching operation of the color set of each point is performed on the dyeing matrix, so that each sub-objective function is optimal, and the requirements of the total objective function are met, and the dyeing is finished. The theoretical analysis and experimental comparison show that the AVDEVTC exists in all simple communication graphs within 8 vertexes, and the AVDEVTCN of the graph is between the maximum and the maximum of 2. The experimental results show that the algorithm can correctly calculate the AVDEVTCN of the graph with less than 1,000 vertexes in a short time.
【作者单位】：兰州交通大学电子与信息工程学院;兰州交通大学应用数学研究所;
【基金】：国家自然科学基金资助项目(11461038,61163010,61163037) 兰州交通大学青年基金资助项目(2016014)~~
【分类号】：O157.5

【相似文献】