摘要
从Hamilton回路的定义和图的邻接矩阵的定义入手,建立了图中的初级通路的关联关系.利用长度为k的初级通路及其关联关系逐步求长度为k+1的初级通路及其关联关系的方法,求得图的所有Hamilton回路.通过理论分析,说明该算法比已有的求图的所有的Hamilton回路的算法降低了算法的复杂度,为求解Hamilton回路问题提供了新思路.
Having started with the definition of Hamiltonian cycle and of the adjacency matrix of a graph, a correlation of path is built in the graph. Through correlation of path in which path＇s length is k, correlation of path in which path＇s length is k ＋ 1 are obtained, step by step, and so we obtain all Hamiltonian cycle. The complexity of algorithm has been reduced, and a new thought for calculating Hamilton cycle problem has been provided.
出处
《湘潭大学自然科学学报》
CAS
CSCD
北大核心
2005年第4期34-41,共8页
Natural Science Journal of Xiangtan University
基金
湖南省自然科学基金资助项目(02JJY2091)
