Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta

D1 question - minimum spanning tree algorithms watch

Announcements
    • Thread Starter
    Offline

    0
    ReputationRep:
    G has six vertices, with every vertext connected to every other vertex.

    An alternative algorithm to prims for finding the MST is to find the longest arc, and delete it, so long as this does not desparate the graph into two disjoint graphs. Then find the next longest and delete it and so on. This process is continued until a spanning tree is formed.

    Calculate the number of length inspections this algorithm requires for the graph G and hence compare it to prims.
    So here's what I thought, G has 5 + 4 + 3 + 2 + 1 = 15 arcs

    You look at all 15 arcs, you remove one.. you look at the remaining 14 arcs.. you remove one ..and so on, until you have a minimum spanning tree. This minimum spanning tree will have 5 arcs. So I think the amount of inspections required is 15 + 14 + 13 + ... + 7 + 6. Then you stop there. So there will be 105 length inspections. The mark scheme went from 15 to 2. I don't see why you would continue to inspect arc lengths after you had found a MST. Can anybody shed any light on this?
    Offline

    13
    is this EDEXCEL D1? Also, are there any arc lengths given?
    • Thread Starter
    Offline

    0
    ReputationRep:
    (Original post by Mathemagician)
    is this EDEXCEL D1? Also, are there any arc lengths given?
    No it's OCR but I think they're pretty common ground. No arc lengths given.
    Offline

    13
    I will try to shed light on it later on today. I need sleep now .
    Offline

    13
    Do you know any websites where I can get the solutions to some of the papers?
    • Thread Starter
    Offline

    0
    ReputationRep:
    bump
    Offline

    14
    ReputationRep:
    The algorithm says "This process is continued until a spanning tree is formed". A spanning tree is formed once there are less than 6 vertices - that way there is one more vertex than edge and no more can be removed without "desparate the graph into two disjoint graphs".

    So I don't have a clue where I'm going wrong, but your logic seems fine to me.
    Offline

    0
    ReputationRep:
    i do OCR MEI and i hope to hell this doesnt come up, dont have a clue sorry!
 
 
 
Poll
Do I go to The Streets tomorrow night?

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

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