Revision Library

revisionlibrary.co.uk

A-Level · AQA

FP.D2 Decision Maths: Graphs, Trees and Minimum Spanning Trees

AQA 7367 · Calculator allowed · about 120 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

The graph G has vertex set {A, B, C, D, E} and edge set {AB, AC, BC, BD, CE, DE} (the graph is unweighted).

(a)State what is meant by a tree in graph theory.(1)

(b)State what is meant by a spanning tree of a connected graph.(1)

(c)For the graph G, state (i) the order of G, (ii) the size of G.(2)

(d)Determine, with justification, whether G is a tree.(2)

(e)State the number of edges in the complete graph K6.(1)

(Total for Question 1 is 7 marks)

This question concerns the relationship between the degrees of the vertices of a graph and its number of edges.

(a)State the handshaking lemma, relating the sum of the degrees of the vertices of a graph to its number of edges.(1)

(b)A graph has 8 vertices and 11 edges. Find the sum of the degrees of its vertices.(2)

(c)A graph has degree sequence 4, 3, 3, 2, 2, 1, 1. Find the number of edges in the graph.(2)

(d)Explain why the number of vertices of odd degree in any graph must be even.(1)

(Total for Question 2 is 6 marks)

This question concerns the number of edges in a spanning tree.

(a)State the number of edges in a spanning tree of a connected graph with n vertices, in terms of n.(1)

(b)Hence write down the number of edges in a spanning tree of a connected graph with 9 vertices.(1)

(c)A connected graph has a spanning tree with 12 edges. State the number of vertices in the graph.(1)

(d)A connected network has 10 vertices and 15 edges. State how many edges must be removed to reduce the network to a spanning tree.(2)

(Total for Question 3 is 5 marks)

A network of relay stations A, B, C, D, E, F, G is to be connected by fibre-optic cable. The possible direct links and their lengths, in km, are: AB=5, AC=8, AD=10, BC=3, BE=7, CD=4, CE=6, CF=9, DF=5, EF=2, EG=8, FG=3. Kruskal's algorithm is to be used to find a minimum spanning tree for this network.

(a)State the two key steps of Kruskal's algorithm for finding a minimum spanning tree.(2)

(b)Apply Kruskal's algorithm to the network, listing the edges in the order they are considered and stating whether each is accepted or rejected.(5)

(c)State the total weight of the minimum spanning tree found in part (b).(1)

(d)Verify that the tree found in part (b) uses the correct number of edges for a spanning tree of this network.(1)

(e)A new relay station, H, is to be added, connected only to G by a new link GH = 5 km, at a cost of £3000 per km. State the new total weight of the minimum spanning tree once H is included, and find the total cost of the resulting network.(2)

(Total for Question 4 is 11 marks)

Six towns P, Q, R, S, T, U are to be linked by a new cable network. The possible direct routes and their lengths, in km, are: PQ=6, PR=9, PS=13, QR=4, QT=8, RS=5, RT=7, ST=6, SU=11, TU=3. Prim's algorithm, starting at P, is to be used to find a minimum spanning tree for this network.

(a)State how Prim's algorithm builds up a minimum spanning tree from a given starting vertex.(2)

(b)Apply Prim's algorithm to the network, starting at vertex P. Show the order in which vertices are added to the tree and the edge chosen at each step.(6)

(c)State the total weight of the minimum spanning tree found in part (b).(1)

(d)State two advantages of using Prim's algorithm, rather than Kruskal's algorithm, when working by hand with a large network given as a distance matrix.(2)

(Total for Question 5 is 11 marks)

The table below shows the direct distances, in km, between six market towns A, B, C, D, E, F that a regional council wishes to connect with a new fibre-optic network, following existing roads only where a distance is given (a dash indicates no direct road).
A B C D E F
A - 12 - 9 - 14
B 12 - 7 - 11 -
C - 7 - 6 10 8
D 9 - 6 - 5 -
E - 11 10 5 - 4
F 14 - 8 - 4 -

