陈帅君，徐美进，李永明

（辽宁工业大学 理学院，辽宁 锦州 121001）

0 引言

图论以1736年欧拉提出的“哥尼斯堡七桥问题”为起源，经历了近300年的发展沉淀，至今无论是在理论或是应用方面它都有着极其重要的价值. 所谓图论就是对某些点和连接这些点的线所组成集合的某些性质的研究，对于某个连通图来说，经过该图的每条边的迹，称之为欧拉迹；若存在某条路覆盖了每条边恰好一次的回路，称之为欧拉环游，含有欧拉环游的图称之为欧拉图. 若存在某条路覆盖了每个顶点恰好一次，则称之为哈密尔顿路；假如这样的路是一条回路，则称这样的路为哈密尔顿回路；含有哈密尔顿回路的图，称之为哈密尔顿图. 若图中的任意两个顶点都有哈密尔顿路连接着，那么称这类图为哈密尔顿连通图.

图的哈密尔顿性是结构图论一个非常重要而且意义深远的研究课题，该问题的产生和发展与著名的四色猜想研究密切相关，因而备受国内外众多图论专家和学者的关注. 图的哈密尔顿路问题与结构图论中哈密尔顿性的研究也是密切相关的. 从算法复杂性来讲，判定一个图是否存在一条哈密尔顿路是NP-完全的. 对于某个图是欧拉图成立的条件已经解决：一个非空连通图含有欧拉迹当且仅当其最多含有两个奇点；一个非空的连通图是欧拉图当且仅当它没有奇点. 如图1哥尼斯堡七桥图，图2为其简化图. 图2四个顶点都是奇点，因此从任意点……