一种基于关联矩阵判断图的哈密顿性及求解哈密顿回路的算法  

An incidence-matrix-based algorithm for determining the Hamiltonian of a graph and identifying the Hamiltonian circuit

作　　者：王亚丽 徐晨东[1] WANG Ya-li;XU Chen-dong(Faculty of Science,Ningbo University,Ningbo 315211,China)

机构地区：[1]宁波大学理学院,浙江宁波315211

出　　处：《宁波大学学报（理工版）》2018年第2期83-88,共6页Journal of Ningbo University：Natural Science and Engineering Edition

基　　金：国家自然科学基金(11101230;11371209)

摘　　要：基于对图的关联矩阵分析,刻画了哈密顿回路的关联矩阵的有关性质,给出了简单无向图和有向图为哈密顿图的充分条件和具体算法,该算法不仅可以判断简单图的哈密顿性,而且可以找出该图的所有哈密顿回路.最后用实例说明该算法的正确性和有效性.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

关 键 词：哈密顿图 哈密顿回路 关联矩阵 

分 类 号：O157.5[理学—数学]