| 一种判定图中Hamilton圈的邻接边增长算法 |
| |
| 引用本文： | 李鸿,胡学钢. 一种判定图中Hamilton圈的邻接边增长算法[J]. 计算机技术与发展, 2004, 14(7) |
| |
| 作者姓名： | 李鸿 胡学钢 |
| |
| 基金项目： | 安徽省教育厅自然科学基金 |
| |
| 摘 要： | 一个图是否为Hamilton图在于图中是否有Hamilton圈.文中提出了变换的方法来寻找图中的Hamilton圈,即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈.由此,设计了一个在Edmonds意义下的有效算法--自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换,证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n2).最后通过应用实例说明该算法的有效性和实用性.
|
| 关 键 词： | Hamilton圈 简单无向图 邻接边增长算法 邻接边增长变换 |
Adjacency Edge Growth Algorithm for Determining Hamilton Circle of a Simple Undirected Graph |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
