作　　者： ; ;

机构地区： 湘潭大学信息工程学院

出　　处： 《计算机研究与发展》 2005年第10期1809-1814,共6页

摘　　要： 首先建立了有向图中初级通路的关联关系,并对初级通路的关联关系进行了分析,得到了关于初级通路关联关系的一些重要结果·然后,对初级通路的关联关系进行了分级分层·在此基础上,设计了求有向图中所有Hamilton回路的算法·该算法利用长度为k的初级通路及其分层关联关系逐步求长度为k+1的初级通路及其分层关联关系的方法,求得有向图的所有Hamilton回路·通过理论分析可以看到,所设计的算法与已有的求有向图的所有Hamilton回路的算法相比,避免了大量的重复计算,从而降低了算法复杂度,为求解Hamilton回路问题提供了新思路· The problem to find all Hamiltonian cycles in a digraph is NP-hard, and there isn＇t an efficient algorithm to find all Hamiltonian cycles in a digraph. The traditional algorithm for finding all Hamiltonian cycles in a digraph is not information search, and an algorithm is designed for improving the speed of finding all Hamiltonian cycles in a digraph. Correlation of path and hierarchical correlation of path based on the concept of path are built in digraph. Based on hierarchical correlation, an algorithm for finding all Hamiltonian cycles in digraph is designed. Path and correlation of path in which path＇s length is k ＋ 1 are obtained by using hierarchical correlation step by step, k ＋ 1 becomes greater and of path in which path＇ s length is k greater. When k ＋ 1 is equal to n in the algorithm designed, and - 1, all Hamiltonian paths are obtained, so all Hamiltonian cycles are found through checking all Hamiltonian paths. The algorithms analysis indicate that the designed algorithm is more efficient than the current algorithms for finding all Hamiltonian cycles in digraph, so complexity of the algorithm is reduced. A new train of thought for calculating the Hamiltonian cycle problem is provided.

关 键 词： 有向图 回路 关联关系 初级通路

领　　域： [自动化与计算机技术] [自动化与计算机技术]