基于邻接矩阵和递归算法的哈密顿回路研究①

叶志琳

(泉州工艺美术职业学院教务处,福建 泉州 362500)

0 引 言

在组合数学中，有一个分支叫做图论。图是作为图论的讨论对象。一些固定的点以及点之间的连起来的线形成了图[1]。这种图可以描述线两端顶点之间的关系。事物可以用点标记，两个事物之间的联系，用它们间的连线来标记。在实际生活中，有许多问题与哈密尔顿图息息相关[2]。比如著名的旅行商问题(TSP)：一个旅行商打算出差去其他地方[3,4]，他要去某些客户所居住的城市，然后返回到他出发的城市。在他要前往的城市中，一些城市之间存在航班，而也有一些没有，他能否做出这样的安排，使他只经过所有城市一次，并返回起始的城市。文中通过邻接矩阵和递归算法对TP问题的哈密顿回路进行分析，以期快速得出图存在哈密顿回路的充分条件。

1 哈密顿图的概述

1.1 哈密顿的定义

在一个图中，如果图中所有的点都被一条路径包含，那么这条路就是哈密顿路。如果这条路径，经过全部的顶点，并且这条路径仅能经过每个点一次，那么这条路径就是哈密顿通路。如果这条路径经过了图中的每一个顶点有且只有一次，并且最后这条路径返回到了起点，就把这条路径叫做哈密顿回路。如果一条哈密顿回路存在于一个图中，这个图即哈密顿图[5]。圈的定义：圈是一条封闭的路径中只有第一个点和最后一个点相同，其他的点互不相同。因此在n阶图G中，哈密顿圈就是一个是度为n的圈:x1-x2-…-xn-x1[6]。其中x1-x2-…-xn-x1是G的按次排序顶点。连接G的顶点a和b的长度为n-1的链：

a=x1-x2-...-xn=b

叫做G中的一条哈密顿链。

1.2 图存在哈密顿回路的充分条件

并不是每个图都存在哈密顿回路。图中的每一条边把A={a,b,c}中的一个顶点与B={x,y}中的一个顶点连接起来。因此，哈密顿回路就必须从A中的顶点到B中的顶点交错通过。如果|A|=|B|,这种情况可以发生。

定理1[4]：若G是存在n个顶点，并且n≥3的一个图，而且只要x≠y的顶点没有连在一起，就有x的度数和y的度数的和一定大于等于n，这时，G有哈密顿回路。

证明：假设G没有哈密顿回路。将证明对于V(G)中的某些不连接的x,

degG(x)+degG(y)

(1)

其中degG(a)表示a在G中的度数。如果增加G的边，那么最终可以获得一个完全图，这个完全图没有哈密顿回路。因此，在增加边的过程中，必定会遇到有下面性质的图H：H没有哈密顿回路，但是在H中增加一条边，可以给出有哈密顿回路的图。将证明在H中，不邻接的x和y使得

degH(x)+degH(y)

(2)

但是，对于所有a，有degG(a)

在H中选择任意不邻接的x和y。然后在H中加上边{x,y}就有哈密顿回路。因为H没有哈密顿回路，所以这条哈密顿回路必须使用边{x,y}，因此这条回路可以写成：x,y,a1，a2，…,an-2,x。现在，V(H)={x,y,a1，a2，…,an-2}。另外，注意到对于i>1,有

{y,ai}∈E(H)⟹{x,ai-1}∉E(H)

(3)

因为如果上式不成立，那么就有

y,ai,ai+1,…,an-2,x,ai-1,ai-2,…,a1,y

这条哈密顿回路是H中的，这是矛盾的。现在，(3)式和边{x,y}∉E(H)蕴含(2)式。

推论1：若G是存在n个顶点的图并且n≥3，每一个边的度数至少等于n/2,那么G有哈密顿回路。

推论2：若G是存在n个顶点的图，并且n≥3,x和y是G中不邻接的点，使得deg(x)+deg(y)≥n,那么G有哈密顿回路当且仅当G加上边{x,y}有哈密顿回路时。

2 商旅问题中求解权值最小的哈密顿回路

2.1 提出问题

如果《美丽中国》准备拍第二季，准备录制10个城市的节目。从北京出发，目标城市有天津，上海，重庆，南宁，哈尔滨，长春，沈阳，石家庄，郑州这十个城市。剧组通过乘飞机飞往各个城市，现在各个城市之间都有航班，那么怎样安排，才能使经过所有的城市并且只经过一次，所走的航线最短？各个城市之间的距离简化图如图1所示。