(a)State the number of edges required in a minimum spanning tree connecting all 6 towns.(1)

(b)Use Prim's algorithm, starting at A, to find a minimum spanning tree for this network. Show, at each stage, the town added to the tree and the length of road used to connect it.(9)

(c)State the total length of cable required for the minimum spanning tree found in part (b).(1)

(d)Verify your answer to part (c) by applying Kruskal's algorithm to the same network and comparing the total weight obtained.(2)

(Total for Question 6 is 13 marks)

A network has vertices A, B, C, D and edges AB=3, AC=3, BC=5, BD=4, CD=4 (weights in km).

(a)Apply Kruskal's algorithm to find the total weight of a minimum spanning tree for this network.(3)

(b)State two different edge sets that both give a minimum spanning tree of total weight 10, and explain why both are valid minimum spanning trees.(2)

(c)State whether Prim's algorithm, started at vertex A, could also produce either of the two trees found in part (b). Give a reason.(1)

(Total for Question 7 is 6 marks)

Five villages, Ashcombe (A), Bramwell (B), Corbridge (C), Dunley (D) and Elsworth (E), are to be connected by underground fibre-optic cable. The possible direct routes and their lengths are: AB=3.2 km, AC=5.6 km, BC=2.4 km, BD=4.1 km, CD=3.0 km, CE=6.5 km, DE=2.8 km. The cost of laying cable is £850 per km.

(a)State the number of edges needed to connect all 5 villages in a minimum spanning tree.(1)

(b)Use Kruskal's algorithm to find a minimum spanning tree for this network, showing the order in which edges are considered and whether each is accepted or rejected.(5)

(c)Given the cost of laying cable stated above, find the total cost of connecting all 5 villages using the minimum spanning tree found in part (b).(2)

(Total for Question 8 is 8 marks)

Discuss the similarities and differences between Kruskal's algorithm and Prim's algorithm for finding a minimum spanning tree of a connected network. Your answer should refer to how each algorithm selects edges, how each avoids forming a cycle, and which algorithm is generally more efficient to apply by hand to a large, dense network given as a distance matrix.

(Total for Question 9 is 7 marks)

The table below represents a network of possible cable routes, with distances in km, between four substations K, L, M, N (a dash indicates no direct route).
K L M N
K - 6 - 9
L 6 - 5 7
M - 5 - 4
N 9 7 4 -

(a)Use Kruskal's algorithm to find a minimum spanning tree for the network represented by the matrix above, showing the edges in the order considered.(4)

(b)State the two edges of the network that were not required in the minimum spanning tree, and explain why neither could reduce the total weight if used instead of an edge already chosen.(2)

(Total for Question 10 is 6 marks)

A network has vertices P, Q, R, S and edges PQ=4, PR=6, PS=9, QR=3, QS=7, RS=5 (weights in km). A student claims that {PQ, PR, RS} is the minimum spanning tree for this network, with total weight 15 km.

(a)Explain why {PQ, PR, RS} is a valid spanning tree for this network, but state whether it is necessarily the minimum spanning tree.(2)

(b)Use Kruskal's algorithm to find the actual minimum spanning tree for this network, state its total weight, and hence confirm whether the tree given above is the minimum spanning tree.(4)

(Total for Question 11 is 6 marks)

This question concerns the sum of the degrees of the vertices of a tree.

(a)State the number of edges in a tree with n vertices.(1)

(b)Hence show that the sum of the degrees of the vertices of a tree with n vertices is 2(n - 1).(2)

(c)A tree has 15 vertices. Find the sum of the degrees of its vertices.(2)

(Total for Question 12 is 5 marks)

Mark scheme · FP.D2 Decision Maths: Graphs, Trees and Minimum Spanning Trees

Question 1

