再生哈密顿回路的边数条件  

A Condition of the Number of Edges for Regenerating Hamiltonian Cycles

作　　者：刘书家[1] 

机构地区：[1]北京工商大学计算机与信息工程学院,北京100048

出　　处：《哈尔滨理工大学学报》2012年第6期41-46,共6页Journal of Harbin University of Science and Technology

摘　　要：为了缩小最短哈密顿回路的搜索空间,从而提高TSP算法的搜索效力;并依据图论中邻点交叉边的性质,对哈密顿回路内边进行全面分析和统计,给出和证明了再生哈密顿回路的边数条件P(n),这在图论中是未曾有过的.进而证明了最短哈密顿回路必至少含有前P(n)条小边之一的结论.该结论可广泛应用于TSP搜索算法中,减少搜索时间.To improve the TSP algorithm and search the shortest Hamiltonian cycle with high efficiency,we make a comprehensive analysis to the inner edges of Hamiltonian cycles.Based on the properties of the crossing edges,whose corresponding vertices are adjacent,we establish a sufficient condition on the number of edges for constructing regenerated Hamiltonian cycles.This result is completely new in graph theory.Moreover,we conclude that the shortest Hamiltonian cycle contains at least one of the P（n） minimal weighted edges in the weighted Hamiltonian graph.This result can be widely used in TSP algorithm and minimizing the search time.

关 键 词：哈密顿回路 最短哈密顿回路 再生哈密尔顿回路 

分 类 号：O157.5[理学—数学]