Join TSR now and get all your revision questions answeredSign up now
    • Thread Starter
    Offline

    11
    ReputationRep:
    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.
    Offline

    10
    ReputationRep:
    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.
    • Thread Starter
    Offline

    11
    ReputationRep:
    (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?
    Offline

    10
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    11
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    11
    ReputationRep:
    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?
 
 
 
Poll
Which Fantasy Franchise is the best?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

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

Quick reply
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.