(a) B1 a connected graph containing no cycles (oe), e.g. a connected graph with exactly one path between every pair of vertices
(a) Answer: A tree is a connected graph that contains no cycles.
(b) B1 a subgraph that includes every vertex of the original graph and is itself a tree (connected, no cycles) (oe)
(b) Answer: A spanning tree of a connected graph is a subgraph containing every vertex of the graph, which is connected and contains no cycles.
(c) B1 order = 5 cao
(c) B1 size = 6 cao
(c) Answer: Order = 5, size = 6.
(d) B1 correct conclusion: G is not a tree
(d) B1 valid justification, e.g. G contains the cycle A-B-C-A (oe), or: a tree on 5 vertices has exactly 4 edges but G has 6
(d) Answer: G is not a tree.
(e) B1 15 cao
(e) Answer: 15

Question 2

(a) B1 the sum of the degrees of all the vertices of a graph equals twice the number of edges (oe)
(a) Answer: Sum of degrees = 2 x (number of edges).
(b) M1 sum of degrees = 2 x 11
(b) A1 22 cao
(b) Answer: 22
(c) M1 sum of degrees = 4 + 3 + 3 + 2 + 2 + 1 + 1 (= 16)
(c) A1 8 cao (edges = 16/2)
(c) Answer: 8
(d) B1 the sum of all degrees is always even (= 2|E|); removing the even-degree vertices (which contribute an even amount) leaves the sum of the odd degrees, which must also be even, and a sum of odd numbers is only even if there is an even number of them (oe)
(d) Answer: The number of odd-degree vertices must be even.

Question 3

(a) B1 n - 1 cao
(a) Answer: n - 1
(b) B1 8 cao
(b) Answer: 8
(c) B1 13 cao
(c) Answer: 13
(d) M1 a spanning tree of the network has 10 - 1 = 9 edges
(d) A1 6 cao (15 - 9)
(d) Answer: 6

Question 4

(a) B1 consider the edges in ascending order of weight (oe)
(a) B1 an edge is added unless it would form a cycle with edges already selected; the process stops once all vertices are connected, i.e. n - 1 edges have been chosen (oe)
(a) Answer: Sort edges by ascending weight; add each edge unless it forms a cycle, stopping once n - 1 edges have been chosen.
(b) M1 edges sorted into ascending order: EF(2), BC(3), FG(3), CD(4), AB(5), DF(5), CE(6), BE(7), AC(8), EG(8), CF(9), AD(10)
(b) M1 EF, BC, FG, CD each correctly accepted, forming no cycle with the edges already chosen
(b) M1 AB correctly accepted, then DF correctly accepted as it joins the two separate components {A,B,C,D} and {E,F,G} (oe)
(b) A1 remaining edges CE, BE, AC, EG, CF, AD all correctly rejected, each forming a cycle with edges already accepted
(b) A1 final minimum spanning tree correctly stated as {AB, BC, CD, DF, EF, FG}, using 6 edges to connect all 7 vertices
(b) Answer: Minimum spanning tree: {AB, BC, CD, DF, EF, FG}.
(c) B1 22 (km) ft their tree from part (b)
(c) Answer: 22 km
(d) B1 6 edges are used, and 7 - 1 = 6, so the number of edges is consistent with a spanning tree of a 7-vertex network cao
(d) Answer: 6 edges = 7 - 1, so the tree is a valid spanning tree.
(e) M1 new total weight = 22 + 5 = 27 (ft their part (c))
(e) A1 cost = 27 x 3000 = £81 000 cao
(e) Answer: New weight = 27 km; total cost = £81 000.

Question 5

(a) B1 the tree starts containing only the given starting vertex (oe)
(a) B1 at each step, the least-weight edge joining a vertex already in the tree to a vertex not yet in the tree is added; this repeats until all vertices are included (oe)
(a) Answer: Start with only the given vertex; repeatedly add the cheapest edge from the tree to a vertex outside it, until all vertices are included.
(b) M1 PQ=6 selected, Q added (rejecting PR=9, PS=13)
(b) M1 QR=4 selected, R added
(b) M1 RS=5 selected, S added
(b) M1 ST=6 selected, T added (rejecting QT=8, RT=7)
(b) A1 TU=3 selected, U added (rejecting SU=11)
(b) A1 complete minimum spanning tree correctly stated as {PQ, QR, RS, ST, TU}, using 5 edges to connect all 6 vertices
(b) Answer: Order of addition: Q, R, S, T, U. Tree = {PQ, QR, RS, ST, TU}.
(c) B1 24 (km) ft their tree from part (b)
(c) Answer: 24 km
(d) B1 Prim's algorithm always maintains a single growing tree, so there is no need to check explicitly whether an edge would create a cycle (oe)
(d) B1 Kruskal's algorithm requires the whole edge list to be sorted in advance, which can be slow for a network with many edges; Prim's algorithm on a matrix only ever searches the rows/columns of vertices already in the tree (oe)
(d) Answer: Prim's algorithm needs no cycle-checking and avoids sorting the full edge list in advance.

