图(n≤9)的优美性

• 作者: 李敬文 武永兰 魏众德
• 来源期刊: 中山大学学报（自然科学版）
• 学科: 数学
• 关键词: 优美标号 优美图 非优美图 优美空间 算法
• 年，卷（期）: 2018,（4）
• 页码范围: 76-85
• 页数: 10页
• 分类号: O157.5
• 字数: 5261字
• 语种: 中文
• DOI: 10.13471/j.cnki.acta.snus.2018.04.010

摘要

设计了一种递归回溯算法,采用了剪枝函数与预判函数相结合的算法优化策略,实现了对有限点内任意图的优美性验证.利用该算法,对9个点内的所有简单连通图进行了优美性验证,得到该范围内所有优美图和非优美图的数量.结果表明,在该范围内绝大多数的图是优美的.并且根据实验数据,文中还得出以下结果:Kn-m(由完全图减去m条边所得的图)是非优美图的确定下界;当p、q满足一定条件时,这类(p,q)图(p为顶点数,q为边数)中的所有图全部是优美的;当q(mod4)={0,3},且q≤[3.7p-9.3]时,(p,q)图中几乎所有的图都是优美的.且进一步猜测,当p>9时,相关结论成立.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李敬文	兰州交通大学电子与信息工程学院	91	810	11.0	26.0
2	武永兰	兰州交通大学电子与信息工程学院	3	8	2.0	2.0
3	魏众德	兰州交通大学电子与信息工程学院	6	9	2.0	3.0