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

摘要：

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

关键词：Hamilton圈、简单无向图、邻接边增长算法、邻接边增长变换

所属期刊栏目：14

分类号：TP301.6(计算技术、计算机技术)

资助基金：安徽省教育厅自然科学基金2002kj298zc

在线出版日期：2004-08-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：103-105