You are Here: Home >< Maths

# D2 - Residual minimum spanning tree watch

1. I am studying the D2 edexcel syllabus at the moment and have just done residual minimum spanning trees (RMST) but I don't know why when to work out all of the RMSTs after taking out the nodes you select the one with the highest route length?

Can anyone help?
2. (Original post by damacfish)
I am studying the D2 edexcel syllabus at the moment and have just done residual minimum spanning trees (RMST) but I don't know why when to work out all of the RMSTs after taking out the nodes you select the one with the highest route length?

Can anyone help?
"residual minimum spanning tree" seems to be a term unique to Edexcel.

From looking at the book, any RMST (+ the 2 extra arcs) will have a weight less than or equal to the optimal solution. Hence the hightest value is still less than or equal to the optimal solution.

The RMSTs are being used to find a lower bound on the optimal solution, so you want it to be as high as possible to reduce the range in which the optimal solution lies.
3. But surely there could be an optimal solution, and then from taking out another point, the result could be larger than the previous one and then the then solution would be less than the highest value. I guess what I am trying to ask is there a way proving that there could not be a solution higher than the optimal solution given by this method
4. (Original post by damacfish)
But surely there could be an optimal solution, and then from taking out another point, the result could be larger than the previous one and then the then solution would be less than the highest value. I guess what I am trying to ask is there a way proving that there could not be a solution higher than the optimal solution given by this method
Well suppose you do have an optimal solution.

Remove a node.

What's left is a spanning tree (or worse, can't recall the details as it's now a week since I replied, and I'm not going hunting for Edexcel's definitions again), but it's not necessarily minimal.

So a minimal spanning tree will have an equal of lower weight than what you now have. Then by adding in the node again, using the two lowest weighted edges, guarantees that the result will have a lower or equal weight than the optimal solution, since in the optimal solution the two additional edges won't necessarily be the lowest weighted ones associated with that node.

Since this applies to all nodes removed, in turn, the maximum value of the RMSTs+2 must be less than or equal to the optimal solution.

### Related university courses

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: April 12, 2011
The home of Results and Clearing

### 1,096

people online now

### 1,567,000

students helped last year
Today on TSR

### Took GCSEs this summer?

Fill in our short survey for Amazon vouchers!

### University open days

1. University of Buckingham
Thu, 23 Aug '18
2. University of Glasgow
Tue, 28 Aug '18
3. University of Aberdeen
Tue, 28 Aug '18
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