内容发布更新时间 : 2024/6/15 22:00:34星期一 下面是文章的全部内容请认真阅读。

从哈密尔顿图到旅行货郎问题

1979年11月7日《纽约时报》出现一篇引人注目的文章，它的标题是：《苏联的发现震动数学界》（Soviet Discovery Rocks World of Mathematics），这文章介绍一个本是默默无闻的年青数学家卡倩（L．G．Khachian），他在线性规划理论上的一个发现使到美国数学界为之轰动。由于记者在询问一些著名数学家时对数学问题了解不深，文章报导是有一些失实，但由这文章引起的轰动及误导是相当严重。我以后会讨论这问题。该文中说：“俄国人的发现建议用电子计算机处理一类和‘旅行货郎问题’（Travelling Salesman Problem）有关的数学上一个著名及难处理的问题。‘旅行货朗问题’目的是决定一个货郎（或推销员或销货员）所要跑的最短路程──他要走遍市镇，但是不能再回到走过的地方。表面上，这问题看来简单，事实上为了要解决这问题

的实际应用，人们需要电子计算机来解决。”

在这点上这记者是说对了。“旅行货郎问题”目前是许多国家（如西德、日本、苏联、英国、美国、法国）的运筹学工作者研究的热烈课题。为了要了解这问题，我们可要知道目前在图论（Graph Theory）上许多人正在研究一种图──哈密尔顿图（Hemilton

graphs）。 一、哈密尔顿图的由来

在17—18世纪时，欧洲宫庭及一些贵族很喜欢玩西洋象棋，西洋象棋中的骑士（knight）是对应我们中国象棋的“马”，而它通常是刻成一个马头，跑法也是和中国

象棋的“马”一样，走“日”线──即从日的一角沿着对角线跃到另一角。 在1771年，就有一位名叫范德蒙（A．Vandermonde）的法国数学家，写了一篇文章研究所谓“棋盘的骑士问题”。这问题是这样：在8×8的棋盘格的随意一个位置，我放一个骑士，然后我想法子使他跑遍棋盘的所有的格子，走过的不许再走，我能不能

使骑士最后回到原来的位置？

这个问题并不简单，许多象棋爱好者及数学家曾坐下来研究这个问题。我这里列出一个情形的解（见图一），我将棋盘的左下角的格选为起始位置，把它定为1，读者可

以验证根据图一的跑法，骑士最后是能跑回1的。

56 47 42 45 20 41 44 57 48 5 58 55 46 43 30 35 40 49 54 63 50 59 36 31 22 39 34 53 62 11 60 51 32 37 16 33 38 61 52 13 29 64 21 4 17 14 25 6 19 2 27 8 23 12 1 28 7 18 3 26 9 10 15 24 图一 “棋盘骑士问题”的一个解法

18世纪的大数学家欧拉（Euler），在1759年就系统地研究过这个问题，也得到了一些结果。以后德国数学家高斯也曾对这问题发生兴趣，花过一些时间研究它及另外

一个棋盘的“皇后问题”。

我们现在把棋盘上的格子对应在一个平面上的一个小圆点，这样我们在平面上就有64个小圆点。从一个格子用骑士的走法我们可以抵达不同数目的格子：如果是处在棋盘的四个角，只能有两种跑法；在其他边缘的格子就有三种跑法；一般当中的格子，就有四种可能的跑法。我们把平面上的点用弧线连接，两个点有一条弧线连起当且仅当（if and only if）我们可以从它们所对应的格子将骑士移动。我们得到了一个图（ graph）。

在图中取一个顶点v0，如果我们有一个弧线把它和另外一个点v1联起来，我们就用（v0，v1）来表示这个弧线。假定我有一系列点v0，v1，v2，?，vn其中没有两个相同以及一序列的弧线存在（v0，v1），（v1，v2），?，（vn-1，vn），（vn，v0），使到我从v0出发可以经过v1，v2，?，vn最后由vn回到v0，我就说这些弧线组成一个回路（circuit），

为了方便，我们用下面的记号表示这回路：（v0，v1，v2，?，vn，v0）。 如果我有一个图G有n+1个顶点（vertices）{v0，v1，v2，?，vn}，而我能找到一个回路（v0，v1，v2，?，vn，v0），那么我就说这个图是哈密尔顿图（Hamilton graph），

这个回路称为哈密尔顿回路（Hamilton circuit）。

因此，“棋盘的骑士问题”实际上就是要判断它所对应的图是否是哈密尔顿图的问

题。

为什么叫哈密尔顿图？哈密尔顿是谁呢？

哈密尔顿是爱尔兰的一位数学家和天文学家。他的一生是多姿多彩的，我在《数学和数学家的故事》第一集里有详细介绍他的工作和生平，读者可以找来一读。 自从哈密尔顿发现“四元数”之后，他又发现了另外一种他命名为“The Icosian Calculus”的代数系统，这系统有加和乘的运算子（operators），可是乘法不满足交

换律（Commutative law即xy=yx这个规律）。

他发现这代数系统是和正则20面体（regularicosion polybedron）有关系。他想到一个游戏，怎样跑遍正则多面体上的所有顶点，而最后又能回到起点的问题。在1857年他把这个游戏的想法以25英镑的价钱卖给一位玩具和游戏制造商。这25英镑在124年前是很好用，在今天拿去伦敦的“唐人区”买“牛腩面”吃可能连十碗都吃不到。

这玩具商把这游戏制造出来了（见图二），在圆盘上有20个代表城市的圆孔，你必须把20个上面标有1，2，3，?，20的木条顺序插进去，代表你经过不同的城市，最后回到原出发点。这个游戏叫“环游世界”，很可惜玩具商人没有从这游戏上赚到钱。

以后人们因这游戏就称这类图为哈密尔顿图。

THE ICOSIAN GAME

二、怎么样的图是哈密尔顿图

给你一个图，你怎么知道它是否是哈密尔顿图呢？当然如果图的顶点不多，你可以试试找哈密尔顿回路就可以解决和判断。你用的是最古老的“尝试和错误”的方法，但是数学家并不满意这样的碰得焦头烂额后才找到真理的方法。是否存在一组必要和充分的条件，使到我们能简单轻易地判断一个图是否哈密尔顿图？许多聪明人去试过了，很

可惜到现在这问题还未解决，因此读者可以试试自己来找寻一下。 英国数学家G．A．狄拉克（Dirac）在1952年给出一个充分条件使得一个图会是哈密尔顿图。他的定理是只要检查每一个顶点x，看它的上面有多少个弧通过，把这个数目用d（x）来表示，只要每一个点的d（x）是相当大的话，这图就会是哈密尔顿图。

狄拉克定理 给定一个图G，如果其顶点集V的元素数是n≥3，

由于我们可以看到以下的两个图G1，G2都是哈密尔顿图（见图三）。

到了1960年，美国著名的图论专家奥斯坦·奥勒（ Oystein Ore）推广狄拉克的