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.Ordinary 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=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.

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, like costs on each edge. Three cheap ones, all from A: 7, 9 and 11. The other three are 45 each.
  • What do they want? Two answers: a minimum spanning tree, meaning which edges, and its total weight W.
Céim

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

Minimum Spanning Trees

A minimum spanning tree connects every vertex without a cycle while minimising the total edge weight.

Why it matters

Choosing cheap edges alone can leave vertices disconnected or create cycles, so network cost and connectivity must be checked together.

The worked example

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.

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, like costs on each edge. Three cheap ones, all from A: 7, 9 and 11. The other three are 45 each.
    • What do they want? Two answers: a minimum spanning tree, meaning which edges, and its total weight W.
  2. Understand

    • How do I picture it?
    • Put A in the middle with B, C, D around it. Join every pair and write each weight on its edge.
    • A spanning tree joins all 4 vertices with no loop. So it has 4 − 1 = 3 edges. Which 3?
  3. Reduce

    • Where do I start?
    • Take the cheapest edges first. Skip any edge that would make a loop: that happens when its two ends are already joined.
    • In order: 7, 9, 11, then 45, 45, 45. Stop when 3 edges are in, then add them for W.
  4. Solve

    • Take the cheapest edges.
    • Accept AB = 7. Total 7.
    • Accept AC = 9. C is new, so no loop.
  5. Check

    • Is it really the least?
    • It is a spanning tree: 3 = 4 − 1 edges, and B, C, D each join A, so no loop. ✓
    • Every other tree uses at least one 45. Its total is at least 7 + 9 + 45 = 61, and 61 > 27. ✓