输出图的全部Hamiltonian回路的新算法

为求出图的全部哈密顿回路，本文提出了H集合、连接积、H矩阵和通路矩阵等概念。给出了基于这些概念下的一些哈密顿回路的存在性判定定理和通过构造通路矩阵序列Mk=Mk-1*M(k=2,...,n)的办法输出简单图（无向或有向）的全部哈密顿回路的算法和实例。本算法特别适合寻找图的最短哈密顿回路，较其它算法更为简单直观。

A New Algorithm for Outputing All Hamiltonian Circuits of a Graph or Digraph

In order to find out all Hamiltonian tours of a graph, this paper puts forward the concepts about H sets, H matrices joining product and path matrix, etc. By means of these concepts, some theorems for judgementing the existence of the Hamiltonian circuit are drawn in the paper. Here we also describe a new algorithm for generating all Hamiltonian tours of a graph or digraph by constructing the matrix sequence of the paths, and some examples are given. The algorithm is specially suitable for finding a shortest Hamiltonian circuit. It is more simple and more direct than other algorithms.