Question 6

(a) B1 5 cao
(a) Answer: 5
(b) M1 AD=9 selected, D added (rejecting AB=12, AF=14)
(b) M1 DE=5 selected, E added (comparing AB=12, AF=14, DC=6, DE=5)
(b) M1 EF=4 selected, F added
(b) M1 DC=6 selected, C added (rejecting EC=10, EB=11, FC=8)
(b) A1 BC=7 selected, B added (rejecting AB=12, EB=11)
(b) A1 correct order of towns added stated: D, E, F, C, B
(b) A1 correct final edge set stated: {AD, DE, EF, DC, BC}
(b) B1 correct method shown of eliminating (crossing out) the column of any town already in the tree when searching for the next minimum entry (oe)
(b) B1 tree confirmed to use 5 edges connecting all 6 towns with no cycles
(b) Answer: Order of addition: D, E, F, C, B. Tree = {AD, DE, EF, DC, BC}.
(c) B1 31 (km) ft their tree from part (b)
(c) Answer: 31 km
(d) M1 Kruskal's algorithm correctly applied: EF(4), DE(5), CD(6), BC(7) accepted in order; CF(8) rejected as it would form a cycle; AD(9) accepted
(d) A1 total = 31 (km), matching part (c) and confirming the minimum spanning tree weight cao
(d) Answer: Kruskal's algorithm also gives 31 km, confirming part (c).

Question 7

(a) M1 edges sorted into ascending order: AB(3), AC(3), BD(4), CD(4), BC(5)
(a) M1 AB and AC both correctly accepted, then either BD or CD correctly accepted to complete a 3-edge tree
(a) A1 10 (km) cao
(a) Answer: 10 km
(b) B1 {AB, AC, BD} correctly identified as one minimum spanning tree of weight 10
(b) B1 {AB, AC, CD} correctly identified as a second minimum spanning tree of weight 10, with explanation that BD and CD have equal weight (4), so either may be chosen without changing the total weight (oe)
(b) Answer: {AB, AC, BD} and {AB, AC, CD}, both of weight 10.
(c) B1 Yes; since BD and CD both have weight 4, Prim's algorithm could select either edge when connecting D, so it could produce either of the two trees (oe)
(c) Answer: Yes; the tie between BD and CD means either tree could result.

Question 8

(a) B1 4 cao
(a) Answer: 4
(b) M1 edges sorted into ascending order: BC(2.4), DE(2.8), CD(3.0), AB(3.2), BD(4.1), AC(5.6), CE(6.5)
(b) M1 BC and DE each correctly accepted (no cycle)
(b) M1 CD correctly accepted, joining the two separate components {B,C} and {D,E}
(b) A1 AB correctly accepted, completing the tree; BD, AC, CE correctly rejected or not required
(b) A1 total weight = 11.4 (km) cao
(b) Answer: Minimum spanning tree = {AB, BC, CD, DE}, weight 11.4 km.
(c) M1 11.4 x 850 (ft their weight from part (b))
(c) A1 £9690 cao
(c) Answer: £9690

Question 9

