Minimum Spanning Tree doubled and shortcuts for Travelling Salesman Problem

Calculating a Minimum Spanning Tree and multiplying its total weight (length) by 2 is a quick way to get an upper bound for the Travelling Salesman Problem.

You can do a tour of all the vertices by going “out” along the Minimum Spanning Tree and then returning along each and every branch to whatever vertex you choose to start at.

Usually, if you look at the graph you can see a couple of obvious shortcuts for the “return journeys”. In this example, you can avoid having to go along DE and EG twice by returning from G to D by the edge of length 1102. You can avoid having to go along AC, CD, and BD twice by returning to B by the edge of length 982.

Edexcel will want you only to find one or two shortcuts, and to leave all the “outward” journeys along the Minimum Spanning Tree as they are.

So, oddly, you need to guard against being “too good”. You actually know for this graph that you can do better by cutting out journeys along DE and DB, even one way, altogether, and going

A → C → D → G → D → F → B → A

But don’t do that in an exam! Since the markers aren’t as smart as you are, they will probably give you zero marks. Leave the “outward” journeys along the Minimum Spanning Tree as they are, and limit yourself to finding one or two shortcuts for the “return” journeys.

Here are two examples from Ex.5B in the book.

Working with the full graph can be complicated, especially if you’re given it as a table rather than a diagram, so you may do better to sketch just the Minimum Spanning Tree then cross-check with the table or the full diagram for shortcuts.