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

Algorithm of graceful labeling of unicyclic graphs

作　　者：武永兰 魏众德 WU Yong-lan;WEI Zhong-de(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《信息技术》2018年第9期50-54,共5页Information Technology

基　　金：国家自然科学基金项目(11461038)

摘　　要：优美标号是图标号问题的起源,其有着广泛的应用价值。图的优美标号是指对图的顶点或边用自然数进行标号,并使这些标示数字满足一定的条件。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.

关 键 词：图标号 优美标号 单圈图 标号算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]