首页
|
官方网站
微博
|
高级检索
全部学科
医药、卫生
生物科学
工业技术
交通运输
航空、航天
环境科学、安全科学
自然科学总论
数理科学和化学
天文学、地球科学
农业科学
哲学、宗教
社会科学总论
政治、法律
军事
经济
历史、地理
语言、文字
文学
艺术
文化、科学、教育、体育
马列毛邓
全部专业
中文标题
英文标题
中文关键词
英文关键词
中文摘要
英文摘要
作者中文名
作者英文名
单位中文名
单位英文名
基金中文名
基金英文名
杂志中文名
杂志英文名
栏目中文名
栏目英文名
DOI
责任编辑
分类号
杂志ISSN号
有向哈密顿回路问题的一个充分条件及其多项式验证算法
作者姓名:
曹卫华
刘富春
作者单位:
广东工业大学计算机学院
基金项目:
国家自然科学基金(61673122);;广东省自然科学基金(2023A1515012783);
摘 要:
利用自动机理论研究有向哈密顿回路问题,提出一个多项式复杂度的算法验证有向哈密顿回路问题的一个充分条件.更具体地说,将有向图建模为一个自动机,并在自动机的基础上形式化了哈密顿图的相关概念,然后提出了一个多项式复杂度的算法,检验一个自动机标记的语言的子集是否满足真子集的一个充分条件.在该算法的基础上,提出了一个多项式复杂度的算法检验哈密顿图的一个充分条件并找出相应的哈密顿回路.特别地,给出了一个判断有向图是否是哈密顿图的充分条件和一个判断有向图中的一条回路是否是哈密顿回路的充分条件.
关 键 词:
有向哈密顿图
有向哈密顿回路
充分条件
多项式复杂度算法
离散事件系统
自动机
设为首页
|
免责声明
|
关于勤云
|
加入收藏
Copyright
©
北京勤云科技发展有限公司
京ICP备09084417号-23
京公网安备 11010802026262号