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

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

Abstract: This paper introduces the new linear k-partite digraph with single jumping-off and end point. Delete-algorithm, combination-algorithm and output-algorithm are designed. The algorithms with polynomial-time to judge whether or not there is Hamiltonian cycle in the digraph and to count the Hamilton cycle are designed. The algorithm to solve all Hamilton cycles in the digraph is constructed. The algorithmic validity is validated by example. Judgment, count and output of Hamilton cycle are effectually solved.

Key words: linear k-partite digraph, k-elementary access, Hamilton cycle

中图分类号: 

• TP301.6