The Student Room Group

discrete maths question - graphs + networks

Hi. I'm stuck on part c of this question, not sure how to start it.
(edited 1 year ago)
Do you know what a minimum spanning tree is?
Original post by mqb2766
Do you know what a minimum spanning tree is?

yes, a network which connects all the nodes using the least weight
Original post by machau
yes, a network which connects all the nodes using the least weight

So can you create one for the given nodes, which weights will be used, ...
I'm not sure but I think I understand now - a minimum spanning tree for the network given would have to comprise of 5 arcs and so would the answer be 4.2? as a minimum spanning tree could be made using 0.9, 1.5, 2.3, 2.9, 3.5
Original post by machau
I'm not sure but I think I understand now - a minimum spanning tree for the network given would have to comprise of 5 arcs and so would the answer be 4.2? as a minimum spanning tree could be made using 0.9, 1.5, 2.3, 2.9, 3.5

Why 5 edges? There are 5 vertices.
Original post by mqb2766
Why 5 edges? There are 5 vertices.

oh right sorry I meant 4. so the answer would be 3.5?
Original post by machau
oh right sorry I meant 4. so the answer would be 3.5?

agree.
Original post by mqb2766
agree.

great, thank you for your help :smile:
Original post by machau
great, thank you for your help :smile:

Note Im not 100% sure about the wording of the question part, but I think thats the way to interpret it.
Original post by mqb2766
Note Im not 100% sure about the wording of the question part, but I think thats the way to interpret it.


yes I agree, thanks.
Original post by mqb2766
Note Im not 100% sure about the wording of the question part, but I think thats the way to interpret it.


Original post by machau
yes I agree, thanks.


Have to say I struggle to get the meaning of the question, but I would have said, 2.3.

0.9 and 1.5 must always be present.

If we have a network where a triangle of nodes are joined by 0.9, 1.5, and 2.3, then the 2.3 would not be part of a MST.

Quick Reply

Latest