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/

jmaths

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

Minimum spanning trees: Prim's algorithm Problem set A Worked solutions

Skills

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

    10514121193415ABCDEF
    • Start at D. Edges in the order added: DA (11), AE (4), EB (9), BC (5), CF (3).
    • Total weight: 11 + 4 + 9 + 5 + 3 = 32.
    • Check: 6 vertices, 5 edges.

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

    8212154146310137ABCDEFG
    • Start at G. Edges in the order added: GC (3), CB (2), GA (7), GE (10), EF (4), CD (12).
    • Total weight: 3 + 2 + 7 + 10 + 4 + 12 = 38.
    • 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 A, to find a minimum spanning tree. List the edges in order, draw the tree and state its total weight.

    ABCDEFA–––513–B––17–2212C–17––147D5–––186E13221418––F–1276––
    • Start at A. Edges in the order added: AD (5), DF (6), FC (7), FB (12), AE (13).
    • Total weight: 5 + 6 + 7 + 12 + 13 = 43.
    • Check: 6 vertices, 5 edges.

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

    ABCDEFGA–525––3727B5–4–294032C254–22–2136D––22–28718E–29–28–1534F374021715–14G273236183414–
    • Start at D. Edges in the order added: DF (7), FG (14), FE (15), FC (21), CB (4), BA (5).
    • Total weight: 7 + 14 + 15 + 21 + 4 + 5 = 66.
    • Check: 7 vertices, 6 edges.

In context

  1. The table shows the distances, in km, between six villages A to F. A water company must connect all six villages by pipe so that every village is joined to the others. Find the least total length of pipe.

    ABCDEFA–4419281110B44–2026815C1920–331222D282633–1821E1181218–14F1015222114–
    • Prim from A: AF (10), AE (11), EB (8), EC (12), ED (18).
    • Total: 10 + 11 + 8 + 12 + 18 = 59 km.
    • Any start vertex gives the same total.

  2. A farm has seven buildings A to G. The graph shows the possible pipe routes, with lengths in units of 10 m. The pipe network must join all seven buildings with least total length.

    21351041583697ABCDEFG

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

      • Prim from A: AB (2), AG (7), GC (3), CD (5), GE (6), EF (4).
      • Total: 2 + 7 + 3 + 5 + 6 + 4 = 27 units = 270 m.

    2. (b) Pipe costs £350 for each 10 m. Find the total cost.

      • 27 × £350 = £9 450

  3. The table gives the distances, in km, between six towns A to F. A rail company wants to join all six towns with track of least total length.

    ABCDEFA–292431642B29–47504812C2447–403944D315040–1425E6483914–35F4212442535–

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

      • Start at B: BF (12), FD (25), DE (14), EA (6), AC (24).

    2. (b) State the least total length.

      • 12 + 25 + 14 + 6 + 24 = 81 km

Stretch

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

    ABCDEFA–18–173013B18–––2534C––––2138D17–––2812E30252128–4F133438124–

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

      • AF (13), FE (4), FD (12), AB (18), EC (21)
      • 13 + 4 + 12 + 18 + 21 = 68

    2. (b) Do the same from F.

      • FE (4), FD (12), FA (13), AB (18), EC (21)
      • 4 + 12 + 13 + 18 + 21 = 68

    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 cable routes between the vertices, with lengths in km. A minimum spanning tree is built from A. Edge AC (length 4) then becomes unusable.

    849151421156ABCDEF

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

      • Prim from A: AC (4), AB (8), BE (6), ED (2), EF (5).
      • Total 25.

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

      • Delete AC and run Prim again: AB (8), BE (6), ED (2), EF (5), BC (9).
      • New total 30.
      • 30 − 25 = 5.

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