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

摘要

哈密顿图的判定问题是一个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-Hamiltonian 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,mergenea and connection in common 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 itseff is an atomic cycle which contains every vertex of G or the Hamiltonian 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.