一种基于关联矩阵判断图的哈密顿性及求解哈密顿回路的算法
PDF下载 (13137)王亚丽,徐晨东 *.一种基于关联矩阵判断图的哈密顿性及求解哈密顿回路的算法[J].宁波大学学报(理工版),2018,31(2):83-88.DOI:
WANG Ya-li,XU Chen-dong *.An incidence-matrix-based algorithm for determining the Hamiltonian of a graph and identifying the Hamiltonian circuit[J].Journal of Ningbo University(Natural Science & Engineering Edition),2018,31(2):83-88.DOI:
| Title: | An incidence-matrix-based algorithm for determining the Hamiltonian of a graph and identifying the Hamiltonian circuit |
| 作者: | 王亚丽, 徐晨东 * |
| Author(s): | WANG Ya-li, XU Chen-dong * |
| 关键词: | 哈密顿图; 哈密顿回路; 关联矩阵 |
| Keywords: | Hamiltonian graph; Hamiltonian circuit; incidence matrix |
| 分类号: | O157.5 |
| 文献标识码: | A |
| 摘要: | 基于对图的关联矩阵分析, 刻画了哈密顿回路的关联矩阵的有关性质, 给出了简单无向图和有向图为哈密顿图的充分条件和具体算法, 该算法不仅可以判断简单图的哈密顿性, 而且可以找出该图的所有哈密顿回路. 最后用实例说明该算法的正确性和有效性. |
| Abstract: | Based on the incidence matrix of given graph, this paper describes the properties of the incidence matrix of the Hamiltonian circuit, and presents the sufficient condition and the specific algorithm for both simple undirected graph and directed graph. The algorithm not only judges whether or not a given graph is a Hamiltonian graph, but also finds all the Hamiltonian circuits of the graph. In the end, some examples are given to validate of the presented algorithm. |
| 参考文献 /References: | [1] Rubin F. A search procedure for Hamilton paths and circuits[J]. Journal of the Association for Computing Machinery, 1974, 21(4):576-580. [2] Dirac G A. Some theorems on abstract graphs[J]. Proceedings of the London Mathematical Society, 1952, 2(1):69-81. [3] Ore O. Hamilton connected graphs[J]. Journal De Mathématiques Pures Et Appliqués, 1963, 42:21-27. [4] Chvátal V, Erd?s P. A note on Hamilton circuits[J]. Discrete Mathmatics, 1972, 2:111-113. [5] Fan G H. New sufficient conditions for cycles in graphs [J]. Journal of Combinatorial Theory (Series B), 1984, 37:221-227. [6] Faudree R J. Neighborhood unions and Hamiltonian properties in graphs[J]. Journal of Combinatorial Theory (Series B), 1989, 47:1-9. [7] Li J S, Li J R, Feng J F. An efficient condition for a graph to be Hamiltonian[J]. Discrete Applied Mathematics, 2007, 155:1842-1845. [8] Zhao K W, Lai H J, Shao Y H. New sufficient condition for Hamiltonian graphs[J]. Applied Mathematics Letters, 2007, 20:116-122. [9] Zhao K W, Gould R J. A note on the Song-Zhang theorem for Hamiltonian graphs[J]. Colloquium Mathematicum, 2010, 120(1):63-75. [10] 姜新文. 求解哈密顿图判定问题的一个新算法[J]. 计算技术与自动化, 1997, 16(1):1-3. [11] 陈德钦, 赵克文. 一般图的哈密顿图的研究进展[J]. 数学理论与应用, 2011, 31(2):92-99. [12] 侯爱民, 郝志峰. 无向哈密顿图的一个充分必要条件及计算公式[J]. 计算机工程及应用, 2011, 47(14):7-9. |
| 备注/Memo: | 收稿日期: 2017－05－31. 宁波大学学报（理工版）网址: http://journallg.nbu.edu.cn/ 基金项目: 国家自然科学基金（11101230, 11371209）. 第一作者: 王亚丽（1990－）, 女, 河南洛阳人, 在读硕士研究生, 主要研究方向: 计算几何. E-mail: 18892614929@163.com *通信作者: 徐晨东（1977－）, 男, 浙江慈溪人, 副教授, 主要研究方向: 计算机辅助几何设计与计算几何. E-mail: xuchendong@nbu.edu.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
