Menu
Sign up Sign in

AI HL · AHL 1

Graph Theory

0 of 43 skills done

0
AHL 1.9

Minimum spanning trees: Prim's algorithm

AHL 1.9

Minimum spanning trees: Prim's algorithm

Target: I can use Prim's algorithm from a named vertex on a drawn graph and list the edges in the order they are added. (+3 more)

By the end of this section

Key points

Minimum spanning trees

  • A tree is a connected graph with no cycles. A spanning tree joins every vertex of the graph.
  • A tree with n vertices has exactly n − 1 edges. If your answer has a different number of edges, it is wrong.
  • A minimum spanning tree is the spanning tree of least total weight. It gives the shortest total length of cable or pipe that joins every place.

Prim's algorithm on a graph

  • Start at the vertex the question names. That vertex is the first one in the tree.
  • Look at every edge that joins a vertex in the tree to a vertex not yet in it. Add the shortest.
  • Repeat until every vertex is in the tree. Never add an edge that joins two vertices already in the tree.
  • Write the edges in the order you add them. Add their weights for the total.

Prim's algorithm on a table

  • A dash in the table means there is no edge.
  • Cross out the row of the start vertex. Then look down the columns of the vertices in the tree, only in rows not crossed out. Box the smallest number.
  • The row of the boxed number is the next vertex. Cross out that row, and repeat.
  • Write the boxed numbers as edges, for example the box in row C, column A is edge AC.

Checks

  • When every weight is different, there is one minimum spanning tree. A different start vertex gives the same tree, with the edges added in a different order.
  • If two edges have the same weight, either may be chosen. The total weight is the same.
  • When no start vertex is given, any vertex will do.

Explore: minimum spanning trees

Choose Kruskal or Prim, then press Next to watch the tree grow, or switch to "Try it yourself" and press the edge you would add. Another graph gives a new example.

