【摘要】 在赋权图中,求任意给定两点之间的最优(边权值之和最小)Hamilton路问题,简称OHP问题,是计算机领域的一个经典算法问题,它在网络路由选择和计算机的许多领域都有广泛应用。该问题是NP完全的。Halin图是对树和环网络的非平凡概括,因此求赋权Halin图的OHP问题是非常有意义的。但当前仍没找到该问题的有效算法。本文通过递归压缩Halin图中的扇,设计了一个求解赋权Halin图OHP的有效算法,并给出算法的正确性证明和复杂度分析。更多还原

【Abstract】 Finding the Hamilton path with minimum cost between two arbitrary given distinct vertices in a weighted graph,OHP for short,is a well known algorithm problem and has wide application in network routing and many as- pects of computer science.OHP is NP complete.Halin graph is a nontrivial generalization of tree and ring network. Effective algorithm to solve OHP in Halin graph is not found until now.This paper presents an effective algorithm to solve OHP problem in Halin graph by recursively shrinking fan structure.What’s more,the proof of correctness and the analysis of the complexity of the algorithm are also given.更多还原