随机图的L(2,1)-标号混合人工蜂群算法

A Hybrid Artificial Bee Colony Algorithm for L(2,1)-Labelling of Random Graph

为解决图的L(2,1)-标号问题,设计了一种全新的标号算法,该算法利用人工蜂群全局搜索能力强的优点来得到最优的L(2,1)-标号方案。为了加快算法的收敛速度,修改了部分搜索策略并采用改进后的CK算法对初始蜜源进行限制。实验结果表明,该算法可以有效地求解有限点内随机图的L(2,1)-标号且10个点内的简单连通图都满足Griggs的猜想。通过分析实验结果总结出有关K_(n)\e、K_(n)\2e、联图K_(n)↑S_(m)以及太阳图等的相关定理,并结合已有结果给出了新的猜想。

In order to solve the problem L(2,1)-labelling of graphs, a new labelling algorithm is designed to obtain the optimal L(2,1)-labelling based on the advantages of strong global searching ability of artificial bee colony. Some search strategies are modified and the improved CK algorithm is used to limit the initial nectar source, which speeds up the convergence speed of the algorithm. It shows that the algorithm can effectively solve the L(2,1)-labelling of random graphs within finite points according to experimental results, and simple connected graphs within 10 points satisfy Griggs’ s conjecture. By analyzing the experimental results, we summarize the relevant theorems about K_(n)\e, K_(n)\2e, the composite graph K_(n)↑S_(m), and the sun graph, and give new conjectures combining the existing results.