| 用分层关联方法求简单图中所有Hamilton回路的算法 |
| |
| 引用本文： | 文中华,姜云飞.用分层关联方法求简单图中所有Hamilton回路的算法[J].中山大学学报(自然科学版),2006,45(2):20-24. |
| |
| 作者姓名： | 文中华 姜云飞 |
| |
| 作者单位： | 1. 中山大学软件研究所,广东,广州,510275;湘潭大学信息工程学院,湖南,湘潭,411105
2. 湘潭大学信息工程学院,湖南,湘潭,411105 |
| |
| 基金项目： | 国家自然科学基金资助项目(60173039) |
| |
| 摘 要： | 研究简单图中所有的Ham ilton回路,不但可以判断简单图是否Ham ilton图,并且还可以得到简单图的所有的Ham ilton回路。首先在简单图中建立了初级通路的关联关系,并对初级通路的关联关系进行了分层,在此基础上,设计了求简单图中所有Ham ilton回路的算法。该算法利用简单图中长度为x的初级通路及长度为x的初级通路的分层关联关系逐步求长度为x 1的初级通路及长度为x 1的初级通路的分层关联关系的方法,求得简单图的所有Ham ilton回路。通过理论证明,该算法与已有的求简单图的所有Ham ilton回路的算法相比,原有的求简单图的所有Ham ilton回路算法中大量的重复计算被避免,从而提高了算法的效率。
|
| 关 键 词： | 简单图 Hamilton回路 关联关系 初级通路 |
| 文章编号： | 0529-6579（2006）02-0020-05 |
| 收稿时间： | 2005-03-10 |
| 修稿时间： | 2005年3月10日 |
An Algorithm for Finding All Hamiltonian Cycle in Simple Graph via Hierarchical Correlation |
| |
| WEN Zhong-hua,JIANG Yun-fei.An Algorithm for Finding All Hamiltonian Cycle in Simple Graph via Hierarchical Correlation[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2006,45(2):20-24. |
| |
| Authors: | WEN Zhong-hua JIANG Yun-fei |
| |
| Affiliation: | 1. Software Institute,Sun Yat-sen University, Guangzhou 510275, China;2. College of Information Engineering, Xiangtan University, Xiangtan 411105, China |
| |
| Abstract: | |
| |
| Keywords: | simple graph Hamiltonian cycle correlation path |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
