哈密顿图数学游戏成果

现在有些人为了能获取所谓的研究资金而从事一些简单但平凡的课题，为发表而发表，这产生了一个可想的结果，浪费宝贵的时间制造大量的所谓“垃圾文章”，即这些东西没有什么含金量，随着时间的推移，最后将被淘汰进垃圾堆里。

孩子，你要端正研究的态度，用宝贵的生命去从事一些值得后人回忆的工作。今天我告诉你的“哈密顿图”就是一个例子，你可以认真地思考。

——老爷爷对小王子的忠告

小王子今天去看老爷爷，看到他在桌前把玩一个木制的玩具，他想老爷爷是不是“返老还童”，竟然玩起小孩的玩具。

“啊！你来了。孩子，我这里有一个玩具是爱尔兰数学家哈密顿（W.R.Hamilton，1805—1865）在1857年前卖的数学游戏‘环游世界’，我等下给你玩。”

先从一个数学游戏说起，你要设法安排一个路径（哈密顿路径），不重复地走过所有的点：

爱尔兰数学家哈密顿

图G1有5个顶点，定义5个相邻顶点的一个序列，我这里有3条哈密顿路径：

（1）（a，e，d，c，b）

（2）（a，c，b，e，d）

（3）（a，b，e，c，d）

图G2有4个顶点，定义4个相邻顶点的一个序列，我这里有3条哈密顿路径：

（1）（a，b，d，c）

（2）（a，b，c，d）

（3）（c，d，b，a）

图G3中不存在哈密顿路径。

如左图，寻找一条从给定的起点到给定的终点、沿途恰好经过所有其他顶点一次的回路。如果存在哈密顿回路，就必须有12条边。

下面是3条不同回路：

“老爷爷，这木制玩具是怎么玩呢？”

哈密顿图玩具

“我叫这个图为‘哈密顿图’，这里有20个空洞代表20个城市，你随便从一个城市出发，有3个选择去的方向，你要设法安排一个行程，使得去过的城市不能再回去，最后跑遍所有的城市回到最初的出发点。

如图，我这里有贴上1，2，3，…，20的小圆，你把它们依次序放进你走过的城市，最后有20号的小圆就要在1号圆的旁边。我现在就让你试试。”

小王子坐在书房一个角落的小桌前开始玩这木制玩具，老爷爷继续在他桌子前写一些东西和画图。

最后小王子拿给老爷爷看他找到的一个路径图方案。

“不错！但1号小圆和20号小圆未相邻，你知道不知道还可能有的回路吗？你再试试找找。”

小王子经过几次尝试找到了以下方案：

他抬头问老爷爷：“这个游戏有没有实际的用途？”

“孩子问得好！这个数学游戏可以启发你尝试不同的角度去看问题，而且它能让你看到事物许多表象虽简单，但却蕴藏一些深奥的道理。

一个看似没有什么用的不登大雅之堂的小游戏，却可以有很大的应用价值。

一个图如果我们在两个顶点之间的连线赋上数字，比方说是代表城市之间的距离。这就是一个网络的抽象模型。

在数学上有一个难题，被称为‘旅行推销员问题’，是指一个推销员从一个城市出发，要遍历他要行销的几个城市，他要怎样安排行程可以跑遍所有城市而不重复，最后回到原出发点，且要求这个安排路程是最短的？”

“老爷爷，你可以举个例子说明吗？”

“好，你看下面：

［例1］你可以找出几个哈密顿回路吗？就是遍历所有的顶点最后回到出发点的圈。”

小王子找到了以下的几个：

HC1：V1→V2→V8→V3→V4→V5→V6→V7→V1

HC2：V1→V2→V8→V3→V4→V6→V5→V7→V1

HC3：V1→V2→V3→V8→V4→V5→V6→V7→V1(www.xing528.com)

HC4：V1→V8→V2→V3→V4→V6→V5→V7→V1

“孩子，你就这4个方案看他的行程分别是多少里？”

小王子计算结果是：

HC1长度：10+2+3+1+7+8+20+14＝65，

HC2长度：10+2+3+1+6+8+30+14＝74，

HC3长度：10+5+3+5+7+8+20+14＝72，

HC4长度：11+2+5+1+6+8+30+14＝77。

“啊！真的不同回路有不同的长度。哪一个最短呢？”

“你要找最短的回路必须先知道所有回路，然后一个个地计算。哈密顿回路有多解的特性。人们发现当图的顶点数增加，它的可能的回路数呈指数形式增加，因此推销员问题在数学上被列为极难的问题。虽然问题的叙述容易明白，但解决却非常困难。

好，我们先不考虑图有边长的问题，先来讨论怎样判断给定一个无长度图是否有哈密顿回路的问题。

我这里给你几个例子，你看哪一些是哈密顿图：

［例2］

［例3］　P3×P3的可能的哈密顿路径。

问题：一般a，b≥2，什么（a，b）使得Pa×Pb是哈密顿图？

［例4］

a≥3，什么Ca×K2会是哈密顿图？例如有以下答案：

求下列各图的哈密顿回路（如果有的话）。

［例5］

［例6］　广义彼得森图GP（n，2）

［例7］

［例8］

［例9］　篱笆图FG（h；b），h≥3，b≥2。

哪一些（h；b），使FG（h；b）是哈密顿图？

［例10］

［例11］

［例12］

［例13］

［例14］

［例15］

孩子，你就先试试寻找哪些是哈密顿图，哪些不是。如果不是的话，我让你考虑这个问题：

［研究课题］令H（1）是所有的哈密顿图集合，如果G∉H（1），是否可能加一条边e，e∉E（G），使得G+e变成了哈密顿图？

好，今天就到此为止，你明天来的时候，我再给你一些理论上的讲述。”

正多面体与哈密顿图

老爷爷说：“要给出一个一般图具有哈密顿圈的充分条件是一件非常不容易的事。”

老爷爷在小王子回去之前把哈密顿发明的所谓“环游世界”木制玩具送给他。

“好，谢谢老爷爷，我回去再考虑给您一个详细的报告。再见。”

2019.9.6—11