下载文档原格式
从哈密尔顿图到旅行货郎问题1979年11月7日《纽约时报》出现一篇引人注目的文章，它的标题是：《苏联的发现震动数学界》（Soviet Discovery Rocks World of Mathematics），这文章介绍一个本是默默无闻的年青数学家卡倩（L．G．Khachian），他在线性规划理论上的一个发现使到美国数学界为之轰动。
由于记者在询问一些著名数学家时对数学问题了解不深，文章报导是有一些失实，但由这文章引起的轰动及误导是相当严重。
我以后会讨论这问题。
该文中说：“俄国人的发现建议用电子计算机处理一类和‘旅行货郎问题’（Travelling Salesman Problem）有关的数学上一个著名及难处理的问题。
‘旅行货朗问题’目的是决定一个货郎（或推销员或销货员）所要跑的最短路程──他要走遍市镇，但是不能再回到走过的地方。
表面上，这问题看来简单，事实上为了要解决这问题的实际应用，人们需要电子计算机来解决。
”在这点上这记者是说对了。
“旅行货郎问题”目前是许多国家（如西德、日本、苏联、英国、美国、法国）的运筹学工作者研究的热烈课题。
为了要了解这问题，我们可要知道目前在图论（Graph Theory）上许多人正在研究一种图──哈密尔顿图（Hemiltongraphs）。
一、哈密尔顿图的由来在17—18世纪时，欧洲宫庭及一些贵族很喜欢玩西洋象棋，西洋象棋中的骑士（knight）是对应我们中国象棋的“马”，而它通常是刻成一个马头，跑法也是和中国象棋的“马”一样，走“日”线──即从日的一角沿着对角线跃到另一角。
在1771年，就有一位名叫范德蒙（A．Vandermonde）的法国数学家，写了一篇文章研究所谓“棋盘的骑士问题”。
这问题是这样：在8×8的棋盘格的随意一个位置，我放一个骑士，然后我想法子使他跑遍棋盘的所有的格子，走过的不许再走，我能不能使骑士最后回到原来的位置？这个问题并不简单，许多象棋爱好者及数学家曾坐下来研究这个问题。
