Abstract: To construct an extremal graph with a given girth is still a challenging problem of graph theory.Especially when the vertex number increasex combination explosion will appear.Thus,this paper proposes an algorithm for constructing graphs with given girth based on quantum evolution.By making full use of the characteristics of the extremal graphs in producing and adjusting the individuals,it makes the algorithm achieve higher convergence speed and precision.Experimental results show that,by constructing the graphs with the girth of 10,the proposed algorithm is compared with the other algorithms,namely Particle Swarm Optimization(PSO) algorithm and Genetic Algorithm(GA),the algorithm can achieve the optimal solutions and near optimal solutions with the highest accuracy.It uses the proposed algorithm to construct the graphs with the girth of 11,and gives lower bounds of the sizes of extremal graphs with the girth 11.

Key words: evolutionary algorithm, Quantum Evolutionary Algorithm(QEA), extremal graph, girth, cycle

摘要： 构造给定围长的极图是图论难题之一,特别是在顶点数规模不断增大的情况下会出现组合爆炸的现象。针对该问题,提出一种构造给定围长图的算法,通过在生成个体、调整个体中充分利用极图的特性,使算法达到较高的收敛速度与收敛精度。实验结果表明,通过构造围长为10的图,与粒子群优化算法、遗传算法相比,该算法达到次优解和最优解的准确率最高,构造围长为11的图,可得到相应的极图边数的下界。

关键词: 进化算法, 量子进化算法, 极图, 围长, 圈

CLC Number: 

• TP391