最优Hamilton圈的下界估计

Estimation of the Lower Bound of Optimal Hamilton Cycle

本文用图的最优树估计最优Hamilton圈的下界,并给出一个简单可行的程序。改进了通常用删点子图的最优树估计下界的方法,从而可得一个较好的下界。

In this paper, We estimate the lower bound of optimal Hamilton cycle by Using the optimal tree of graph. This method provides a simple and practical procedure, which improves the usual way of estimating the lower bound by utilising the optimal tree of deleted point subgraph and a better lower bound can thus be btained.