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

Sufficient and necessary condition for undirected Hamiltonian graph and its formula

作　　者：侯爱民[1,2] 郝志峰[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510006 [2]东莞理工学院计算机科学与技术系,广东东莞523808

出　　处：《计算机工程与应用》2011年第14期7-9,69,共4页Computer Engineering and Applications

基　　金：广东省自然科学基金重点项目(No.9251009001000005);广东省科技计划项目(No.2008B080701005)

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

关 键 词：原子圈 分解 合并 单条公共边连通 充分必要条件 必要条件计算公式 

分 类 号：O157.5[理学—数学]