一种判定图中Hamilton圈的邻接边增长算法

• 作者: 李鸿 胡学钢
• 来源期刊: 微机发展
• 学科: 工学
• 关键词: Hamilton圈 简单无向图 邻接边增长算法 邻接边增长变换
• 年，卷（期）: 2004,（7）
• 所属期刊栏目: 理论、算法及智能研究
• 页码范围: 103-105
• 页数: 3页
• 分类号: TP301.6
• 字数: 2719字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2004.07.036

摘要

一个图是否为Hamilton图在于图中是否有Hamilton圈.文中提出了变换的方法来寻找图中的Hamilton圈,即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈.由此,设计了一个在Edmonds意义下的有效算法--自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换,证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n2).最后通过应用实例说明该算法的有效性和实用性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡学钢	合肥工业大学计算机与信息学院	314	3156	27.0	39.0
2	李鸿	合肥工业大学计算机与信息学院	37	117	5.0	9.0