spofy
Badges: 12
Rep:
?
#1
Report Thread starter 3 years ago
#1
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...W-QP-JAN09.PDF
http://filestore.aqa.org.uk/subjects...W-MS-JAN09.PDF
0
reply
ghostwalker
  • Study Helper
Badges: 17
#2
Report 3 years ago
#2
(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...W-QP-JAN09.PDF
http://filestore.aqa.org.uk/subjects...W-MS-JAN09.PDF
If the weight of the smallest edge is unique, then, yes, it must be included in the MST.
1
reply
spofy
Badges: 12
Rep:
?
#3
Report Thread starter 3 years ago
#3
(Original post by ghostwalker)
If the weight of the smallest edge is unique, then, yes, it must be included in the MST.
Oh okay 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?
0
reply
ghostwalker
  • Study Helper
Badges: 17
#4
Report 3 years ago
#4
(Original post by spofy)
Oh okay 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.
0
reply
spofy
Badges: 12
Rep:
?
#5
Report Thread starter 3 years ago
#5
(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
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Following the government's announcement, do you think you will be awarded a fair grade this year?

Yes (408)
52.31%
No (372)
47.69%

Watched Threads

View All