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

《从哈密尔顿图到旅行货郎问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、从哈密尔顿图到旅行货郎问题1979年11月7日《纽约时报》出现一篇引人注目的文章，它的标题是：《苏联的发现震动数学界》（SovietDiscoveryRocksWorldofMathematics），这文章介绍一个本是默默无闻的年青数学家卡倩（L．G．Khachian），他在线性规划理论上的一个发现使到美国数学界为之轰动。由于记者在询问一些著名数学家时对数学问题了解不深，文章报导是有一些失实，但由这文章引起的轰动及误导是相当严重。我以后会讨论这问题。该文中说：“俄国人的发现建议用电子计算机处理一

2、类和‘旅行货郎问题’（TravellingSalesmanProblem）有关的数学上一个著名及难处理的问题。‘旅行货朗问题’目的是决定一个货郎（或推销员或销货员）所要跑的最短路程──他要走遍市镇，但是不能再回到走过的地方。表面上，这问题看来简单，事实上为了要解决这问题的实际应用，人们需要电子计算机来解决。”在这点上这记者是说对了。“旅行货郎问题”目前是许多国家（如西德、日本、苏联、英国、美国、法国）的运筹学工作者研究的热烈课题。为了要了解这问题，我们可要知道目前在图论（GraphTheory）

3、上许多人正在研究一种图──哈密尔顿图（Hemiltongraphs）。一、哈密尔顿图的由来在17—18世纪时，欧洲宫庭及一些贵族很喜欢玩西洋象棋，西洋象棋中的骑士（knight）是对应我们中国象棋的“马”，而它通常是刻成一个马头，跑法也是和中国象棋的“马”一样，走“日”线──即从日的一角沿着对角线跃到另一角。在1771年，就有一位名叫范德蒙（A．Vandermonde）的法国数学家，写了一篇文章研究所谓“棋盘的骑士问题”。这问题是这样：在8×8的棋盘格的随意一个位置，我放一个骑士，然后我想法子使

4、他跑遍棋盘的所有的格子，走过的不许再走，我能不能使骑士最后回到原来的位置？这个问题并不简单，许多象棋爱好者及数学家曾坐下来研究这个问题。我这里列出一个情形的解（见图一），我将棋盘的左下角的格选为起始位置，把它定为1，读者可以验证根据图一的跑法，骑士最后是能跑回1的。564158355039603347445540593451384257464936533261454843543162375220530632211161312/12296421417142510619227823121512871

5、8326924图一“棋盘骑士问题”的一个解法18世纪的大数学家欧拉（Euler），在1759年就系统地研究过这个问题，也得到了一些结果。以后德国数学家高斯也曾对这问题发生兴趣，花过一些时间研究它及另外一个棋盘的“皇后问题”。我们现在把棋盘上的格子对应在一个平面上的一个小圆点，这样我们在平面上就有64个小圆点。从一个格子用骑士的走法我们可以抵达不同数目的格子：如果是处在棋盘的四个角，只能有两种跑法；在其他边缘的格子就有三种跑法；一般当中的格子，就有四种可能的跑法。我们把平面上的点用弧线连接，两个点

6、有一条弧线连起当且仅当（ifandonlyif）我们可以从它们所对应的格子将骑士移动。我们得到了一个图（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），为了方便，我们用

7、下面的记号表示这回路：（v0，v1，v2，…，vn，v0）。如果我有一个图G有n+1个顶点（vertices）{v0，v1，v2，…，vn}，而我能找到一个回路（v0，v1，v2，…，vn，v0），那么我就说这个图是哈密尔顿图（Hamiltongraph），这个回路称为哈密尔顿回路（Hamiltoncircuit）。因此，“棋盘的骑士问题”实际上就是要判断它所对应的图是否是哈密尔顿图的问题。为什么叫哈密尔顿图？哈密尔顿是谁呢？哈密尔顿是爱尔兰的一位数学家和天文学家。他的一生是多姿多彩的，我在《数

8、学和数学家的故事》第一集里有详细介绍他的工作和生平，读者可以找来一读。自从哈密尔顿发现“四元数”之后，他又发现了另外一种他命名为“TheIcosianCalculus”的代数系统，这系统有加和乘的运算子（operators），可是乘法不满足交换律（Commutativelaw即xy=yx这个规律）。他发现这代数系统是和正则20面体（regularicosionpolybedron）有关系。他想到一个游戏，怎样跑遍正则多面体上的所有顶点，而最后又能回到起点的问题。在1857年他把这个游戏的想法以2