求有向图的所有Hamilton回路的新方法

摘要：

引入了单源单汇线性有向k-部图,设计了该结构上的删除算法、合并算法和输出算法,在此基础上给出了判断有向图是否含有H回路的多项式时间算法和计算H回路数的多项式时间算法,给出了求解有向图的所有H回路算法,并通过实例验证了算法的有效性,解决了H回路的判定、计数和求解问题.

关键词：线性有向k-部图、k-初级通路、H回路

所属期刊栏目：33

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金10472042;10672151;四川省教育厅资助项目2004B020

在线出版日期：2007-11-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：208-210