Step 4 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.Higher Level · Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 4Follow the worked example and explain why each modelling and calculation step is valid.
Use Prim’s algorithm starting at A. The undirected graph has AB=3, AC=13, BC=5, BD=7, CD=16 and no other edges. Find the resulting tree weight.
An undirected graph has AB = 3, AC = 13, BC = 5, BD = 7 and CD = 16, and no other edges.
Use Prim's algorithm starting at A. Find the resulting tree weight W.
Higher Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 4 of 8
Prim’s algorithm builds a minimum spanning tree by repeatedly choosing the cheapest edge joining the current tree to a new vertex.
Recording the growing vertex set makes your exam working clear and prevents you from using Kruskal’s global edge-selection rule instead.
An undirected graph has AB = 3, AC = 13, BC = 5, BD = 7 and CD = 16, and no other edges. Use Prim's algorithm starting at A. Find the resulting tree weight W.