Minimum spanning trees and shortest path Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths Minimum spanning trees and shortest path questions. See exactly how to solve problems on kruskal, minimum-spanning-tree, networks, prim.

kruskalminimum-spanning-treenetworksprimtreesdijkstra
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
A network has vertices AA, BB, CC, DD and EE. The arcs of the network and their weights are AB=10AB=10, AC=16AC=16, BC=44BC=44, BD=17BD=17, CD=25CD=25, CE=45CE=45, DE=33DE=33. Use Kruskal's algorithm to find a minimum spanning tree for this network, and state the total weight of the tree.

Worked solution

  1. List the arcs in ascending order of weight

    AB=10,  AC=16,  BD=17,  CD=25,  DE=33,  BC=44,  CE=45AB=10,\;AC=16,\;BD=17,\;CD=25,\;DE=33,\;BC=44,\;CE=45

    Kruskal's algorithm looks at the arcs in order of increasing weight.

  2. Work along the list, rejecting any arc that would create a cycle

    accept AB,  AC,  BD,  DE;reject CD\text{accept }AB,\;AC,\;BD,\;DE;\quad\text{reject }CD

    An arc is rejected exactly when both of its ends are already joined to each other by arcs already chosen.

  3. Add the weights of the arcs in the tree

    10+16+17+33=7610+16+17+33=76

    The total weight of the tree is the sum of the weights of its 44 arcs.

  4. State the total weight of the minimum spanning tree

    total weight=76\text{total weight}=76

    This is the smallest possible total weight of a spanning tree of this network.

Answer
7676
Question 2
2 markseasy
A network has vertices AA, BB, CC, DD and EE. The arcs of the network and their weights are AB=51AB=51, AC=38AC=38, AD=14AD=14, AE=40AE=40, CD=5CD=5, CE=3CE=3, DE=49DE=49. Use Kruskal's algorithm to find a minimum spanning tree for this network, and state the total weight of the tree.

Worked solution

  1. List the arcs in ascending order of weight

    CE=3,  CD=5,  AD=14,  AC=38,  AE=40,  DE=49,  AB=51CE=3,\;CD=5,\;AD=14,\;AC=38,\;AE=40,\;DE=49,\;AB=51

    Kruskal's algorithm looks at the arcs in order of increasing weight.

  2. Work along the list, rejecting any arc that would create a cycle

    accept CE,  CD,  AD,  AB;reject AC,  AE,  DE\text{accept }CE,\;CD,\;AD,\;AB;\quad\text{reject }AC,\;AE,\;DE

    An arc is rejected exactly when both of its ends are already joined to each other by arcs already chosen.

  3. Add the weights of the arcs in the tree

    3+5+14+51=733+5+14+51=73

    The total weight of the tree is the sum of the weights of its 44 arcs.

  4. State the total weight of the minimum spanning tree

    total weight=73\text{total weight}=73

    This is the smallest possible total weight of a spanning tree of this network.

Answer
7373
Question 3
2 markseasy
A network has vertices AA, BB, CC, DD and EE. The arcs of the network and their weights are AB=37AB=37, AC=5AC=5, BC=30BC=30, BD=39BD=39, BE=20BE=20, CD=48CD=48, DE=41DE=41. Use Kruskal's algorithm to find a minimum spanning tree for this network, and state the total weight of the tree.

Worked solution

  1. List the arcs in ascending order of weight

    AC=5,  BE=20,  BC=30,  AB=37,  BD=39,  DE=41,  CD=48AC=5,\;BE=20,\;BC=30,\;AB=37,\;BD=39,\;DE=41,\;CD=48

    Kruskal's algorithm looks at the arcs in order of increasing weight.

  2. Work along the list, rejecting any arc that would create a cycle

    accept AC,  BE,  BC,  BD;reject AB\text{accept }AC,\;BE,\;BC,\;BD;\quad\text{reject }AB

    An arc is rejected exactly when both of its ends are already joined to each other by arcs already chosen.

  3. Add the weights of the arcs in the tree

    5+20+30+39=945+20+30+39=94

    The total weight of the tree is the sum of the weights of its 44 arcs.

  4. State the total weight of the minimum spanning tree

    total weight=94\text{total weight}=94

    This is the smallest possible total weight of a spanning tree of this network.

Answer
9494
Question 4
2 markseasy
A network has vertices AA, BB, CC, DD and EE. The arcs of the network and their weights are AB=6AB=6, AC=44AC=44, AD=32AD=32, BD=8BD=8, BE=39BE=39, CE=47CE=47, DE=16DE=16. Use Kruskal's algorithm to find a minimum spanning tree for this network, and state the total weight of the tree.

Worked solution

  1. List the arcs in ascending order of weight

    AB=6,  BD=8,  DE=16,  AD=32,  BE=39,  AC=44,  CE=47AB=6,\;BD=8,\;DE=16,\;AD=32,\;BE=39,\;AC=44,\;CE=47

    Kruskal's algorithm looks at the arcs in order of increasing weight.

  2. Work along the list, rejecting any arc that would create a cycle

    accept AB,  BD,  DE,  AC;reject AD,  BE\text{accept }AB,\;BD,\;DE,\;AC;\quad\text{reject }AD,\;BE

    An arc is rejected exactly when both of its ends are already joined to each other by arcs already chosen.

  3. Add the weights of the arcs in the tree

    6+8+16+44=746+8+16+44=74

    The total weight of the tree is the sum of the weights of its 44 arcs.

  4. State the total weight of the minimum spanning tree

    total weight=74\text{total weight}=74

    This is the smallest possible total weight of a spanning tree of this network.

Answer
7474
Question 5
2 markseasy
A network has vertices AA, BB, CC, DD and EE. The arcs of the network and their weights are AB=3AB=3, AD=10AD=10, BC=13BC=13, BD=2BD=2, BE=48BE=48, CD=27CD=27, CE=18CE=18. Use Prim's algorithm, starting at AA, to find a minimum spanning tree for this network, and state the total weight of the tree.

Worked solution

  1. Start the tree at vertex AA

    tree={A}\text{tree}=\left\{A\right\}

    Prim's algorithm grows a single connected tree from the starting vertex.

  2. Repeatedly add the cheapest arc joining the tree to a vertex not yet in the tree

    AB=3,  BD=2,  BC=13,  CE=18AB=3,\;BD=2,\;BC=13,\;CE=18

    The arcs are added in this order: AB,\;BD,\;BC,\;CE.

  3. Add the weights of the arcs chosen

    3+2+13+18=363+2+13+18=36

    This is the total weight of the minimum spanning tree.

  4. State the total weight of the minimum spanning tree

    total weight=36\text{total weight}=36

    Prim's algorithm always produces a minimum spanning tree.

Answer
3636

Unlock 65 more Minimum spanning trees and shortest path questions

Create a free account to work through every Further Maths Minimum spanning trees and shortest path question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Minimum spanning trees and shortest path practice

Hard QuestionsPractice Questions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks