摘要
本文详尽讨论了有向循环图Ｇ（ｎ，α_１，α_２）存在哈密顿圈的充分必要条件，并揭示了其中哈密顿圈的组合结构。我们还构造了一个Ｏ（ｎ３）算法，当Ｇ（ｎ，α_１，α_２）为哈密顿图时，算法可求出它的所有哈密顿圈．
In this paper the Hamiltonicity of Circulant Digraph is considered. This problem is motivated by trying to solve the special case of the Travelling Salesman Problem where the distance matrices are circulant-a problem that is mentioned in the famous TSP book of Lawler et al.as being open(p.96).This paper presents necessary and sufficient conditions for Circulant Digraphs G(n,a1,a2)being Hamiltonian. Moreover,an efficient algorithm is presented for finding all Hamiltonian cycles of G(n,a1,a2)if they exist.
基金
国家自然科学基金
关键词
有向循环图
强连通分支
哈密顿圈
存在性
cicculant digraph
strongly connected components
hamiltoninan cycles
travelling salesman problem
efficient algorithm