The edges in order of weight ()

    Vertices, n
    Edges in a spanning tree, n − 1
    Edges chosen so far

    1. Before you press Next, say whether Kruskal will take the next edge or reject it. How can you tell?
    2. Run Kruskal, then Prim on the same graph. Are the edges the same? Is the total the same? Is the order the same?
    3. With Prim, change the start vertex. What changes, and what stays the same?
    4. On Graph 4, two edges have the same weight. Does it matter which one you take first?

    Explore: Prim's algorithm on a table

    A dash means there is no edge. Press Next to cross out a row and box the smallest number, or choose "Try it yourself" and press the number you would box.

    Start vertex

    In the tree
    Boxed edges, in order

    1. Which numbers can you choose from at each step? Why are the numbers in the crossed-out rows left out?
    2. A number in the table can be smaller than the one you box and still be left alone. Find one and say why.
    3. Change the start vertex. Which boxed numbers change, and what happens to the total?
    4. How many edges does the tree have, and how many vertices? How could you tell before you began?

    Worked examples

    Problems like the ones in class. Pick one, try it, then open the working.
    Prim from vertex C

    Use Prim's algorithm, starting at vertex C, to find a minimum spanning tree of this graph. List the edges in the order you add them and find the total weight.

    9101513145486ABCDEF
    Working
    1. Edge 1

      Add CA (10)

      Tree: C. Edges to a new vertex: CA 10, CE 14, CB 15. The smallest is CA.

    2. Edge 2

      Add AB (9)

      Tree: A, C. Edges to a new vertex: AB 9, CE 14, CB 15. The smallest is AB.

    3. Edge 3

      Add BE (6)

      Tree: A, B, C. Edges to a new vertex: BE 6, BD 13, CE 14. The smallest is BE.

    4. Edge 4

      Add ED (5)

      Tree: A, B, C, E. Edges to a new vertex: ED 5, EF 8, BD 13. The smallest is ED.

    5. 109654ABCDEF
      Edge 5

      Add DF (4)

      Tree: A, B, C, D, E. Edges to a new vertex: DF 4, EF 8. The smallest is DF. All 6 vertices are in.

    6. Total

      10 + 9 + 6 + 5 + 4 = 34

      5 edges for 6 vertices. The order is CA, AB, BE, ED, DF.

    Video walkthrough coming
    Prim from a table

    The table shows 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 the order you add them, draw the tree and find its total weight.

    ABCDEFA–17–48–B17–22136–C–22–1126–D41311–719E86267–21F–––1921–
    Working
    1. Edge 1

      Add AD (4)

      Cross out row A. Tree: A. Uncrossed rows, columns of the tree: AD 4, AE 8, AB 17. The smallest is AD. Box it.

    2. Edge 2

      Add DE (7)

      Tree: A, D. Uncrossed rows, columns of the tree: DE 7, AE 8, DC 11, DB 13, AB 17, DF 19. The smallest is DE. Box it and cross out its row.

    3. Edge 3

      Add EB (6)

      Tree: A, D, E. Uncrossed rows, columns of the tree: EB 6, DC 11, DB 13, AB 17, DF 19, EF 21, EC 26. The smallest is EB. Box it and cross out its row.

    4. Edge 4

      Add DC (11)

      Tree: A, B, D, E. Uncrossed rows, columns of the tree: DC 11, DF 19, EF 21, BC 22, EC 26. The smallest is DC. Box it and cross out its row.

    5. 4761119ABCDEF
      Edge 5

      Add DF (19)

      Tree: A, B, C, D, E. Uncrossed rows, columns of the tree: DF 19, EF 21. The smallest is DF. Box it and cross out its row.

    6. Total

      4 + 7 + 6 + 11 + 19 = 47

      5 edges for 6 vertices.

    Video walkthrough coming
    Cabling six villages

    The table shows the distances, in km, between six villages A to F. An electricity company must join all six villages with cable. Find the least total length of cable needed.

    ABCDEFA–179342326B17–32223530C932–131219D342213–3315E23351233–6F263019156–
    Working
    1. Start

      Start at A

      The question does not give a start vertex. Any start gives a tree of the same total weight, so use A.

    2. Edge 1

      Add AC (9)

      Tree: A. Edges to a new vertex: AC 9, AB 17, AE 23, AF 26, AD 34. The smallest is AC.

    3. Edge 2

      Add CE (12)

      Tree: A, C. Edges to a new vertex: CE 12, CD 13, AB 17, CF 19, AE 23, AF 26, CB 32, AD 34. The smallest is CE.

    4. Edge 3

      Add EF (6)

      Tree: A, C, E. Edges to a new vertex: EF 6, CD 13, AB 17, CF 19, AF 26, CB 32, ED 33, AD 34, EB 35. The smallest is EF.

    5. Edge 4

      Add CD (13)

      Tree: A, C, E, F. Edges to a new vertex: CD 13, FD 15, AB 17, FB 30, CB 32, ED 33, AD 34, EB 35. The smallest is CD.

    6. Last edge

      Add AB (17)

      Continue in the same way until all 6 villages are joined.

    Video walkthrough coming
    A different start vertex

    Use the graph in the first example. Start Prim's algorithm at F. Find the total weight of the tree. Does it change?

    9101513145486ABCDEF
    Working
    1. Edge 1

      Add FD (4)

      Tree: F. Edges to a new vertex: FD 4, FE 8. The smallest is FD.

    2. Edge 2

      Add DE (5)

      Tree: D, F. Edges to a new vertex: DE 5, FE 8, DB 13. The smallest is DE.

    3. Edge 3

      Add EB (6)

      Tree: D, E, F. Edges to a new vertex: EB 6, DB 13, EC 14. The smallest is EB.

    4. Edge 4

      Add BA (9)

      Tree: B, D, E, F. Edges to a new vertex: BA 9, EC 14, BC 15. The smallest is BA.

    5. 456910ABCDEF
      Edge 5

      Add AC (10)

      Tree: A, B, D, E, F. Edges to a new vertex: AC 10, EC 14, BC 15. The smallest is AC.

    6. Compare

      4 + 5 + 6 + 9 + 10 = 34

      The edges come in a different order but the total is 34, the same as from C. Each weight is different, so the minimum spanning tree is the same tree.

    Video walkthrough coming