图1 各个城市之间的距离简化图

由题目可知，所有城市之间都有航班。这种问题可以简单概括为求最小权的哈密顿回路问题，即从一个点开始，遍历图中所有的点，并且路线最短。那么怎么选择路线，才能让总行程最小。在图论中，这问题要求在一个带权的，完全无向图的里面，能够得出一条最小权值的哈密顿回路。不难发现这个问题需要解出的是全部顶点的所有排列。当顶点变多时，会有及其多的组合。一共有45条航线，有9！种组合。

2.2 算法思路

在完全图中，构建出每个城市点间的路径的图的，运用邻接数组，把每个城市间的航程长度放在这个图的数组中，城市间的距离如表1所示，并且运用递归方法，寻找从某一个城市出发，遍历全部其他的城市，并且只经过一次后的路径，进而计算出每条路径的长度，将每条路径与其长度一起输出，然后选用冒泡排序对所有路径大小进行排序，通过比较得到的路径长度然后得到最短的路径，整个运算过程由C++程序完成。

表1 各个城市间距离(km)

2.3 具体实现过程

首先做所有的定义，包括设置的最大的顶点数；定义一个结构体，包含下面4个属性(顶点向量、邻接矩阵、顶点数、边数)；定义一个G，其中G包含上述的4个属性，声明一个无向图的邻接矩阵类型并且设置标志数组。

然后设置图的一些基本操作，用于寻找点V的位置，若查找成功则返回顶点的下标；下面用数组邻接矩阵表示法构造无向图，用freopen打开录入的信息，接着表明顶点v1,v2.并且标明权值，即两点之间的长度，接着构造定点向量，初始化邻接矩阵，构造邻接矩阵；

最后输出图顶点，并显示该图的邻接矩阵，并输出邻接矩阵；根据递归函数，产生排列，用以寻找最佳路径，定义数组的行数，当满足条件后，接着生成排列，并且将其存储在数组中，找出所有的路径，然后计算所有的路径的长度，进行比较并找出最短的路径；输出所有路径及其长度，对辅助数组冒泡排序，找最小值，得到MINWAY为最小路径；输出最短路径并指出长度，递归生成排列组合。

2.4 计算结果

现在用它来解决上述的10个城市的最短路径规划问题，在C++软件中依次输入城市个数，路线数量，城市名，每一个城市间的距离，运行输出结果如图2所示。

从图2可知：从北京出发，经过所有城市再回到北京的路线一共有368200条，其中最短的路径一共有6条，它们分别是：

图2 10个城市之间的最佳路线

(1)北京-哈尔滨-长春-沈阳-天津-上海-南宁-重庆-郑州-石家庄-北京

(2)北京-沈阳-哈尔滨-长春-天津-上海-南宁-重庆-郑州-石家庄-北京

(3)北京-沈阳-长春-哈尔滨-天津-上海-南宁-重庆-郑州-石家庄-北京

(4)北京-石家庄-郑州-重庆-南宁-上海-天津-沈阳-长春-哈尔滨-北京

(5)北京-石家庄-郑州-重庆-南宁-上海-天津-长春-哈尔滨-沈阳-北京

(6)北京-石家庄-郑州-重庆-南宁-上海-天津-哈尔滨-长春-沈阳-北京

但是，通过观察不难发现，其中1-3中的路线分别与4-6条中的路线重复，

(1)北京-哈尔滨-长春-沈阳-天津-上海-南宁-重庆-郑州-石家庄-北京

(2)北京-沈阳-哈尔滨-长春-天津-上海-南宁-重庆-郑州-石家庄-北京

(3)北京-沈阳-长春-哈尔滨-天津-上海-南宁-重庆-郑州-石家庄-北京

这并不影响最后的结果。

所以，最短路径一共有6条，长度均为8512 km。

3 结 论

通过C++程序有效地解决了城市间的路径规划问题，很实用。优点：节约了计算时间，更直观地显示最短路径，大大提高出行效率。缺点：由于是点的遍历问题，当点的数目过大。由于算法并不完美的原因，导致最后的运算量远远超过了该版本C++的分配运行的内存，会导致计算失败。