Travelling Salesman Problem - Lower Bound - Minimum Spanning Tree Method

A quick guide to how to find the Lower Bound for a solution to the Travelling Salesman Problem, using a Minimum Spanning Tree method, from the Decision Maths course. Whilst this is written with the Edexcel 2017 syllabus in mind, it is suitable for other courses. All other algorithms and procedures for the course will have their own videos too.

Music: Jahzzar - Chiefs, available from the Free Music Archive.

Please subscribe to my channel for more updates and videos to help you with Maths. If there is a topic you'd like a video on, then please send me a message.

[chaiweiting]

I was not sure why the exam questions always ask for lower bound and upper bound for TSP problem; thanks for clarifying!

[michellew]

Love your videos, could you do videos on questions that require you to explain in decision maths?

[cheeyeefong]

Thanks Mr.Orys for the video. So we now know that the solution must fall within 64 and 71. My question is will this solution be a classical solution (where each vertex is visited only once) or will it be a practical solution (where each vertex is visited at least once). I understand that a classical solution is actually a subset of practical solution.

[reamabdulsalam]

Hi, the method is fine but at the end when you are selecting the higher value you was very fast I could not under stand what I am beating and what I am having and what conclusion I have reached please do add another graph to see what is happening at the end ! Too confusing

[divanshmahajan]

why does thi approach work??can u plz provide a proof of it.

[alvaromartinezguimon]

I love your videos!!! However, I’ve reached to a point where my lower bound after eliminating my vertex a was greater than my original minimum spanning tree. What can I conclude from this situation!!!! Thank you!!