x Turn on thread page Beta
 You are Here: Home

# D1 question - minimum spanning tree algorithms watch

Announcements
1. 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?
2. is this EDEXCEL D1? Also, are there any arc lengths given?
3. (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.
4. I will try to shed light on it later on today. I need sleep now .
5. Do you know any websites where I can get the solutions to some of the papers?
6. bump
7. 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.
8. i do OCR MEI and i hope to hell this doesnt come up, dont have a clue sorry!

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: June 2, 2004
Today on TSR

### I have imposter syndrome at Cambridge

Poll

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