图上编造的谎言

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

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

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

在字面上，“不可能存在这样的途径”(There is no possibleway)表示不存在题目中要求的途径；而事实上又存在这样的途径。这就形成了自相矛盾的幽默。这就是“火星运河悖论”。

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

那怎么都与哈密顿有关呢？

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

哈密顿的问题，被他简化为左或右所示的“棋盘”平面图形问题。哈密顿还自豪地在棋盘上做了这样的说明：“12面遨游，单身周游列国游戏。本玩具是钦命的爱尔兰天文学博士、爵士威廉·罗恩·哈密顿的发明。宴席上，作为即兴表演，稀奇无比。”

皇帝钦命的天文学博士发明的玩具，一定会与众不同。于是当时英伦三岛掀起了一股“单身周游列国”热。

最后，这个问题已由哈密顿本人解决。他的答案所示——与前面的“不可能存在这样的途径”本质上相同。从1→20→1，就形成了一个哈密顿圈，即哈密顿图。

已经证明，除此之外采用别的本质不同的方式，是不能按要求周游世界的。

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

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

好，现在问题简单了。只要从点A出发，沿着20边形的边界走一圈，就可以“周游列国”了。

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

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

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

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

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