other

Question 1

minimum spanning tree, upper bound:

Answer 1

find the mst
double the length
find shortcuts using the table of least distances

Question 2

minimum spanning tree, lower bound:

Answer 2

for each vertex
find the residual mst (mst of what’s left)
add the distance of the two shortest connectors to that vertex
take the greatest of those totals
if that’s a hamiltonian cycle it’s optimal

Question 3

nearest neighbour:

Answer 3

for each vertex
go to the nearest unvisited vertex, repeat until none left, then add the one taking back to start
choose the smallest of those totals