Step 2 of 8 · Worked example · TEACH

← Algorithms, Optimisation & Project Scheduling

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 2

Follow the worked example and explain why each modelling and calculation step is valid.

An undirected complete four-vertex graph has AB=3, AC=5, AD=7; BC, BD and CD each have weight 41. Find a minimum spanning tree and its total weight.

An undirected complete graph has vertices A, B, C and D. AB = 3, AC = 5 and AD = 7. BC, BD and CD each have weight 41.

Find a minimum spanning tree and its total weight W.

Read it once, slowly. Then copy it onto your page.
  • What is going on? Four vertices, A to D. Complete means every pair is joined by an edge: 6 edges in all.
  • What is fixed? The weights. Three cheap edges, all from A: 3, 5 and 7. The other three, BC, BD, CD, are 41 each. No units are given.
  • What do they want? Two answers: a minimum spanning tree (which edges) and its total weight W.
Céim

Higher Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 2 of 8

Minimum Spanning Trees

A minimum spanning tree connects every vertex without cycles at the smallest possible total edge weight.

Why it matters

Exam solutions must justify both a valid connection and a minimum total, rather than merely select cheap edges.

The worked example

An undirected complete graph has vertices A, B, C and D. AB = 3, AC = 5 and AD = 7. BC, BD and CD each have weight 41. Find a minimum spanning tree and its total weight W.

How the worked example goes

  1. Read

    • What is going on? Four vertices, A to D. Complete means every pair is joined by an edge: 6 edges in all.
    • What is fixed? The weights. Three cheap edges, all from A: 3, 5 and 7. The other three, BC, BD, CD, are 41 each. No units are given.
    • What do they want? Two answers: a minimum spanning tree (which edges) and its total weight W.
  2. Understand

    • How do I picture it?
    • Draw A in the middle with B, C, D around it. Join every pair. Write each weight on its edge.
    • Edges from A
  3. Reduce

    • Where do I start?
    • Take the cheapest edges first, but only accept an edge that makes no cycle. This is Kruskal's algorithm.
    • An edge makes a cycle when its two ends are already joined in the tree.
  4. Solve

    • Take the cheapest edges.
    • Why cheapest first is safe: the cheapest edge out of any group of joined vertices always belongs to some minimum tree.
    • Accept AB = 3. Tree {A, B}. Total 3.
  5. Check

    • Is it really the least?
    • It is a spanning tree: 3 = 4 − 1 edges, and B, C, D each join A directly, so no cycle. ✓
    • Proof: the only tree with no 41 edge is AB, AC, AD. Every other tree carries at least one 41, and 41 > 15 on its own. ✓