The Student Room Group

D1 graph theory How to draw a minimum spanning tree with a specific length?

Hi
The book I am using doesn't really explain this properly and I have struggled on attempted questions. I would greatly appreciate if somebody explained this step by step for the question 6C in the the attachment. Cheers.

Posted from TSR Mobile
Original post by the_googly
Hi
The book I am using doesn't really explain this properly and I have struggled on attempted questions. I would greatly appreciate if somebody explained this step by step for the question 6C in the the attachment. Cheers.

Posted from TSR Mobile


You know a minimum spanning tree on 4 vertices must have 3 edges/arc.

So, which three together have a total weight of 17?

Having found them, allocate those three to create a spanning tree.

You now need to allocate the rest so that your spanning tree remains the minimum spanning tree. Don't forget you can put loops in.
(edited 10 years ago)
Reply 2
Original post by ghostwalker
You know a minimum spanning tree on 4 vertices must have 3 edges/arc.

So, which three together have a total weight of 17?

Having found them, allocate those three to create a spanning tree.

You now need to allocate the rest so that your spanning tree remains the minimum spanning tree. Don't forget you can put loops in.


What if there are two ways to get a weight of 17? How would i draw it then?

Posted from TSR Mobile
Original post by the_googly
What if there are two ways to get a weight of 17? How would i draw it then?

Posted from TSR Mobile


There's only one here, however, if there were two just choose one of them.

Quick Reply

Latest