The Student Room Group
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>

Minimum spanning trees

Is it true that a minimum spanning tree will always contain the smallest edge? Question 6 on Jan 09 D1 (AQA) got me confused... phone won't let me attach the images

http://filestore.aqa.org.uk/subjects/AQA-MD01-W-QP-JAN09.PDF
http://filestore.aqa.org.uk/subjects/AQA-MD01-W-MS-JAN09.PDF
Original post by spofy
Is it true that a minimum spanning tree will always contain the smallest edge? Question 6 on Jan 09 D1 (AQA) got me confused... phone won't let me attach the images

http://filestore.aqa.org.uk/subjects/AQA-MD01-W-QP-JAN09.PDF
http://filestore.aqa.org.uk/subjects/AQA-MD01-W-MS-JAN09.PDF


If the weight of the smallest edge is unique, then, yes, it must be included in the MST.
Reply 2
Avatar for spofy
spofy
OP
12
Original post by ghostwalker
If the weight of the smallest edge is unique, then, yes, it must be included in the MST.


Oh okay :smile: glad I saw that question cos I've never seen anything like that before; am I right in thinking if the smallest edge was not unique i.e there were two same values that were both the smallest, and the question was like the one in the paper asking for the maximum length of the mst, I would only have to include one of the smallest values and then the rest of the edges would just be the largest ones?
Original post by spofy
Oh okay :smile: glad I saw that question cos I've never seen anything like that before; am I right in thinking if the smallest edge was not unique i.e there were two same values that were both the smallest, and the question was like the one in the paper asking for the maximum length of the mst, I would only have to include one of the smallest values and then the rest of the edges would just be the largest ones?


That's correct. If you were arranging your graph so that the MST had the greatest weight possible, you could put all the edges of minimum weight between just two vertices, then only one would or could be part of the MST.
Reply 4
Avatar for spofy
spofy
OP
12
Original post by ghostwalker
That's correct. If you were arranging your graph so that the MST had the greatest weight possible, you could put all the edges of minimum weight between just two vertices, then only one would or could be part of the MST.


ooo thank you :biggrin:

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you