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

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

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

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