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

作     者：武永兰 魏众德 WU Yong-lan;WEI Zhong-de

作者机构：兰州交通大学电子与信息工程学院兰州730070 

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

出 版 物：《信息技术》 (Information Technology)

年 卷 期：2018年第42卷第9期

页      码：50-54页

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

主 题 词：图标号 优美标号 单圈图 标号算法 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.13274/j.cnki.hdzj.2018.09.011

馆 藏 号：203366339...