|
|||||
|
|
| 有向哈密顿回路问题的一个充分条件及其多项式验证算法 | |
| 引用本文： | 曹卫华,刘富春.有向哈密顿回路问题的一个充分条件及其多项式验证算法[J].云南大学学报(自然科学版),2023(3):555-563. |
| 作者姓名： | 曹卫华 刘富春 |
| 作者单位： | 广东工业大学计算机学院 |
| 基金项目： | 国家自然科学基金(61673122)；;广东省自然科学基金(2023A1515012783)； |
| 摘 要： | 利用自动机理论研究有向哈密顿回路问题，提出一个多项式复杂度的算法验证有向哈密顿回路问题的一个充分条件.更具体地说，将有向图建模为一个自动机，并在自动机的基础上形式化了哈密顿图的相关概念，然后提出了一个多项式复杂度的算法，检验一个自动机标记的语言的子集是否满足真子集的一个充分条件.在该算法的基础上，提出了一个多项式复杂度的算法检验哈密顿图的一个充分条件并找出相应的哈密顿回路.特别地，给出了一个判断有向图是否是哈密顿图的充分条件和一个判断有向图中的一条回路是否是哈密顿回路的充分条件. |
| 关 键 词： | 有向哈密顿图 有向哈密顿回路 充分条件 多项式复杂度算法 离散事件系统 自动机 |