| 无向哈密顿图的一个充分必要条件及计算公式 |
| |
| 引用本文： | 侯爱民,郝志峰.无向哈密顿图的一个充分必要条件及计算公式[J].计算机工程与应用,2011,47(14):7-9. |
| |
| 作者姓名： | 侯爱民 郝志峰 |
| |
| 作者单位： | 1. 华南理工大学计算机科学与工程学院,广州510006;东莞理工学院计算机科学与技术系,广东东莞523808
2. 华南理工大学计算机科学与工程学院,广州,510006 |
| |
| 基金项目： | 广东省自然科学基金重点项目，广东省科技计划项目 |
| |
| 摘 要： | 哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一。1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果。根据无向哈密顿图的特征,提出了基本圈的分解、合并、单条公共边连通,原子圈等概念。任何一个简单连通无向图G是哈密顿图,当且仅当,哈密顿圈要么其本身就是一个包含所有顶点的原子圈;要么总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通。根据这个充分必要条件,推导出了一个必要条件计算公式。它不仅能处理平面图,也能处理非平面图;甚至能处理某些Grinberg条件不能处理的平面图。此外,对一些实际案例的测试结果验证了充分必要条件和计算公式的有效性。
|
| 关 键 词： | 原子圈 分解 合并 单条公共边连通 充分必要条件 必要条件计算公式 |
| 修稿时间： | |
Sufficient and necessary condition for undirected Hamiltonian graph and its formula |
| |
| HOU Aimin,HAO Zhifeng.Sufficient and necessary condition for undirected Hamiltonian graph and its formula[J].Computer Engineering and Applications,2011,47(14):7-9. |
| |
| Authors: | HOU Aimin HAO Zhifeng |
| |
| Affiliation: | 1.College of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,China 2.Department of Computer Science and Technology,Dongguan University of Technology,Dongguan,Guangdong 523808,China |
| |
| Abstract: | As an NP-complete problem,Hamiltonian graph problem is one of the main unresolved problems in graph theory. In 1968 Grinberg advanced a necessary condition for Hamiltonian planar graphs,which enhanced the solution of non-Hamilto- nian planar graphs and led to a series of research work on 3-regular 3-connected non-Hamiltonian planar graphs.Based on the characteristic of undirected Hamiltonian graph,some new notions about decomposition,mergence and connection in com- mon edge of basic cycles,as well as atomic cycle are defined.Any a connected simple undirected graph G is a Hamiltonian graph if and only if either the Hamiltonian cycle itself is an atomic cycle which contains every vertex of G or the Hamilto- nian cycle can always be decomposed into several atomic cycles which are connected with one another by one common edge in a certain order.A new necessary condition formula is derived from this sufficient and necessary condition which can deal with not only planar graphs but also non-planar graphs,even more those planar graphs which can not be treated by Grinberg condition.Moreover,experimental results on some real cases demonstrate the effectiveness of this condition and its formula |
| |
| Keywords: | atomic cycle decomposition mergence connection in one common edge sufficient and necessary condition formula of necessary condition |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
