作　　者： ; ;

机构地区： 中山大学

出　　处： 《中山大学学报（自然科学版）》 2006年第2期20-24,共5页

摘　　要： 研究简单图中所有的Ham ilton回路,不但可以判断简单图是否Ham ilton图,并且还可以得到简单图的所有的Ham ilton回路。首先在简单图中建立了初级通路的关联关系,并对初级通路的关联关系进行了分层,在此基础上,设计了求简单图中所有Ham ilton回路的算法。该算法利用简单图中长度为x的初级通路及长度为x的初级通路的分层关联关系逐步求长度为x+1的初级通路及长度为x+1的初级通路的分层关联关系的方法,求得简单图的所有Ham ilton回路。通过理论证明,该算法与已有的求简单图的所有Ham ilton回路的算法相比,原有的求简单图的所有Ham ilton回路算法中大量的重复计算被避免,从而提高了算法的效率。 Researching all Hamiltonian cycle in simple graph can not only know whether this graph is Hamiltonian or not, but also obtain all Hamiltonian cycles of this graph. Hierarchical correlation of path is built. Based on hierarchical correlation, an algorithm for identifying all Hamiltonian cycles in simple graph is built. Through correlation of path in which path＇s length is x, path and correlation of path in which path＇s length is x ＋ 1 are obtained, step by step, all Hamiltonian cycles are obtained. That the complexity of this algorithm has been reduced is shown.

关 键 词： 简单图 回路 关联关系 初级通路

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