论文研究 无向哈密顿图的一个充分必要条件及计算公式.pdf

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