哈密顿圈问题

哈密顿圈问题(Hamilton circuit problem)是图论中著名的难题之一。巡回售货员问题有一个基于图的天然类似问题，它是图论中的一个基本问题，给定一个有向图G(V，E)，如果G中的圈C恰好经过每一个顶点一次，则称圈C是一个哈密顿圈。换句话说，它构成一条经过所有顶点的、没有重复的“路线”。哈密顿圈问题如下：给定一个有向图G，问它有一条哈密顿圈吗?

基本介绍设有一个图，若其上存在一个圈，这个圈包含该图上的每一节点，则称该圈为哈密顿圈，这个图称为哈密顿图.哈密顿圈问题可叙述为：什么样的图为哈密顿图，或者说判断一个图是哈密顿图的行之有效的充分必要条件是什么.目前这一问题尚未解决.关于哈密顿圈的研究，最早是欧拉(L.Euler)研究骑士(相当于中国象棋中的马)从棋盘上的某一位置出发，走遍所有可能的位置且每个位置只通过一次后，回到原来的位置，而哈密顿(W.R.Hamilton)研究环游世界的游戏是在欧拉之后近一个世纪，然而却由此开始引起人们对于这个问题的注意.实际上，哈密顿的游戏就是，在一个正十二面体上，从一个顶点开始沿着棱走遍所有的十二个顶点回到原地，使得每一顶点只通过一次.就是在十二面体相应的图上求一个哈密顿圈.若一个图上存在一条路，这条路包含该图上的所有节点，则称该图为可迹图，称这样的路为哈密顿路，若对于一个图上的每一节点，存在一个以该节点为始点的哈密顿路，则称该图为齐次可迹图，一个图被称为哈密顿连通图，若对于这图上任何两节点，存在一条哈密顿路连结这两节点，称一个图为亚哈密顿图，若从这图上去掉无论哪一节点，所得的图都是哈密顿图，称一个图为亚可迹图，若从这图上去掉无论哪一节点，所得的图都是可迹图1。

哈密顿圈火星运河悖论X国的人造火星卫星发现了火星上的运河水道还有20个城市遗址，如图1所示。每个城市用一个拉丁字母来代表。最南边的T是火星的“南极城”。X国《天地指南报》刊登了如下悬赏100万美元征解的题目：从某个火星城出发，沿运河水路而行，每个城必须经过而且只经过一次，并且所经过的城市的代表字母恰好能拼写成一句话。问，是否有这样的途径?如果有，请把它画出来2。

《天地指南报》编辑很快收到5万多封读者来信，都回答“不可能存在这样的途径”(There is no possible way)。

读者的答案是“正确”的：图1中已用1～20标出了这个途径——从“南极城”T出发到达终点y。由一路上所经过的城市的代表字母，就拼写成了“There is no possible way”，其含义是“不可能存在这样的途径”；但是，这句话的意思就是有这样的途径，即这样的途径是存在的。

从字面意思来看的话，“不可能存在这样的途径”(There is no possibleway)表示不存在题目中要求的途径；而事实上又存在这样的途径。这就导致了自相矛盾的局面。这就是所谓的“火星运河悖论”。

读者回答的“不可能存在这样的途径”，是这个图1上的一条“哈密顿轨道”。如果从y再走到“南极城”T，则从“南极城”出发又回到了“南极城”，这又是一个“哈密顿圈”。这样，图1就是“哈密顿图”2。

为什么都与哈密顿有关呢?

哈密顿周游世界问题1859年，英国数学家、物理学家威廉·罗恩·哈密顿(1805～1865)，提出了以下“周游世界游戏”，据说公布在当地市场上：用图2那样的一个正12面体的20个顶点来表示地球上的20个城市，如何才能从某个城市出发，沿着各条棱走正好只经过每个城市一次，最后返回到出发地点?

哈密顿的问题，被他简化为图3的左或右所示的“棋盘”平面图形问题。哈密顿还自豪地用棋盘做了形象明了的说明：“12面遨游，单身周游列国游戏。

本玩具是钦命的爱尔兰天文学博士、爵士威廉·罗恩·哈密顿的发明。宴席上，作为即兴表演，稀奇无比。”

因为是皇帝钦命的天文学博士发明的玩具，大家都十分感兴趣。于是，当时英伦三岛掀起了一股“单身周游列国”热2。

最后，这个问题已由哈密顿本人解决。他的答案如图4所示，与前面的“不可能存在这样的途径”本质上相同。图4中从1→20→1，就形成了一个哈密顿圈，即哈密顿图。已经证明，除此之外采用别的本质不同的方式，是不能按要求周游世界的。

不只外国人钟情“单身周游列国”，中国著名数学家苏步青(1902-2003)也是“爱好者”之一。

苏步青从图3右边“周游世界棋盘”里的12个大大小小的五边形中，挑出了6个(图5中画有斜线的那6个)，这6个五边形在原正12面体中的位置如图6所示。再把图6所示的6个五边形“摊平”，就得到图7那样的有20个顶点的20边形。

|| ||

那么，到现在问题已经变得简单化了。只要从图7的点A出发，沿着20边形的边界走一圈，就可以“周游列国”了2。

哈密顿和苏步青把一个12面体“压扁”、变形后再进行研究的方法，值得我们深思。

“周游世界棋盘”问题是哈密顿问题的特例，其对象后来也扩展为一般的m×n棋盘上走马步的问题。用电子计算机研究之后，目前的成果有：对任意奇数的m，n，m×n，棋盘上不存在马的哈密顿同路；国际象棋8 x 8的棋盘上至少存 苏步青在10条哈密顿回路；中国象棋9×10的棋盘上至少存在300条哈密顿回路。这些问题，包括中国数学工作者在内的许多学者仍在不断地寻找解决方法。

要判定一个图是否具有哈密顿圈的问题，是图论中著名的难题之一。除个别情形以外，迄今为止还没有找到一个图是否具有哈密顿圈的必要而且充分的条件。

哈密顿圈问题引出了诸如货郎问题、邮递员问题等类似的问题。比如，货郎问题就是货郎必须到每个村庄售货，怎样走才能使路程最短?当然，这个问题因为还要求“路程最短”，比哈密顿圈问题难度更大，以致用现代电子计算机来解决都很复杂。

这类问题的研究，促进了最优化方法、图论等问题的研究，促进了运筹学、拓扑学等学科的发展2。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学