Step 2 of 8 · Worked example · TEACH
0 of 3 done
Work through the example to CHECK to open the problems.
Reach CHECK to open the problems.Ordinary Level · Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 2Follow the worked example and explain why each modelling and calculation step is valid.
An undirected complete four-vertex graph has AB=7, AC=9, AD=11; BC, BD and CD each have weight 45. Find a minimum spanning tree and its total weight.
An undirected complete graph has vertices A, B, C and D. AB = 7, AC = 9 and AD = 11. BC, BD and CD each have weight 45.
Find a minimum spanning tree and its total weight W.
Ordinary Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 2 of 8
A minimum spanning tree connects every vertex without a cycle while minimising the total edge weight.
Choosing cheap edges alone can leave vertices disconnected or create cycles, so network cost and connectivity must be checked together.
An undirected complete graph has vertices A, B, C and D. AB = 7, AC = 9 and AD = 11. BC, BD and CD each have weight 45. Find a minimum spanning tree and its total weight W.