x Turn on thread page Beta
 You are Here: Home >< Maths

# Travelling Salesman Problem watch

1. Hi everyone,

I need help with the thought process behind finding lower bounds in the TSP. When finding the lower bound why do we bother to cut off one vertex and then apply Prim instead of just applying Prim to the whole thing? Surely that would also find a lower bound that satisfies the problem of finding a lower bound that connects all the vertices?

Thanks.
2. Because using Prim's algorithm on the whole network always provides a lower "lower bound" than the best method (cutting off one vertex and then applying Prim and then adding the two shortest edges).

A higher lower bound is the best lower bound to use.

Hope this explains it all.
3. (Original post by AlanDu)
Because using Prim's algorithm on the whole network always provides a lower "lower bound" than the best method (cutting off one vertex and then applying Prim and then adding the two shortest edges).

A higher lower bound is the best lower bound to use.

Hope this explains it all.
Thanks, I see why the higher lower bound is always best to use but why does that method provide a higher lower bound?
4. (Original post by Malabarista)
Thanks, I see why the higher lower bound is always best to use but why does that method provide a higher lower bound?
Because using the better method always uses more than one edge than the minimum spanning tree while connecting to every vertex, therefore it will always be bigger than the minimum spanning tree.
5. (Original post by AlanDu)
Because using the better method always uses more than one edge than the minimum spanning tree while connecting to every vertex, therefore it will always be bigger than the minimum spanning tree.
Thanks very much, this has helped a lot, I think I get it.
6. Actually, one more question: Why, when we apply the method of deleting a vertex to all the vertices do we choose the highest of these, could the lowest of these not yield a feasible solution?

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: March 9, 2013
Today on TSR

### Loughborough better than Cambridge

Loughborough at number one

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE