| 一种判定图中Hamilton圈的邻接边增长算法 |
| |
| 引用本文： | 李鸿,胡学钢.一种判定图中Hamilton圈的邻接边增长算法[J].微机发展,2004,14(7):103-105. |
| |
| 作者姓名： | 李鸿 胡学钢 |
| |
| 作者单位： | 合肥工业大学计算机与信息学院，合肥工业大学计算机与信息学院 安徽合肥230009宿州学院计算机系安徽宿州234000，安徽合肥230009 |
| |
| 基金项目： | 2002年安徽省教育厅自然科学基金资助项目(2002kj298zc) |
| |
| 摘 要： | 一个图是否为Hamilton图在于图中是否有Hamilton圈。文中提出了变换的方法来寻找图中的Hamilton圈，即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈。由此，设计了一个在Edmonds意义下的有效算法——自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换，证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n^2)。最后通过应用实例说明该算法的有效性和实用性。
|
| 关 键 词： | Hamilton图 邻接边增长算法 邻接边增长变换 简单无向图 图论 |
| 文章编号： | 1005-3751(2004)07-0103-03 |
| 修稿时间： | 2003年11月16 |
Adjacency Edge Growth Algorithm for Determining Hamilton Circle of a Simple Undirected Graph |
| |
| LI Hong.Adjacency Edge Growth Algorithm for Determining Hamilton Circle of a Simple Undirected Graph[J].Microcomputer Development,2004,14(7):103-105. |
| |
| Authors: | LI Hong |
| |
| Abstract: | |
| |
| Keywords: | Hamilton circle simple undirected graph adjacency edge growth algorithm adjacency augment transformation |
| 本文献已被 CNKI 维普 等数据库收录！ |
