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

叶志琳

(泉州工艺美术职业学院教务处,福建 泉州 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的按次排序顶点。……