Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/graph-theory/ahl-1-9/problems/b/

jmaths

IB Mathematics: Applications and Interpretation HL · AHL 1: Graph Theory · AHL 1.9

Minimum spanning trees: Prim's algorithm Problem set B One question at a time

Try each question on paper first. Open the working a line at a time, then say whether you had it.

Skills

  1. Use Prim's algorithm, starting at A, on this graph. List the edges in the order they are added and find the total weight of the minimum spanning tree.

    2127683101514ABCDEF
    • Start at A. Edges in the order added: AB (2), BD (6), DE (3), BC (7), DF (10).
    • Total weight: 2 + 6 + 3 + 7 + 10 = 28.
    • Check: 6 vertices, 5 edges.

  2. Use Prim's algorithm, starting at B, to find a minimum spanning tree of this graph. Write the edges in the order you add them.

    1214106811313294ABCDEFG
    • Start at B. Edges in the order added: BG (3), GE (2), GA (4), ED (6), EF (8), DC (10).
    • Total weight: 3 + 2 + 4 + 6 + 8 + 10 = 33.
    • Check: 7 vertices, 6 edges.

  3. The table gives the weights of the edges of a graph. A dash means there is no edge. Use Prim's algorithm, starting at C, to find a minimum spanning tree. List the edges in order, draw the tree and state its total weight.

    ABCDEFA–14–4828B14–1721106C–17––3–D421––1927E810319–24F286–2724–
    • Start at C. Edges in the order added: CE (3), EA (8), AD (4), EB (10), BF (6).
    • Total weight: 3 + 8 + 4 + 10 + 6 = 31.
    • Check: 6 vertices, 5 edges.

  4. Use Prim's algorithm on this weighted adjacency table, starting at F. Write the edges in the order they are added and find the total weight of the tree.

    ABCDEFGA–––1433631B–––15–138C–––18–711D141518–4–2E3––4–12–F36137–12–29G318112–29–
    • Start at F. Edges in the order added: FC (7), CG (11), GD (2), DE (4), EA (3), GB (8).
    • Total weight: 7 + 11 + 2 + 4 + 3 + 8 = 35.
    • Check: 7 vertices, 6 edges.

In context

  1. The table shows the distances, in km, between six wind turbines A to F on an island. They must all be joined by cable to one network. Find the least total length of cable.

    ABCDEFA–244425119B24–1721736C4417–334130D252133–4245E1174142–32F936304532–
    • Prim from A: AF (9), AE (11), EB (7), BC (17), BD (21).
    • Total: 9 + 11 + 7 + 17 + 21 = 65 km.
    • Any start vertex gives the same total.

  2. A theme park has six zones A to F. The graph shows the possible cable routes, with lengths in units of 10 m. The network must join all zones with least total length.

    4121071458136ABCDEF

    1. (a) Use Prim's algorithm from A and state the total length of the network in metres.

      • Prim from A: AB (4), BE (5), BF (6), FC (8), ED (10).
      • Total: 4 + 5 + 6 + 8 + 10 = 33 units = 330 m.

    2. (b) Cable costs £480 for each 10 m. Find the total cost.

      • 33 × £480 = £15 840

  3. The table gives the distances, in km, between six lighthouses A to F. A boat company wants a set of routes that joins all six with least total length.

    ABCDEFA–628401431B6–41333218C2841–12837D403312–2325E1432823–30F3118372530–

    1. (a) Use Prim's algorithm from B. List the edges in the order added.

      • Start at B: BA (6), AE (14), EC (8), CD (12), BF (18).

    2. (b) State the least total length.

      • 6 + 14 + 8 + 12 + 18 = 58 km

Stretch

  1. The table gives the weights of the edges of a graph.

    ABCDEFA–322432–B3–1138239C2211–33–7D43833–216E322–21––F–3976––

    1. (a) Use Prim's algorithm from B. List the edges in order and state the total weight.

      • BE (2), BA (3), AD (4), DF (6), FC (7)
      • 2 + 3 + 4 + 6 + 7 = 22

    2. (b) Do the same from E.

      • EB (2), BA (3), AD (4), DF (6), FC (7)
      • 2 + 3 + 4 + 6 + 7 = 22

    3. (c) What do you notice about the two trees? Explain.

      • Both trees contain the same 5 edges.
      • Different weights mean one minimum spanning tree: only the order changes.

  2. The graph shows the possible pipe routes between the vertices, with lengths in km. A minimum spanning tree is built from A. Edge AB (length 9) then becomes unusable.

    921564118371310ABCDEFG

    1. (a) Find the total weight of the original minimum spanning tree.

      • Prim from A: AB (9), BC (2), CG (3), GE (7), EF (4), ED (6).
      • Total 31.

    2. (b) Use Prim's algorithm from A without edge AB. State the new total weight and how much longer it is.

      • Delete AB and run Prim again: AG (10), GC (3), CB (2), GE (7), EF (4), ED (6).
      • New total 32.
      • 32 − 31 = 1.

jmaths.xyz · AI HL · AHL 1.9 Minimum spanning trees: Prim's algorithm