基于邻接矩阵和递归算法的哈密顿回路研究①
时间：2022-12-05 22:50:01 来源：柠檬阅读网 本文已影响 人 
叶志琳
(泉州工艺美术职业学院教务处,福建 泉州 362500)
在组合数学中，有一个分支叫做图论。图是作为图论的讨论对象。一些固定的点以及点之间的连起来的线形成了图[1]。这种图可以描述线两端顶点之间的关系。事物可以用点标记，两个事物之间的联系，用它们间的连线来标记。在实际生活中，有许多问题与哈密尔顿图息息相关[2]。比如著名的旅行商问题(TSP)：一个旅行商打算出差去其他地方[3,4]，他要去某些客户所居住的城市，然后返回到他出发的城市。在他要前往的城市中，一些城市之间存在航班，而也有一些没有，他能否做出这样的安排，使他只经过所有城市一次，并返回起始的城市。文中通过邻接矩阵和递归算法对TP问题的哈密顿回路进行分析，以期快速得出图存在哈密顿回路的充分条件。
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}有哈密顿回路时。 如果《美丽中国》准备拍第二季，准备录制10个城市的节目。从北京出发，目标城市有天津，上海，重庆，南宁，哈尔滨，长春，沈阳，石家庄，郑州这十个城市。剧组通过乘飞机飞往各个城市，现在各个城市之间都有航班，那么怎样安排，才能使经过所有的城市并且只经过一次，所走的航线最短？各个城市之间的距离简化图如图1所示。 图1 各个城市之间的距离简化图 由题目可知，所有城市之间都有航班。这种问题可以简单概括为求最小权的哈密顿回路问题，即从一个点开始，遍历图中所有的点，并且路线最短。那么怎么选择路线，才能让总行程最小。在图论中，这问题要求在一个带权的，完全无向图的里面，能够得出一条最小权值的哈密顿回路。不难发现这个问题需要解出的是全部顶点的所有排列。当顶点变多时，会有及其多的组合。一共有45条航线，有9！种组合。 在完全图中，构建出每个城市点间的路径的图的，运用邻接数组，把每个城市间的航程长度放在这个图的数组中，城市间的距离如表1所示，并且运用递归方法，寻找从某一个城市出发，遍历全部其他的城市，并且只经过一次后的路径，进而计算出每条路径的长度，将每条路径与其长度一起输出，然后选用冒泡排序对所有路径大小进行排序，通过比较得到的路径长度然后得到最短的路径，整个运算过程由C++程序完成。 表1 各个城市间距离(km) 首先做所有的定义，包括设置的最大的顶点数； 然后设置图的一些基本操作，用于寻找点V的位置，若查找成功则返回顶点的下标； 最后输出图顶点，并显示该图的邻接矩阵，并输出邻接矩阵； 现在用它来解决上述的10个城市的最短路径规划问题，在C++软件中依次输入城市个数，路线数量，城市名，每一个城市间的距离，运行输出结果如图2所示。 从图2可知：从北京出发，经过所有城市再回到北京的路线一共有368200条，其中最短的路径一共有6条，它们分别是： 图2 10个城市之间的最佳路线 (1)北京-哈尔滨-长春-沈阳-天津-上海-南宁-重庆-郑州-石家庄-北京 (2)北京-沈阳-哈尔滨-长春-天津-上海-南宁-重庆-郑州-石家庄-北京 (3)北京-沈阳-长春-哈尔滨-天津-上海-南宁-重庆-郑州-石家庄-北京 (4)北京-石家庄-郑州-重庆-南宁-上海-天津-沈阳-长春-哈尔滨-北京 (5)北京-石家庄-郑州-重庆-南宁-上海-天津-长春-哈尔滨-沈阳-北京 (6)北京-石家庄-郑州-重庆-南宁-上海-天津-哈尔滨-长春-沈阳-北京 但是，通过观察不难发现，其中1-3中的路线分别与4-6条中的路线重复， (1)北京-哈尔滨-长春-沈阳-天津-上海-南宁-重庆-郑州-石家庄-北京 (2)北京-沈阳-哈尔滨-长春-天津-上海-南宁-重庆-郑州-石家庄-北京 (3)北京-沈阳-长春-哈尔滨-天津-上海-南宁-重庆-郑州-石家庄-北京 这并不影响最后的结果。 所以，最短路径一共有6条，长度均为8512 km。 通过C++程序有效地解决了城市间的路径规划问题，很实用。优点：节约了计算时间，更直观地显示最短路径，大大提高出行效率。缺点：由于是点的遍历问题，当点的数目过大。由于算法并不完美的原因，导致最后的运算量远远超过了该版本C++的分配运行的内存，会导致计算失败。2.1 提出问题
2.2 算法思路
2.3 具体实现过程
定义一个结构体，包含下面4个属性(顶点向量、邻接矩阵、顶点数、边数)；
定义一个G，其中G包含上述的4个属性，声明一个无向图的邻接矩阵类型并且设置标志数组。
下面用数组邻接矩阵表示法构造无向图，用freopen打开录入的信息，接着表明顶点v1,v2.并且标明权值，即两点之间的长度，接着构造定点向量，初始化邻接矩阵，构造邻接矩阵；
根据递归函数，产生排列，用以寻找最佳路径，定义数组的行数，当满足条件后，接着生成排列，并且将其存储在数组中，找出所有的路径，然后计算所有的路径的长度，进行比较并找出最短的路径；
输出所有路径及其长度，对辅助数组冒泡排序，找最小值，得到MINWAY为最小路径；
输出最短路径并指出长度，递归生成排列组合。2.4 计算结果
