Decision Maths: Graphs, Trees and Minimum Spanning Trees - Worksheets, Questions and Revision
24 original exam-style questions - 8 pages of questions with a full mark scheme - free printable PDF.
Decision Maths: Graphs, Trees and Minimum Spanning Trees revision guideMore A Level Further Maths practiceMock exams
This topic is chapter 2 of A Level Further Maths Decision Topic Workbook and chapter 17 of A Level Further Maths 10-Minute Tests 1.
4.2 Decision Maths: Graphs, Trees and Minimum Spanning Trees
| K | L | M | N | |
|---|---|---|---|---|
| K | - | 6 | - | 9 |
| L | 6 | - | 5 | 7 |
| M | - | 5 | - | 4 |
| N | 9 | 7 | 4 | - |
| 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 | - |
Question 1
- (a) n - 1 caoB1
- (a) Answer: n - 1
- (b) using the handshaking lemma, sum of degrees = 2 x (number of edges)M1
- (b) = 2(n - 1) cso, using the result from part (a) that the tree has n - 1 edgesA1
- (b) Answer: Sum of degrees = 2(n - 1).
- (c) number of edges = 15 - 1 = 14M1
- (c) 28 cao (sum of degrees = 2 x 14)A1
- (c) Answer: 28
Question 2
- (a) the sum of the degrees of all the vertices of a graph equals twice the number of edges (oe)B1
- (a) Answer: Sum of degrees = 2 x (number of edges).
- (b) sum of degrees = 2 x 11M1
- (b) 22 caoA1
- (b) Answer: 22
- (c) sum of degrees = 4 + 3 + 3 + 2 + 2 + 1 + 1 (= 16)M1
- (c) 8 cao (edges = 16/2)A1
- (c) Answer: 8
- (d) 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)B1
- (d) Answer: The number of odd-degree vertices must be even.
Question 3
- (a) edges from the matrix correctly listed: KL=6, KN=9, LM=5, LN=7, MN=4M1
- (a) edges sorted into ascending order: MN(4), LM(5), KL(6), LN(7), KN(9)M1
- (a) MN, LM, KL correctly accepted in order; LN and KN correctly rejected as each would form a cycleA1
- (a) total weight = 15 (km) caoA1
- (a) Answer: Minimum spanning tree = {KL, LM, MN}, weight 15 km.
- (b) LN(7) and KN(9) correctly identified as the two edges not requiredB1
- (b) LN(7) exceeds both edges on L-M-N (5,4); KN(9) exceeds every edge on K-L-M-N (6,5,4). To retain a spanning tree after adding either edge, remove an edge on its resulting cycle. Every valid replacement therefore increases the total weight, so neither can reduce it (oe).B1
- (b) Answer: LN(7) and KN(9) are not required.
Question 4
- (a) n - 1 caoB1
- (a) Answer: n - 1
- (b) 8 caoB1
- (b) Answer: 8
- (c) 13 caoB1
- (c) Answer: 13
- (d) a spanning tree of the network has 10 - 1 = 9 edgesM1
- (d) 6 cao (15 - 9)A1
- (d) Answer: 6
Question 5
- (a) edges sorted into ascending order: AB(3), AC(3), BD(4), CD(4), BC(5)M1
- (a) AB and AC both correctly accepted, then either BD or CD correctly accepted to complete a 3-edge treeM1
- (a) 10 (km) caoA1
- (a) Answer: 10 km
- (b) {AB, AC, BD} correctly identified as one minimum spanning tree of weight 10B1
- (b) {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)B1
- (b) Answer: {AB, AC, BD} and {AB, AC, CD}, both of weight 10.
- (c) 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)B1
- (c) Answer: Yes; the tie between BD and CD means either tree could result.
Question 6
- (a) 4 caoB1
- (a) Answer: 4
- (b) 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)M1
- (b) BC and DE each correctly accepted (no cycle)M1
- (b) CD correctly accepted, joining the two separate components {B,C} and {D,E}M1
- (b) AB correctly accepted, completing the tree; BD, AC, CE correctly rejected or not requiredA1
- (b) total weight = 11.4 (km) caoA1
- (b) Answer: Minimum spanning tree = {AB, BC, CD, DE}, weight 11.4 km.
- (c) 11.4 x 850 (ft their weight from part (b))M1
- (c) £9690 caoA1
- (c) Answer: £9690
Question 7
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: AB (3), AE (8), CF (13), BF (25), CD (28)A1
- (a) Answer: AB (3), AE (8), CF (13), BF (25), CD (28)
- (b) 77B1
- (b) Answer: 77
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AB (3), AE (8), BF (25), CF (13), CD (28)A1
- (c) Answer: AB (3), AE (8), BF (25), CF (13), CD (28)
Question 8
- (a) counts the edges at each vertexM1
- (a) degrees: A 2, B 3, C 3, D 2, E 2A1
- (a) sum of degrees = 12 = 2 x 6 edgesA1
- (a) Answer: A 2, B 3, C 3, D 2, E 2; sum 12
- (b) counts the vertices of odd degree: B, CM1
- (b) semi-Eulerian (has an Eulerian trail but no cycle)A1
- (b) Answer: semi-Eulerian (has an Eulerian trail but no cycle)
- (c) 6(6 - 1)/2M1
- (c) 15 edgesA1
- (c) each vertex has degree 5, which is odd, so K6 is not EulerianB1
- (c) Answer: 15 edges; not Eulerian
Question 9
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: DE (5), CE (10), AB (16), FG (19), AF (23), BE (33)A1
- (a) Answer: DE (5), CE (10), AB (16), FG (19), AF (23), BE (33)
- (b) 106B1
- (b) Answer: 106
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AB (16), AF (23), FG (19), BE (33), DE (5), CE (10)A1
- (c) Answer: AB (16), AF (23), FG (19), BE (33), DE (5), CE (10)
Question 10
- (a) counts the edges at each vertexM1
- (a) degrees: A 3, B 3, C 3, D 3, E 4, F 2A1
- (a) sum of degrees = 18 = 2 x 9 edgesA1
- (a) Answer: A 3, B 3, C 3, D 3, E 4, F 2; sum 18
- (b) counts the vertices of odd degree: A, B, C, DM1
- (b) neither Eulerian nor semi-EulerianA1
- (b) Answer: neither Eulerian nor semi-Eulerian
- (c) 7(7 - 1)/2M1
- (c) 21 edgesA1
- (c) each vertex has degree 6, which is even, so K7 is EulerianB1
- (c) Answer: 21 edges; Eulerian
Question 11
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: AG (4), CE (5), EF (11), DF (12), BG (15), AE (16)A1
- (a) Answer: AG (4), CE (5), EF (11), DF (12), BG (15), AE (16)
- (b) 63B1
- (b) Answer: 63
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AG (4), BG (15), AE (16), CE (5), EF (11), DF (12)A1
- (c) Answer: AG (4), BG (15), AE (16), CE (5), EF (11), DF (12)
Question 12
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: AC (5), AB (9), EG (12), BG (13), DE (15), DF (18)A1
- (a) Answer: AC (5), AB (9), EG (12), BG (13), DE (15), DF (18)
- (b) 72B1
- (b) Answer: 72
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AC (5), AB (9), BG (13), EG (12), DE (15), DF (18)A1
- (c) Answer: AC (5), AB (9), BG (13), EG (12), DE (15), DF (18)
Question 13
- (a) counts the edges at each vertexM1
- (a) degrees: A 2, B 2, C 4, D 2, E 4, F 3, G 3A1
- (a) sum of degrees = 20 = 2 x 10 edgesA1
- (a) Answer: A 2, B 2, C 4, D 2, E 4, F 3, G 3; sum 20
- (b) counts the vertices of odd degree: F, GM1
- (b) semi-Eulerian (has an Eulerian trail but no cycle)A1
- (b) Answer: semi-Eulerian (has an Eulerian trail but no cycle)
- (c) 7(7 - 1)/2M1
- (c) 21 edgesA1
- (c) each vertex has degree 6, which is even, so K7 is EulerianB1
- (c) Answer: 21 edges; Eulerian
Question 14
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: FG (5), DG (6), BC (10), AD (11), AE (18), CF (23)A1
- (a) Answer: FG (5), DG (6), BC (10), AD (11), AE (18), CF (23)
- (b) 73B1
- (b) Answer: 73
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AD (11), DG (6), FG (5), AE (18), CF (23), BC (10)A1
- (c) Answer: AD (11), DG (6), FG (5), AE (18), CF (23), BC (10)
Question 15
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: CD (5), AC (8), BD (9), BG (10), CE (17), CF (24)A1
- (a) Answer: CD (5), AC (8), BD (9), BG (10), CE (17), CF (24)
- (b) 73B1
- (b) Answer: 73
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AC (8), CD (5), BD (9), BG (10), CE (17), CF (24)A1
- (c) Answer: AC (8), CD (5), BD (9), BG (10), CE (17), CF (24)
Question 16
- (a) counts the edges at each vertexM1
- (a) degrees: A 2, B 2, C 3, D 3, E 2, F 3, G 3A1
- (a) sum of degrees = 18 = 2 x 9 edgesA1
- (a) Answer: A 2, B 2, C 3, D 3, E 2, F 3, G 3; sum 18
- (b) counts the vertices of odd degree: C, D, F, GM1
- (b) neither Eulerian nor semi-EulerianA1
- (b) Answer: neither Eulerian nor semi-Eulerian
- (c) 5(5 - 1)/2M1
- (c) 10 edgesA1
- (c) each vertex has degree 4, which is even, so K5 is EulerianB1
- (c) Answer: 10 edges; Eulerian
Question 17
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: BE (3), CE (7), AD (21), CD (23), CF (24)A1
- (a) Answer: BE (3), CE (7), AD (21), CD (23), CF (24)
- (b) 78B1
- (b) Answer: 78
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AD (21), CD (23), CE (7), BE (3), CF (24)A1
- (c) Answer: AD (21), CD (23), CE (7), BE (3), CF (24)
Question 18
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: AD (7), CF (9), AG (16), EF (17), DF (22), AB (32)A1
- (a) Answer: AD (7), CF (9), AG (16), EF (17), DF (22), AB (32)
- (b) 103B1
- (b) Answer: 103
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AD (7), AG (16), DF (22), CF (9), EF (17), AB (32)A1
- (c) Answer: AD (7), AG (16), DF (22), CF (9), EF (17), AB (32)
Question 19
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: EF (4), AC (7), EG (9), CD (10), CE (11), BD (24)A1
- (a) Answer: EF (4), AC (7), EG (9), CD (10), CE (11), BD (24)
- (b) 65B1
- (b) Answer: 65
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AC (7), CD (10), CE (11), EF (4), EG (9), BD (24)A1
- (c) Answer: AC (7), CD (10), CE (11), EF (4), EG (9), BD (24)
Question 20
- (a) counts the edges at each vertexM1
- (a) degrees: A 3, B 4, C 1, D 3, E 3A1
- (a) sum of degrees = 14 = 2 x 7 edgesA1
- (a) Answer: A 3, B 4, C 1, D 3, E 3; sum 14
- (b) counts the vertices of odd degree: A, C, D, EM1
- (b) neither Eulerian nor semi-EulerianA1
- (b) Answer: neither Eulerian nor semi-Eulerian
- (c) 7(7 - 1)/2M1
- (c) 21 edgesA1
- (c) each vertex has degree 6, which is even, so K7 is EulerianB1
- (c) Answer: 21 edges; Eulerian
Question 21
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: CD (3), BC (7), CE (13), BF (18), AB (21)A1
- (a) Answer: CD (3), BC (7), CE (13), BF (18), AB (21)
- (b) 62B1
- (b) Answer: 62
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AB (21), BC (7), CD (3), CE (13), BF (18)A1
- (c) Answer: AB (21), BC (7), CD (3), CE (13), BF (18)
Question 22
- (a) sorts the arcs in increasing order of weight and selects the smallestM1
- (a) adds each next smallest arc that does not form a cycleM1
- (a) arcs selected: AF (3), CD (9), AB (12), BD (13), BE (30)A1
- (a) Answer: AF (3), CD (9), AB (12), BD (13), BE (30)
- (b) 67B1
- (b) Answer: 67
- (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
- (c) first three arcs correctA1
- (c) arcs added: AF (3), AB (12), BD (13), CD (9), BE (30)A1
- (c) Answer: AF (3), AB (12), BD (13), CD (9), BE (30)
Question 23
- (a) consider the edges in ascending order of weight (oe)B1
- (a) 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)B1
- (a) Answer: Sort edges by ascending weight; add each edge unless it forms a cycle, stopping once n - 1 edges have been chosen.
- (b) 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)M1
- (b) EF, BC, FG, CD each correctly accepted, forming no cycle with the edges already chosenM1
- (b) AB correctly accepted, then DF correctly accepted as it joins the two separate components {A,B,C,D} and {E,F,G} (oe)M1
- (b) remaining edges CE, BE, AC, EG, CF, AD all correctly rejected, each forming a cycle with edges already acceptedA1
- (b) final minimum spanning tree correctly stated as {AB, BC, CD, DF, EF, FG}, using 6 edges to connect all 7 verticesA1
- (b) Answer: Minimum spanning tree: {AB, BC, CD, DF, EF, FG}.
- (c) 22 (km) ft their tree from part (b)B1
- (c) Answer: 22 km
- (d) 6 edges are used, and 7 - 1 = 6, so the number of edges is consistent with a spanning tree of a 7-vertex network caoB1
- (d) Answer: 6 edges = 7 - 1, so the tree is a valid spanning tree.
- (e) new total weight = 22 + 5 = 27 (ft their part (c))M1
- (e) cost = 27 x 3000 = £81,000 caoA1
- (e) Answer: New weight = 27 km; total cost = £81 000.
Question 24
- (a) 5 caoB1
- (a) Answer: 5
- (b) AD=9 selected, D added (rejecting AB=12, AF=14)M1
- (b) DE=5 selected, E added (comparing AB=12, AF=14, DC=6, DE=5)M1
- (b) EF=4 selected, F addedM1
- (b) DC=6 selected, C added (rejecting EC=10, EB=11, FC=8)M1
- (b) BC=7 selected, B added (rejecting AB=12, EB=11)A1
- (b) correct order of towns added stated: D, E, F, C, BA1
- (b) correct final edge set stated: {AD, DE, EF, DC, BC}A1
- (b) correct method shown of eliminating (crossing out) the column of any town already in the tree when searching for the next minimum entry (oe)B1
- (b) tree confirmed to use 5 edges connecting all 6 towns with no cyclesB1
- (b) Answer: Order of addition: D, E, F, C, B. Tree = {AD, DE, EF, DC, BC}.
- (c) 31 (km) ft their tree from part (b)B1
- (c) Answer: 31 km
- (d) 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) acceptedM1
- (d) total = 31 (km), matching part (c) and confirming the minimum spanning tree weight caoA1
- (d) Answer: Kruskal's algorithm also gives 31 km, confirming part (c).
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.