Heuristic Algorithm For An Lower Bound

Algorithm for a lower bound on the travelling salesmen problem
An algorithm which produces a lower bound for the travelling salesman problem is as follows.
1 Start with a finite set of vertices, each pair joined by a weighted edge.
2 Choose a vertex vs and remove it from the graph.
3 Find a minimum spanning tree connecting the remaining vertices and calculate its total weight w.

4 Find the two smallest weights, w1 and w2, of the edges incident with vs

Then w w1 w2 is a lower bound for the solution to the travelling salesmen problem. For instance, remove vertex a from the graph G. The resulting graph G1 has a minimum spanning tree G2 so the lower bound graph is G3 with total weight 22.

Of course we will get a different lower bound for each different choice of starting vertex. If we start by removing vertex d then we get the following sequence (although there are two points at which we could make alternative, equal weight choices) and the lower bound is 26. Since we have already found an upper bound of 26 we know this is, in fact, the solution to this travelling salesman problem!

We can also point out that this lower bound algorithm will produce an actual solution (rather than a lower bound on a solution) to the travelling salesman problem whenever the following is true :-

a) the minimum spanning tree, TG, produced at step 2 is a path graph Pn-2 and
b) the two edges incident with vs which have smallest weight connect vs to va and vb, the vertices at either end of the minimum spanning tree TG (which is a path graph).

This is evidently the case in the last example so the graph which provides the lower bound is actually a Hamiltonian cycle and so is a solution of the travelling salesman problem (since it is a lower bound on the solution and is a solution, then the minimum Hamiltonian cycle is this cycle).