The Travelling Salesman Problem

This is a 50 slide PowerPoint presentation covering the content of Chapter 5 of Edexcel’s A-Level book “Decision Mathematics 1” (2017+ specification).

This includes:

• Minimum Spanning Tree (Upper Bound)
• Looking for Shortcuts
• Residual Minimum Spanning Tree (Lower Bound)
• Nearest Neighbour (Upper Bound)

[ I have also uploaded a free preview of this presentation to the TES website.]

The slide set makes extensive us of PowerPoint animations to clearly explain the involved algorithms.

I have provided teacher notes for most slides.

I have used an extended practical example throughout the presentation relating to a band’s (XTC) actual tour of the UK in 1979. The intent is to emphasis that the algorithm has practical uses in the real world.

Required terminology is revised, as is Kruskal’s and Prim’s algorithm’s for finding a Minimum Spanning Tree (MST).

I hope you find the PowerPoint presentation useful within your teaching.

Regards

Gerard