无向哈密顿图的一个充分必要条件及计算公式

• 作者: 侯爱民 郝志峰
• 来源期刊: 计算机工程与应用
• 学科: 数学
• 关键词: 原子圈 分解 合并 单条公共边连通 充分必要条件 必要条件计算公式
• 年，卷（期）: 2011,（14）
• 所属期刊栏目: 博士论坛
• 页码范围: 7-9,69
• 分类号: O157.5
• 字数: 5148字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2011.14.003

摘要

哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一.1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果.根据无向哈密顿图的特征,提出了基本圈的分解、合并、单条公共边连通,原子圈等概念.任何一个简单连通无向图G是哈密顿图,当且仅当,哈密顿圈要么其本身就是一个包含所有顶点的原子圈;要么总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通.根据这个充分必要条件,推导出了一个必要条件计算公式.它不仅能处理平面图,也能处理非平面图;甚至能处理某些Grinberg条件不能处理的平面图.此外,对一些实际案例的测试结果验证了充分必要条件和计算公式的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郝志峰	华南理工大学计算机科学与工程学院	78	987	15.0	29.0
2	侯爱民	华南理工大学计算机科学与工程学院	3	11	2.0	3.0