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

• 作者: 牟廉明
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 线性有向k-部图 k-初级通路 H回路
• 年，卷（期）: 2007,（17）
• 所属期刊栏目: 人工智能及识别技术
• 页码范围: 208-210
• 页数: 3页
• 分类号: TP301.6
• 字数: 4234字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2007.17.071

摘要

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