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

Name Date

Minimum spanning trees: Prim's algorithm Problem set A

Show each edge you add, in order, and the total weight. No calculator is needed.

Difficulty: first skills applying them stretch

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

  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

  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––

  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–

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–

  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.
    2. (b) Pipe costs £350 for each 10 m. Find the total cost.

  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.
    2. (b) State the least total length.

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.
    2. (b) Do the same from F.
    3. (c) What do you notice about the two trees? Explain.

  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.
    2. (b) Use Prim's algorithm from A without edge AC. State the new total weight and how much longer it is.

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