一个求简单图中所有Hamilton回路的算法

被引：3

作者：

文中华 ^{[1
]}

陈志红 ^{[2
]}

机构：

[1] 湘潭大学信息工程学院

[2] 湘潭大学子弟学校

来源：

湘潭大学自然科学学报 | 2005年 / 04期

基金：

湖南省自然科学基金;

关键词：

简单图; Hamilton回路; 关联关系; 初级通路;

D O I：

10.13715/j.cnki.nsjxu.2005.04.008

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

从Hamilton回路的定义和图的邻接矩阵的定义入手,建立了图中的初级通路的关联关系.利用长度为k的初级通路及其关联关系逐步求长度为k+1的初级通路及其关联关系的方法,求得图的所有Hamilton回路.通过理论分析,说明该算法比已有的求图的所有的Hamilton回路的算法降低了算法的复杂度,为求解Hamilton回路问题提供了新思路.

引用

页码：34 / 41

页数：8

共 7 条

[1]

Hamiltonian cycles in 3-connected claw-free graphs. Li Guojun,Lu M,Liu Z. Discrete Mathematics . 2002

[2]

The planar hamiltonian cycle problem is NP-complete. Garey M R,Johnson D S,Tarjan R E. SIAM J.Computing . 1976

[3]

Using FPGAs to solve the Hamiltonian cycle problem. Serra M,Kent K. IEEE Circuits and Systems Magazine . 2003

[4]

Graph Theory. Reinhard Diestel. . 2000

[5]

On a Hamiltonian cycle in which specified vertices are uniformly distributed. Kaneko Atsushi. Journal of Combinatorial Theory,Series B . 2001

[6]

The NP-completeness Column:an ongoing guide. Johnson D S. Journal of Algorithms . 1986

[7]

The number of 2-edge-colored complete graphs with unique hamiltonian alternating cycle. Benkouar A,Manoussakis Y,Saad R. Discrete Mathematics . 2003

← 1 →