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.Ordinary 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=7, AC=17, BC=9, BD=11, CD=20 and no other edges. Find the resulting tree weight.
An undirected graph has AB = 7, AC = 17, BC = 9, BD = 11 and CD = 20, and no other edges.
Use Prim's algorithm starting at A. Find the resulting tree weight W.
Ordinary Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 4 of 8
Prim's algorithm grows one tree by repeatedly choosing the cheapest edge joining a vertex already in the tree to a new vertex.
Tracking the growing vertex set prevents you from confusing Prim's rule with Kruskal's global edge ordering.
An undirected graph has AB = 7, AC = 17, BC = 9, BD = 11 and CD = 20, and no other edges. Use Prim's algorithm starting at A. Find the resulting tree weight W.