Level 0 (0): No relevant comments made, or the response fails to address the question.
Level 1 (1-2): A basic description of at most one algorithm is given, with little or no valid comparison between the two.
Level 2 (3-5): Both algorithms are described with reasonable accuracy, and at least one valid comparison point is made (for example relating to cycle-checking or efficiency), but the discussion is not fully developed or contains minor inaccuracies.
Level 3 (6-7): Both algorithms are described accurately and at least three distinct, well-explained comparison points are made (for example cycle-checking, efficiency on dense versus sparse networks, and uniqueness of the resulting tree), with correct terminology used throughout.
Indicative content:
- Both algorithms produce a spanning tree connecting all vertices with the minimum total weight, using exactly n - 1 edges.
- Kruskal's algorithm considers edges across the whole network in ascending order of weight, adding an edge unless it would form a cycle with edges already chosen; the structure being built can consist of several disconnected sub-trees before they eventually merge.
- Prim's algorithm always grows a single connected tree from a chosen starting vertex, at each stage adding the least-weight edge joining a vertex already in the tree to a vertex not yet in the tree.
- Because Prim's algorithm only ever has one connected component, there is no need to explicitly check whether adding an edge would create a cycle; Kruskal's algorithm does require this check whenever an edge under consideration could join two vertices already linked by other selected edges.
- Prim's algorithm applied to a distance matrix is generally more efficient to use by hand for a large, dense network, since at each stage only the rows and columns of vertices already in the tree need to be searched for the next minimum entry, with unwanted columns crossed out.
- Kruskal's algorithm requires the entire edge list to be sorted first, which can be time-consuming for a dense network with many edges, though it can be more straightforward to apply when the network is sparse (relatively few edges compared with vertices).
- Both algorithms are greedy algorithms (each makes the locally optimal choice at each stage) and both are guaranteed to produce a spanning tree of minimum total weight; the specific tree produced may not be unique when there are equal edge weights, but the minimum total weight itself is always the same.

Question 10

(a) M1 edges from the matrix correctly listed: KL=6, KN=9, LM=5, LN=7, MN=4
(a) M1 edges sorted into ascending order: MN(4), LM(5), KL(6), LN(7), KN(9)
(a) A1 MN, LM, KL correctly accepted in order; LN and KN correctly rejected as each would form a cycle
(a) A1 total weight = 15 (km) cao
(a) Answer: Minimum spanning tree = {KL, LM, MN}, weight 15 km.
(b) B1 LN(7) and KN(9) correctly identified as the two edges not required
(b) B1 valid explanation, e.g. L and N (and K and N) are already connected via lower-weight edges once the tree is complete, so including either would only create a cycle, not reduce the total weight (oe)
(b) Answer: LN(7) and KN(9) are not required.

Question 11

(a) B1 valid, since {PQ, PR, RS} has 3 (= 4 - 1) edges connecting all 4 vertices with no cycle, so it is a valid spanning tree
(a) B1 not necessarily the minimum; a spanning tree is not automatically the minimum-weight spanning tree (oe)
(a) Answer: It is a valid spanning tree, but not necessarily the minimum one.
(b) M1 edges sorted into ascending order: QR(3), PQ(4), RS(5), PR(6), QS(7), PS(9)
(b) M1 QR, PQ, RS correctly accepted, forming a complete spanning tree; PR, QS, PS correctly rejected or not required
(b) A1 total weight = 12 (km) cao
(b) A1 since 12 < 15, the tree {PQ, PR, RS} is confirmed not to be the minimum spanning tree (oe)
(b) Answer: Minimum spanning tree = {QR, PQ, RS}, weight 12 km; the student's tree (weight 15) is not minimum.

Question 12

(a) B1 n - 1 cao
(a) Answer: n - 1
(b) M1 using the handshaking lemma, sum of degrees = 2 x (number of edges)
(b) A1 = 2(n - 1) cso, using the result from part (a) that the tree has n - 1 edges
(b) Answer: Sum of degrees = 2(n - 1).
(c) M1 number of edges = 15 - 1 = 14
(c) A1 28 cao (sum of degrees = 2 x 14)
(c) Answer: 28

Decision Maths: Graphs, Trees and Minimum Spanning Trees - Worksheets, Questions and Revision