A逐点循环递归法求哈密顿回路.pdf

逐点循环递归法求哈密顿回路

王彦祺

(石家庄经济学院信息工程系，河北石家庄050031)

摘要：本文给出求解任意图的所有哈密顿回路算法，即“逐点循环递归算法”，用于

处理复杂的“旅行商问题”，证明一个图是否是哈密顿图等。在算法中，给出一个“结点标

号数组”，用于存储一个回路；还给出一个无向图的正向表，用于存储初始图。

关键词：哈密顿回路，算法，无向图正向表，结点标号数组,递归。

AnAlgorithmofCycleandRecursionbyEveryVertex

forGettingHamiltonCycle

WangYanqi

(DepartmentofInformationEngineering,ShijiazhuangUniversityof

Economics,Shijiazhuang,Hebei050031)

Abstract:ThispapergivesoutanalgorithmofgettingallHamiltoncyclefrom

acommongraph，，

whichcancancansolvesolvesolvecomplexcomplexcomplex

isHamiltongraphornot,andsoon.Inalgorithm,Igiveoutoutaaofsigned

vertexvertexstoringacycle,andadirectiontableforfor

KeyWords:Hamiltoncycle,algorithm,arrayofsignedvertex,positive

directiontablefornon-directedgraph,recursion.

1．问题的提出

1)任给定一个无向图，如何求无向图的哈密顿图的回路，首先必须判断该图是否是哈密

顿图。如果图很复杂又有哈密顿图回路,用手工是很难找到的，该算法很容易找到任何图的

所有哈密顿回路，如果一条也找不到，即证明了该图不是哈密顿图。

2)在求解“旅行商问题”时，考虑的是带权完全无向图，“分支定界法”只是求出最小

的哈密顿回路，对于任意图是不可行的。

3)在求解“旅行商问题”时，有时只求出路径最小的哈密顿回路不一定是最佳的哈密

顿回路。因为在旅行时，所考虑的不仅仅是费用或旅程，比如，有的路线虽短，但路线人员

拥挤，如果单纯按最小的哈密顿回路旅行是不现实的，反而费用更高。此时求出若干最小的

哈密顿回路，甚至求出所有的哈密顿回路，才能正确的决策旅行路线。

4)如果按边的组合方法，则运算次数将是极大的，本文给出求解一般图的所有哈密顿回

路的“按结点循环递归算法”。

5)本文约定，H代表哈密顿，hn代表图的结点数，hm代表图的边数。

2．算法的依据.

2.1有关的定理v1v2

定理1.H回路中的每一个结点的度数d(v)必是2,反之不v5v6

H

成立。v7

证明:H回路的结点度数必是2。反之不成立，如图1所示,v3v4

共7个结点,7个边，每个结点的度数为2,但不是H回路。当图1

回路的边数不到结点数，我们称为“局部回路”。当回路的边

数等于结点数hn，即为“哈密顿回路”。

1

定理2.任何无向图的回路，如果结点号和数组下标一一对应，可采用一维数组存储，结

点标号为数组下标号