单圈图的优美标号算法研究

Algorithm of graceful labeling of unicyclic graphs

优美标号是图标号问题的起源,其有着广泛的应用价值。图的优美标号是指对图的顶点或边用自然数进行标号,并使这些标示数字满足一定的条件。Truszczyński提出优美单圈图猜想:除了圈Cn,n(mod 4)={1,2},之外,其它所有单圈图都是优美的。针对该猜想,设计了一种单圈图优美性验证算法,给出了预判断函数对算法进行优化,并对猜想进行计算机证明,即对每一个单圈图进行优美标号。利用该算法,对18个点内的所有单圈图进行了优美性标号。实验结果表明,对于单圈图来说,除了圈图Cn,n(mod 4)={1,2}之外,18个点内所有单圈图都是优美的。

Graceful labelling is the origin of graph labelling problem,which has a wide range of application value. A graph labelling is an assignment of integers to the vertices or edges,or both with some conditions. Truszczyński proposed conjecture of unicyclic graph： the all unicyclic graphs are graceful except Cn,n（ mod 4） = { 1,2}. An algorithm with a prejudgment function which is applied to optimize algorithm is designed to verify the gracefulness of unicyclic graphs. By the algorithm,the all unicyclic graphs are labeled within 18 vertice. The experimental results show that all the unicyclic graphs are graceful except the Cn,n（ mod 4） = { 1,2} within 18 vertice.