Minimum Spanning Trees

Topic

From an AS paper

Edexcel

Edexcel · Old spec

AS June 2025 Q1

EdexcelAS paperCurrent spec7 marksAlgorithms Minimum Spanning Trees

The list of ten numbers above is to be sorted into ascending order.

(a) Carry out a bubble sort, starting at the left-hand end of the list, to produce the sorted list. You should only give the state of the list after each pass. (3)

Figure 1: weighted network on vertices A to F with arcs AB 13, AC 10, AD 30, BC 12, BE 22, BF 23, CF 20, CD 28, DF 25, EF 16 — Figure 1

(b) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for the network in Figure 1. You must list the arcs in the order in which you select them. (2)

(c)

(i) Draw the minimum spanning tree on Diagram 1 in the answer book.

Diagram 1: the vertices A to F of Figure 1 with no arcs — Diagram 1

(ii) Find the weight of the minimum spanning tree. (2)

Mark scheme (a)

Scheme

Marks

16	10	25	30	13	12	28	22	23	20
10	16	25	13	12	28	22	23	20	30

1.1b

10	16	13	12	25	22	23	20	28	30
10	13	12	16	22	23	20	25	28	30

1.1b

10	12	13	16	22	20	23	25	28	30
10	12	13	16	20	22	23	25	28	30
10	12	13	16	20	22	23	25	28	30

(sort complete)

A1CSO

1.1b

(3)

Notes

a1M1: Bubble sort using all 10 numbers (condone one error or omission). Consistent direction, end number (30) in place and list beginning with correct three numbers (10, 16, 25).
Quick sort scores M0.

a1A1: First, second and third passes correct – so end three numbers (25, 28, 30) in place.

a2A1: CSO (previous two marks must have been awarded in this part). Must state either ‘sort/algorithm complete’ or show 6^th pass showing no swaps/changes.

SC: Bubble sort from right hand end of list:

16	10	25	30	13	12	28	22	23	20
10	16	12	25	30	13	20	28	22	23
10	12	16	13	25	30	20	22	28	23
10	12	13	16	20	25	30	22	23	28
10	12	13	16	20	22	25	30	23	28
10	12	13	16	20	22	23	25	30	28
10	12	13	16	20	22	23	25	28	30
10	12	13	16	20	22	23	25	28	30

M1 Consistent direction, end number (10) in place and list ending with correct three numbers (28,22,23).
A1 First, second and third passes correct – so first three numbers (10,12,13) in place.
A1 CSO (previous two marks must have been awarded in this part). Must state either ‘sort complete’ or show 7^th pass showing no swaps/changes.

SC: If the candidate sorts into descending order from left hand side they can score M1 only for a fully correct sort (even if reversed). (see below)

Descending from left-hand side (maximum M1A0A0)

16	10	25	30	13	12	28	22	23	20
16	25	30	13	12	28	22	23	20	10
25	30	16	13	28	22	23	20	12	10
30	25	16	28	22	23	20	13	12	10
30	25	28	22	23	20	16	13	12	10
30	28	25	23	22	20	16	13	12	10
30	28	25	23	22	20	16	13	12	10

Mark scheme (b)

Scheme	Marks	AO
AC (10), BC (12), CF (20), EF (16), DF (25)	M1 A1	1.1b 1.1b
	(2)

Notes

b1M1: First three arcs correctly chosen in order. Any rejection seen implies M0.

b1A1: All 5 arcs correctly chosen in order.

SC: All 6 nodes written in the correct order ACBFED scores M1A0

Scheme	Marks	AO
(i)	B1	2.2a
(ii) 83	B1	2.2a
	(2)
	(7 marks)

A2 June 2024 Q2

EdexcelCurrent spec13 marksMinimum Spanning Trees Travelling Salesman

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

	A	B	C	D	E	F	G	H	J
A	–	50	59	26	50	40	87	63	59
B	50	–	28	61	79	63	45	64	48
C	59	28	–	33	57	35	70	36	45
D	26	61	33	–	24	64	71	37	33
E	50	79	57	24	–	40	64	30	31
F	40	63	35	64	40	–	47	70	71
G	87	45	70	71	64	47	–	34	67
H	63	64	36	37	30	70	34	–	33
J	59	48	45	33	31	71	67	33	–

(a) Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree. (3)

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

Diagram 1: the nine vertices A, B, C, D, E, F, G, H and J with no arcs — Diagram 1

A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.

(d) Use your answer to part (b) to calculate an initial upper bound for the length of the historian’s route. (1)

(e)

(i) Use the nearest neighbour algorithm, starting at D, to find an upper bound for the length of the historian’s route.

(ii) Write down the route which gives this upper bound. (3)

Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles was found.

(f) State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer. (1)

(g) By deleting A and all of its arcs, find a lower bound for the length of the historian’s route. (2)

By deleting J and all of its arcs, a lower bound of length 274 miles was found.

(h) State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer. (1)

Mark scheme (a)

Scheme	Marks	AO
Prim’s starting at D: DE, AD, EH; EJ, CD, BC; GH, CF	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: First three arcs correctly chosen in order {DE, AD, EH, …} or first four nodes correctly chosen in order{D, E, A, H,…}. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of the matrix {3, -, -, 1, 2, -, -, 4, -} so please check the top of the matrix carefully. If they start at any other vertex M1 only for the first three arcs in order (Starting at A AD DE EH).

A1: First six arcs correctly chosen in order {DE, AD, EH, EJ, CD, BC, …} or all nine nodes correctly chosen in order{D, E, A, H, J, C, B, G, F}. Order of nodes may be seen at the top of the matrix so for the first two marks accept {3, 7, 6, 1, 2, 9, 8, 4, 5} (do not condone any missing numbers e.g. the number 9 must be above F)

A1: CSO – all arcs correctly stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Scheme	Marks	AO
Weight of MST is 241 (miles)	B1	1.1b
	(1)

Scheme	Marks	AO
	B1	1.1b
	(1)

Scheme	Marks	AO
482 (miles)	B1ft	1.1b
	(1)

Mark scheme (e)

Scheme	Marks	AO
NNA starting at D: D – E – H – J – C – B – G – F – A – D 24 + 30 + 33 + 45 + 28 + 45 + 47 + 40 + 26 = 318 (miles)	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: Nearest neighbour route starting at D – must have at least D – E – H – J – C – B – … allow if stated in terms of arcs (DE EH HJ JC CB) but not for just numbering across the matrix

A1: CAO route (must return to D and can be stated as arcs DE EH HJ JC CB BG GF FA AD)

A1: CAO length (318)

Mark scheme (f)

Scheme	Marks	AO
The best upper bound is the one found in (e) as 318 is less than both 352 and 482	dB1ft	2.2a
	(1)

Notes

dB1ft: Follow through their value from (e) (must include reason e.g. 318 is the lowest of the values found, but they do not need to mention the other values) Must score at least M1 in (e)

Mark scheme (g)

Scheme	Marks	AO
(241 – 26) + 26 + 40 = 281 (miles)	M1 A1	3.1b 2.2a
	(2)

Notes

M1: (weight of their MST from (b) or 241 only) – 26 + 26(AD) + 40(AF) (oe so may not see the – 26 + 26). A correct answer of 281 can imply this (and the next) mark. Alternatively may delete A and find RMST (215) and add AD (26) and AF (40)

A1: 281

Mark scheme (h)

Scheme	Marks	AO
The best lower bound is the one found in (g) as 281 is greater than 274	dB1ft	2.2a
	(1)
	(13 marks)

Notes

dB1ft: Follow through their “281” with 274 and makes conclusion (e.g. 281 is the bigger value, but they do not need to mention 274). Must be a smaller value than their answer to (f) and must score at least M1 in (g)

A2 June 2023 Q5

EdexcelCurrent spec13 marksMinimum Spanning Trees Route Inspection Travelling Salesman

Figure 5: network on A to J with arcs AB 34, AG 8, AF 20, AD 42, BE 50, BH 21, BC 17, GD 23, GF 48, FD 22, FE 65, CE 33, CJ 10, HJ 12, EJ 18 — Figure 5

[The total weight of the network is 423]

Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road.

The table below shows the shortest distances, in miles, between the nine towns.

	A	B	C	D	E	F	G	H	J
A	–	34	51	31	79	20	8	55	61
B	34	–	17	65	45	54	42	21	27
C	51	17	–	82	28	71	59	22	10
D	31	65	82	–	87	22	23	86	92
E	79	45	28	87	–	65	87	30	18
F	20	54	71	22	65	–	28	75	81
G	8	42	59	23	87	28	–	63	69
H	55	21	22	86	30	75	63	–	12
J	61	27	10	92	18	81	69	12	–

Table of shortest distances

A route is needed that minimises the total distance required to traverse each road at least once.

The route must start at F and finish at J.

(a)

(i) By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.

(ii) State the total length of this route. (5)

(b) Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. (3)

Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.

(c) Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete’s route. Write down the route that gives this upper bound. (2)

(d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2)

Pete decides to take the route he found in (c).

(e) Interpret the route in terms of the actual towns visited. (1)

Mark scheme (a)

Scheme	Marks	AO
(i) Route must start at F and finish at J therefore need to consider pairings of the nodes F, C, D and G	M1	3.1b
CD + FG = 82 + 28 = 110 CF + DG = 71 + 23 = 94 CG + DF = 59 + 22 = 81	A1 A1	1.1b 1.1b
Repeated roads: CB, BA, AG, and DF	A1	2.2a
(ii) Length of route = 423 + 81 = 504 (miles)	A1ft	2.2a
	(5)

Notes

M1: The correct three pairings of the correct four nodes (F, C, D and G)

A1: Two rows correct including pairings and totals

A1: All three rows correct including pairings and totals

A1: CAO (CB, BA, AG, DF only but in any order) – must be stated as edges so A0 for any of CG or CBAG or CG via B and A

A1ft: 423 + weight of their shortest pairing

Mark scheme (b)

Scheme	Marks	AO
Prim’s starting at A: AG, AF, DF, AB, BC, CJ, HJ, EJ	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: First three arcs correctly chosen in order {AG, AF, DF, …} or first four nodes correctly chosen in order{A, G, F, D,…}. If any explicit rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of one of the tables{1, -, -, 4, -, 3, 2, -, -} so please check the top of the tables carefully

A1: First five arcs correctly chosen in order {AG, AF, DF, AB, BC, …} or all nine nodes correctly chosen in order{A, G, F, D, B, C, J, H, E}. Order of nodes may be seen at the top of one of the tables so for the first two marks accept {1, 5, 6, 4, 9, 3, 2, 8, 7} (do not condone any missing numbers e.g. the number 9 must be above E)

A1: CSO – all arcs correct stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of one of the tables unless the correct list of arcs (in the correct order) is also seen)

Mark scheme (c)

Scheme	Marks	AO
NNA starting at G: G – A – F – D – B – C – J – H – E – G 8 + 20 + 22 + 65 + 17 + 10 + 12 + 30 + 87 = 271	M1 A1	1.1b 1.1b
	(2)

Notes

M1: Nearest neighbour route starting at G – must have at least G – A – F – D – B – C – … allow if stated in terms of arcs

A1: CAO on length (271) and route (must return to G and can be stated in terms of arcs)

Mark scheme (d)

Scheme	Marks	AO
(141 – 8) + 8 + 23 = 164 (miles)	M1 A1	3.1b 2.2a
	(2)

Notes

M1: For one of the following

RMST arcs: AF, DF, AB, BC, CJ, HJ, EJ (stated in any order) – condone AG added too but must be removed at some later stage (e.g. subtracting 8 at some point)
RMST weight calculation: 20 + 22 + 34 + 17 + 10 + 12 + 18 (not just 20, 22, etc.)
RMST weight stated: 133 or 141 – 8
Lower bound stated: 164

A1: CAO (164)

Scheme	Marks	AO
GAFD GA BCJH J E JCBA G	B1	3.2a
	(1)
	(13 marks)

AS June 2023 Q3

EdexcelAS paperCurrent spec11 marksMinimum Spanning Trees Shortest Path

Figure 2: weighted network on vertices A to J with edges AB 40, AD 49, AE 45, BC 32, BD 6, BE 28, BF 58, CD 24, CG 41, CH 34, DG 15, EG 11, EF 30, FG 43, FJ 6, GH 23, GJ 50, HJ 61 — Figure 2

Figure 2 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track.
Dyfan wishes to travel from A to J via C. Dyfan wishes to minimise the distance they travel.

Given that Dijkstra’s algorithm is to be applied only once to find Dyfan’s route,

(a) explain why the algorithm should begin at C. (1)

(b) Use Dijkstra’s algorithm to find the shortest route from A to J via C. State this route and its length. (6)

(c) Use Prim’s algorithm, starting at C, to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree. (3)

(d) State the total length, in km, of the minimum spanning tree. (1)

Mark scheme (a)

Scheme	Marks	AO
Dijkstra’s algorithm only finds the shortest path from a given starting node to all other nodes in the network. If the shortest route from A to J via C is required, then this is equivalent to finding the shortest paths from C to A and C to J and so therefore as C is common to both paths then the algorithm should start at C	B1	3.5b
	(1)

Notes

B1: Recognition that the limitation of the algorithm is that it can only find the shortest path from a given starting node to all others (and not from any node to any other node) and therefore a clear indication is required that C is the starting vertex to of the two required paths that include A and J. As a minimum accept that finding A to J via C is equivalent of finding the shortest (oe) path from C to J and C to A (these two paths must be stated this way round)

Dijkstra labelling from C: C 1 0; D 2 24; B 3 30 (32 30); H 4 34; G 5 39 (41 39 (57)); E 6 50 (58 50); A 7 70 (73 70 (95)); F 8 80 (88 82 80); J 9 86 (95 89 86) — Mark scheme (b)

Dijkstra labelling from A: A 1 0; B 2 40; E 3 45 (45 (68)); D 4 46 (49 46); G 5 56 (56 (61)); C 6 70 (72 70 (97)); F 7 75 (98 75 (99)); H 8 79 (79 (104)); J 9 81 (106 81 (140)) — Mark scheme (b)

Scheme	Marks	AO
	M1 A1 (CDBH) A1 (GEA) A1ft (FJ)	1.1b 1.1b 1.1b 1.1b
Shortest route from A to J via C is A B D C D G E F J	A1	2.2a
Shortest length: 70 + 86 = 156 (km)	A1ft	2.2a
	(6)

Mark scheme (c)

Scheme	Marks	AO
Prim’s algorithm from C: CD, BD, DG; EG, GH, EF; FJ, AB	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: Prim (not Kruskal) – First three arcs (CD, BD, DG) correctly chosen, or first four nodes (C, D, B, G) correctly chosen in order. If any explicit rejections seen at any point then M1 (max) only. A list of weights alone scores M0.

A1: First six arcs correctly chosen in order (CD, BD, DG, EG, GH, EF), or all nodes correctly chosen in order (C, D, B, G, E, H, F, J, A)

A1: cso (correct solution only) – all arcs correctly stated (not just nodes) and chosen in the correct order (with no additional, incorrect or repeated arcs)

Misread in (c): Starting at a node other than C scores M1 only – must have the first three arcs (or four nodes) correct (and in the correct order). Therefore applying Prim, starting at A, would give AB, BD, DG,… for M1 only

Scheme	Marks	AO
155 (km)	B1	1.1b
	(1)
	(11 marks)

A2 June 2022 Q6

EdexcelCurrent spec12 marksAlgorithms Minimum Spanning Trees

6. The following algorithm determines the number of comparisons made when Prim’s algorithm is applied to \(K_n\)

Step 1	Start
Step 2	Input the value of \(n\)
Step 3	Let \(a = 1\)
Step 4	Let \(b = n - 2\)
Step 5	Let \(c = b\)
Step 6	Let \(a = a + 1\)
Step 7	Let \(b = b - 1\)
Step 8	Let \(c = c + (a \times b) + (a - 1)\)
Step 9	If \(b \gt 0\) go to Step 6
Step 10	Output \(c\)
Step 11	Stop

(a) For \(K_5\), complete the table in the answer book to show the results obtained at each step of the algorithm. (3)

You may not need to use all the rows in this table. It may not be necessary to complete all the boxes in each row.

\(n\)	\(a\)	\(b\)	\(c\)

Output: ____________

Figure 4: complete graph on A, B, C, D and E with arcs AB 17, AC 28, AD 24, AE 14, BC 19, BD 21, BE 15, CD 23, CE 20, DE 13 — Figure 4

The weights of the ten arcs in Figure 4 are

(b)

(i) Starting at the left-hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.

(ii) Find the total number of comparisons performed during the sort. (5)

(c) Find the maximum total number of comparisons required to sort the weights of the 10 arcs of \(K_5\) into ascending order using bubble sort. (1)

It is given that the maximum total number of comparisons required to sort the weights of the arcs of \(K_n\) into ascending order using bubble sort is

\(\lambda n(n - 1)(n + 1)(n - 2)\)

where \(\lambda\) is a constant.

(d) Determine the maximum total number of comparisons required to sort the weights of the arcs of \(K_{50}\) into ascending order using bubble sort. You must make your method and working clear. (3)

Mark scheme (a)

Scheme

Marks

\(n\)	\(a\)	\(b\)	\(c\)
5	1	3	3
	2	2	8
	3	1	13
	4	0	16

M1
A1

1.1b
1.1b

Output: 16

2.2a

(3)

Notes

(a) M1: At least three rows of cells completed with a correct first row – condone repeated values in all columns or a single value in each row

A1: cao – the values in the second and third rows correct

A1: cao – correct output following a correct fourth row (with no extra rows) – the output must either be stated on the given answer line or ‘output 16’ must be clearly written somewhere near the table (do not bod the 16 circled, underlined, written twice, etc.)

Mark scheme (b)

Scheme

Marks

(i)

17	21	24	14	23	13	15	19	28	20
17	21	14	23	13	15	19	24	20	28
17	14	21	13	15	19	23	20	24	28
14	17	13	15	19	21	20	23	24	28
14	13	15	17	19	20	21	23	24	28
13	14	15	17	19	20	21	23	24	28
13	14	15	17	19	20	21	23	24	28

M1
A1
A1ft
A1

1.1b
1.1b
1.1b
1.1b

(ii) Total number of comparisons: 9 + 8 + 7 + 6 + 5 + 4 = 39

2.2a

(5)

Notes

(b)(i) M1: Bubble sort. Consistent direction, end number (28) in place, the list containing ten numbers with the list beginning with the correct first five numbers (17 21 14 23 13). Do check these carefully as some candidates show the result of each comparison and swap in their first pass. Consider the placement of the candidate’s numbers, rather than what the candidate labels each line of their pass. For example, assume that the first time that the 28 appears at the end of the list is the end of their first pass

A1: Second and third passes correct – so end three numbers in place

A1ft: Fourth and fifth passes correct following through from the candidate’s third pass – so end five numbers in place. After their third pass their list must contain the correct 10 numbers

A1: cso (correct solution only – so previous three marks must have been awarded in this part). Must show a 6^th pass showing no swaps/changes (give bod if the passes are not labelled but do not award this mark if it is clear that after the 5^th pass the list is simply being written out again (rather than a genuine 6^th pass taking place)). Condone if the sort continues until a 9^th pass has been completed (but there must be no changes in the 6^th to 9^th passes)

(b)(ii) B1: cao (for total number of comparisons)

In (b) starting at the right-hand end of the list is M0. Quick sort (or any other sorting algorithm e.g. shuttle) is M0. No misreads in this part – mark exactly to the scheme.

If sorting into descending order, then award M1 for 21 24 17 23 14 15 19 28 20 13 and the first A1 for both 24 21 23 17 15 19 28 20 14 13 and 24 23 21 17 19 28 20 15 14 13 ONLY (so two out of the first four marks) even if the list is re-ordered after the sort is complete

Scheme	Marks	AO
45	B1	2.2a
	(1)

Mark scheme (d)

Scheme	Marks	AO
e.g. when \(n = 3\) the total number of comparisons is 3 therefore \(\lambda(3)(3 - 1)(3 + 1)(3 - 2) = 3\) e.g. when \(n = 5\) the total number of comparisons is 45 (from (c)) therefore \(\lambda(5)(5 - 1)(5 + 1)(5 - 2) = 45\)	M1	3.1a
For \(K_{50}\) total number of comparisons is \(\text{‘}\lambda\text{’}(50)(50 - 1)(50 + 1)(50 - 2)\)	dM1	3.4
749 700	A1	2.2a
	(3)
	(12 marks)

Notes

(d) M1: Considering the total number of comparisons for any positive integer value of \(n\) (greater than 2) and substitute into the given expression (if correct \(\lambda = \dfrac{1}{8}\)). The correct value of \(\lambda\) implies this mark. If using \(n = 5\) then follow through their value from (c). If any other value of \(n\) used, then the maximum number of comparisons must be correct e.g.

\(n\)	3	4	5	6	7	8	9	10
Comparisons	3	15	45	105	210	378	630	990

dM1: Using their \(\lambda\) and \(n = 50\) to calculate the maximum total number of comparisons (dependent on the previous M mark). Writing \(\dfrac{1}{8}(50)(50 - 1)(50 + 1)(50 - 2)\) implies the first two M marks

A1: cao (749 700) – no marks for the correct answer with no working

Alternative solution to (d) for those who are clearly using an algebraic method to derive the quartic expression for the maximum total number of comparisons:

If there are \(N\) values then
1^st pass of bubble sort requires \(N - 1\) comparisons
2^nd pass of bubble sort requires \(N - 2\) comparisons
3^rd pass of bubble sort requires \(N - 3\) comparisons and so on

Therefore, the total number of comparisons is \(\displaystyle\sum_{r=1}^{N-1} r = \tfrac{1}{2}(N - 1)N\) M1

Maximum number of comparisons in \(K_n\) is therefore
\(\tfrac{1}{2}\left(\tfrac{1}{2}n(n - 1) - 1\right)\left(\tfrac{1}{2}n(n - 1)\right)\)
\(= \tfrac{1}{8}n(n - 1)\left[n(n - 1) - 2\right]\)
\(= \tfrac{1}{8}n(n - 1)(n^2 - n - 2) = \tfrac{1}{8}n(n - 1)(n - 2)(n + 1)\) so \(\lambda = \tfrac{1}{8}\) dM1

Therefore, maximum number of comparisons for \(K_{50}\) is 749 700 A1

M1: Considering the total number of comparisons that are required to sort a list containing \(N\) values (possibly will see \(1 + 2 + 3 + \ldots + (n - 1)\)) and using the standard series result that \(\sum r = \tfrac{1}{2}n(n + 1)\) to get the correct quadratic expression for the total number of comparisons when sorting \(N\) values (allow any letter)

dM1: Dependent on previous M mark – substituting the correct quadratic expression into the correct quadratic expression with correct algebraic working leading to \(\tfrac{1}{8}n(n - 1)(n - 2)(n + 1)\)

A1: Correct answer of 749 700

[Corrected from the printed mark scheme: the alternative solution ends “so \(k = \tfrac{1}{8}\)”; the constant in the question is \(\lambda\).]

AS June 2022 Q1

EdexcelAS paperCurrent spec9 marksAlgorithms Minimum Spanning Trees

The list of eleven numbers shown above is to be sorted into ascending order.

(a) Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify your pivots clearly. (4)

Figure 1: weighted network on vertices A to G with arcs AC 55, AB 52, BC 41, BD 47, CD 34, CE 37, CF 33, DE 28, DG 59, EG 42, FG 44 — Figure 1

(b) Use Kruskal’s algorithm to find the minimum spanning tree for the network in Figure 1. You should list the arcs in the order in which you consider them. For each arc, state whether or not you are adding it to your minimum spanning tree. (3)

(c)

(i) Draw the minimum spanning tree on Diagram 1 in the answer book.

(ii) State the total weight of the tree. (2)

Diagram 1: the vertices A to G of Figure 1 with no arcs — Diagram 1

Mark scheme (a)

Scheme

Marks

middle right											Pivot(s)
55	44	34	59	28	\(\underline{37}\)	41	52	33	42	47	37
34	\(\underline{28}\)	33	37	55	44	59	\(\underline{41}\)	52	42	47	28 41
28	34	\(\underline{33}\)	37	41	55	44	59	\(\underline{52}\)	42	47	33 52
28	33	34	37	41	44	\(\underline{42}\)	47	52	55	\(\underline{59}\)	(34) 42 59
28	33	34	37	41	42	44	\(\underline{47}\)	52	55	59	47 (55)
28	33	34	37	41	42	44	47	52	55	59	(Sort complete)

middle left											Pivot(s)
55	44	34	59	28	\(\underline{37}\)	41	52	33	42	47	37
34	\(\underline{28}\)	33	37	55	44	59	\(\underline{41}\)	52	42	47	28 41
28	\(\underline{34}\)	33	37	41	55	44	\(\underline{59}\)	52	42	47	34 59
28	33	34	37	41	55	44	\(\underline{52}\)	42	47	59	(33) 52
28	33	34	37	41	44	\(\underline{42}\)	47	52	55	59	42 (55)
28	33	34	37	41	42	\(\underline{44}\)	47	52	55	59	44
28	33	34	37	41	42	44	47	52	55	59	(Sort Complete)

M1
A1
A1ft
A1

1.1b
1.1b
1.1b
1.1b

(4)

Notes

M1: Quick Sort, pivot, p, chosen (must be choosing middle right or middle left). After the first pass the list must read (values less than the pivot), pivot, (values greater than the pivot). If choosing one pivot per iteration then M1 only. This mark can be scored if one number only is either missing or incorrect or an additional number is added to the list.

A1: First two passes correct (pivots for third pass need not be chosen)

A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots) (pivot(s) for the fifth pass need not be chosen). After their second pass their list must contain either 10, 11 or 12 numbers (so allow one additional/missing number)

A1: cso – if choosing middle right pivots then they must include a fifth pass and if choosing middle left then they must include a sixth pass

SC: If list is sorted into descending order, then award a maximum of M1A1A0A0 (so 2 marks) as in the scheme above even if the list is re-ordered after the sort is complete

Mark scheme (b)

Scheme	Marks	AO
DE, CF, CD, reject CE; BC, EG, reject FG; reject BD, AB, (reject AC, reject DG)	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: Kruskal: first three arcs correctly chosen (DE, CF, CD), and arc CE rejected at the correct time. No follow through from an incorrect list. Condone list of weights for this mark only (28, 33, 34 and reject 37)

A1: First five arcs correctly chosen (DE, CF, CD, BC, EG), and arc FG rejected at the correct time. Must state the arcs and not the corresponding weights for this mark

A1: cso including all rejections correct and at the correct time. We do not need to see the explicit rejection of arcs AC and DG but if these are explicitly rejected then they must be in the correct order. Note that a list of all the arcs in the correct order followed by a list of the arcs in the MST can score full marks

Scheme	Marks	AO
(i)	B1	2.2a
(ii) (Total weight =) 230	B1	2.2a
	(2)
	(9 marks)

A2 October 2021 Q3

EdexcelCurrent spec8 marksMinimum Spanning Trees Travelling Salesman

	A	B	C	D	E	F	G	H
A	–	24	42	48	34	37	32	22
B	24	–	40	35	30	41	39	44
C	42	40	–	21	26	45	38	36
D	48	35	21	–	32	37	29	27
E	34	30	26	32	–	34	40	28
F	37	41	45	37	34	–	43	41
G	32	39	38	29	40	43	–	38
H	22	44	36	27	28	41	38	–

Table 1

Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.

(a) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree. (3)

(b) State the weight of the minimum spanning tree. (1)

	A	B	C	D	E	F	G	H
J	31	27	50	29	43	25	49	35

Table 2

Table 2 shows the distances, in miles, between town J and towns A, B, C, D, E, F, G and H.

Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.

(c) Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav’s route. You must state your route and its length. (2)

(d) Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav’s route. (2)

Mark scheme (a)

Scheme	Marks	AO
Prim’s starting at A: AH, AB, DH; CD, CE; DG, EF	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

(a) M1: First three arcs correctly chosen in order {AH, AB, DH, …} or first four nodes correctly chosen in order {A, H, B, D,…}. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of the matrix {1, 3, -, 4, -, -, -, 2} so please check the top of the matrix carefully

A1: First five arcs correctly chosen in order {AH, AB, DH, CD, CE, …} or all eight nodes correctly chosen in order {A, H, B, D, C, E, G, F}. Order of nodes may be seen at the top of the matrix so for the first two marks accept {1, 3, 5, 4, 6, 8, 7, 2} (do not condone any missing numbers e.g. the number 8 must be above F)

A1: cso – all arcs correct stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Scheme	Marks	AO
Weight of MST is 183 (miles)	B1	2.2a
	(1)

Mark scheme (c)

Scheme	Marks	AO
NNA: J – F – E – C – D – H – A – B – G – J	B1	1.1b
Upper bound is 267 (miles)	B1	2.2a
	(2)

Notes

(c) B1: cao (for route – must return to J)

B1: cao (for upper bound of 267)

Scheme	Marks	AO
183 + 27 + 25 =…	M1	3.1b
… = 235 (miles)	A1	2.2a
	(2)
	(8 marks)

AS October 2020 Q3

EdexcelAS paperCurrent spec11 marksMinimum Spanning Trees Route Inspection

Figure 2: network on vertices A to H with arcs AB 2x + 10, AD 3x – 2, BC 30, BD 20, BG 25, CE 42, CG 15, DG 8, DH 7, EF 12, EG 23, FG 10, FH 29, GH 17 — Figure 2

[The weight of the network is \(5x + 246\)]

(a) Explain why it is not possible to draw a graph with an odd number of vertices of odd valency. (2)

Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road.

Prim’s algorithm, starting at A, is applied to the network. The order in which the arcs are selected is AD, DH, DG, FG, EF, CG, BD. It is given that the order in which the arcs are selected is unique.

(b) Using this information, find the smallest possible range of values for \(x\), showing your working clearly. (3)

A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex.

Given that the time taken to traverse this route is 318 minutes,

Mark scheme (a)

Scheme	Marks	AO
e.g. (each arc contributes 1 to the orders of two nodes, and so) the sum of the orders of all the nodes is equal to twice the number of arcs	B1	1.2
Which implies that the sum of the orders of all the nodes is even and therefore there must be an even (or zero) number of vertices of odd order hence there cannot be an odd number of vertices of odd order	B1dep	2.4
	(2)

Notes

B1: For one of the following points:

‘Sum of the order/valencies of the nodes/vertices = 2(number of arcs/edges)’
‘Each arc/edge contributes 1 to the order/valency of two nodes/vertices’
‘Sum of the order/valencies of the nodes/vertices is even’

But condone for B1 only

‘sum of the valencies = 2(number of arcs/edges)’ or ‘sum of the nodes/vertices = 2(number of arcs/edges)’ or ‘sum of the orders = 2(number of arcs/edges)
‘sum of the valencies is even’ or ‘sum of the nodes/edges is even’

B1dep: Stating that ‘the sum of the order (or valencies) of the nodes/vertices = 2(number of arcs/edges) therefore the sum of the order (of the nodes/vertices) is even which implies that there must be an even number of nodes/vertices of odd order (or there cannot be an odd number of nodes/vertices of odd order) OR each arc/edge contributes 1 to the order of two nodes/vertices therefore the sum of the order (of the nodes/vertices) is even which implies that there must be an even number of nodes/vertices of odd order (or there cannot be an odd number of nodes/vertices of odd order)

So in summary the first B mark should be awarded for a broadly correct statement (but allow bod as shown in the last two bullet-points above) but for both B marks a fully correct explanation must be given without any bod (please note therefore it is not possible to score B0B1). Do not accept non-technical language for nodes/arcs for either B1B0 or B1B1

Mark scheme (b)

Scheme	Marks	AO
Either \(2x + 10 > 3x - 2\) or \(2x + 10 > 20\)	M1	3.1b
\(x < 12\)	A1	1.1b
\(x > 5\)	A1	1.1b
	(3)

Notes

M1: Either comparing arc AB with AD or BD with AB – accept any inequality symbol or equals

A1: CAO (\(x < 12\))

A1: CAO (\(x > 5\))

Mark scheme (c)

Scheme	Marks	AO
Applies the route inspection algorithm to this non-standard case	M1	3.1b
C(GF)E + F(GD)H = 37 + 25 = 62	A1	1.1b
C(G)F + E(FGD)H = 25 + 37 = 62	A1	1.1b
C(GD)H + EF = 30 + 12 = 42*	A1	1.1b
\(5x + 246 + 42 = 318\)	M1dep	3.1a
\(x = 6\)	A1	2.2a
	(6)
	(11 marks)

Notes

M1: Correct three pairings of the required four odd nodes (C, E, F and H)

A1: Any one correct pairing and total

A1: Any two correct pairings and totals

A1: All three correct pairings and totals

M1dep: Setting up an equation using the given values and their smallest pairing (dependent on the previous M mark) – must have three totals from application of route inspection

A1: CAO (\(x = 6\))

A2 October 2020 Q1

EdexcelCurrent spec6 marksMinimum Spanning Trees

1. The table below shows the lengths, in km, of the roads in a network connecting seven towns, A, B, C, D, E, F and G.

	A	B	C	D	E	F	G
A	–	24	–	22	35	–	–
B	24	–	25	27	–	–	–
C	–	25	–	33	31	36	26
D	22	27	33	–	–	42	–
E	35	–	31	–	–	37	29
F	–	–	36	42	37	–	40
G	–	–	26	–	29	40	–

(a) By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book. (2)

Diagram 1: the network drawn without the arcs from D: AB 24, AE 35, BC 25, CE 31, CF 36, CG 26, EF 37, EG 29, FG 40; vertex D has no arcs — Diagram 1

(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)

Mark scheme (b)

Scheme	Marks	AO
Kruskal’s algorithm: AD, AB, BC, CG, reject BD, EG, reject CE, reject CD, reject AE, CF (reject EF, reject FG, reject DF)	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

(b) M1: Kruskal’s algorithm – first three arcs correctly chosen and at least one rejection seen at some point

A1: All six arcs selected correctly AD, AB, BC, CG, EG, CF only

A1: CSO – all selections and rejections correct (in correct order and at the correct time)

D1 June 2019 Q3

EdexcelOld spec11 marksMinimum Spanning Trees Shortest Path

	A	B	C	D	E	F	G	H	J
A	–	3	8	5	–	–	–	–	–
B	3	–	4	–	–	–	–	–	–
C	8	4	–	–	9	4	–	–	–
D	5	–	–	–	–	7	4	9	–
E	–	–	9	–	–	4	–	–	7
F	–	–	4	7	4	–	–	8	13
G	–	–	–	4	–	–	–	4	–
H	–	–	–	9	–	8	4	–	7
J	–	–	–	–	7	13	–	7	–

The table above shows the lengths, in metres, of the paths between nine vertices, A, B, C, D, E, F, G, H and J.

(a) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges and state its weight. Draw your minimum spanning tree using the vertices in the answer book. (5)

(b) State whether your minimum spanning tree is unique. Justify your answer. (1)

Minimum spanning tree: AB, BC, CF, EF, AD, DG, GH, with EJ or HJ dashed — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
No – there are two different MST (with a weight of 35) either with EJ or HJ	B1
	(1)

Notes

b1B1: CAO – no (oe) + mention of two different MST with either arc EJ or HJ – as a minimum must mention EJ and HJ – or clearly implied that the final arc in the MST could be replaced with the other arc (e.g. if final arc in MST is EJ they must then say that HJ could replace the final arc in the MST) (do not award this mark if the candidate believes that unique means that there is more than one MST)

Dijkstra working: A 1 0; B 2 3; D 3 5; C 4 7 (8 7); G 5 9; F 6 11 (12 11); H 7 13 (14 13 (19)); E 8 15 (16 15); J 9 20 (24 20 (22)) — Mark scheme (c)

D1 June 2018 Q1

EdexcelOld spec8 marksMinimum Spanning Trees

Figure 1: weighted network with vertices A to J — Figure 1

(a) Define the terms

(i) tree,

(ii) minimum spanning tree. (3)

(b) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for the network shown in Figure 1. You must clearly state the order in which you select the arcs of the tree. (3)

(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree. (2)

Mark scheme (a)

Scheme	Marks
(i) A tree is a connected graph with no cycles	B1
(ii) A minimum spanning tree is a tree that contains all vertices and	B1
the total length of its arcs is as small as possible	B1
	(3)

Notes

In (a) all technical language used must be correct

ai1B1: Connected + no cycle(s) (must contain these two points – do not allow ‘circle’, ‘loop’ etc. for cycle(s)) – for connected allow ‘a graph in which a path exists between each pair of vertices’

aii2B1: Contains all (oe) and either vertices or nodes

aii3B1: Total length (of arcs) is minimised (must contain the two points regarding total and minimised/smallest but need not necessarily mention arcs e.g. ‘smallest total weight’ is sufficient for this mark). However ‘a MST is a tree that contains all the nodes and has the least possible weight’ would score B1B0 in (a)(ii) as they have ‘all the nodes’, but no explicit mention of ‘total’ (or equivalent e.g. ‘sum of’)

Mark scheme (b)

Scheme	Marks
AG, AF, GJ; FB, BC, BD; CH, DE	M1; A1; A1
	(3)

Notes

b1M1: First three arcs (AG, AF, GJ) correctly chosen, or first four nodes (A, G, F, J) correctly chosen in order. If any explicit rejections seen then M1 (max) only. A list of weights only scores M0. Candidates may apply Prim’s in matrix form so the order of the nodes may be seen at the top of a matrix – accept {1,-,-,-,-,3,2,-,4} for the M mark. Allow GJ for JG etc. throughout (b)

b1A1: First six arcs correctly chosen in order (AG, AF, GJ, FB, BC, BD), or all nodes correctly chosen in order (A, G, F, J, B, C, D, H, E). Candidates may apply Prim’s in matrix form so the order of the nodes may be seen at the top of a matrix – accept {1,5,6,7,9,3,2,8,4} – do not condone any missing numbers e.g. the number 9 must be above E

b2A1: CSO (correct solution only) – all arcs correctly stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Misread: Starting at a node other than A scores M1 only in (b) – must have the first three arcs (or four nodes) correct (and in the correct order)

D1 June 2017 Q2

EdexcelOld spec7 marksMinimum Spanning Trees

Figure 3: weighted network of nine computer terminals A to J — Figure 3

Figure 3 represents nine computer terminals, A, B, C, D, E, F, G, H and J, at Pearsonby School. The school wishes to connect them to form a single computer network. The number on each arc represents the cost, in pounds, of connecting the corresponding computer terminals.

(a) Use Prim’s algorithm, starting at B, to find the minimum spanning tree for the computer network. You must clearly state the order in which you select the arcs of your tree. (3)

(b) State the minimum cost of connecting the nine computer terminals. (1)

It is discovered that some computer terminals are already connected. There are already direct connections along BD and FJ, as shown in bold in Diagram 1 in the answer book. It is decided to use these connections.

(c) Use Kruskal’s algorithm to find the minimum spanning tree that includes arcs BD and FJ. You must list the arcs in the order that you consider them. In each case, state whether or not you are adding the arcs to your spanning tree. (3)

Mark scheme (a)

Scheme	Marks
BC, BE, EH, CD; EF, FG; HJ, AG	M1; A1; A1
	(3)

Notes

a1M1: First four arcs correctly chosen in order (BC, BE, EH, CD) or first five nodes correctly chosen in order (B, C, E, H, D). If any explicit rejections seen at any point then M1 (max) only. Allow a list of weights for M1 only (10, 30, 25, 45). Candidates may apply Prim’s in matrix form so the order of the nodes may be seen at the top of a matrix – accept {-, 1, 2, 5, 3, -, -, 4, -} for the M mark. Allow CB for BC etc. throughout (a) and (c)

a1A1: First six arcs correctly chosen in order (BC, BE, EH, CD, EF, FG) or all nine nodes correctly chosen in order (B, C, E, H, D, F, G, J, A). Candidates may apply Prim’s in matrix form so the order of the nodes may be seen at the top of a matrix – accept {9, 1, 2, 5, 3, 6, 7, 4, 8} – do not condone any missing numbers e.g. the number 9 must be above A

a2A1: CSO (correct solution only) – all arcs correctly stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Misread: Starting at a node other than B scores M1 only in (a) – must have the first four arcs (or five nodes) correct (and in the correct order). The most common misread is those that start at A so for M1 only – accept AG, GF, EF, EH or A, G, F, E, H or 75, 70, 52, 25

Mark scheme (c)

Scheme	Marks
BC, EH, BE, reject CD, EF, reject BF, FG, reject HJ, AG (reject BG), (reject DA), (reject BA) (Note BD and FJ are already in the tree)	M1 A1 A1
	(3)
	(7 marks)

Notes

c1M1: Kruskal’s - first three arcs BC, EH, BE,…(or weights 10, 25, 30,…) chosen correctly in order and at least one rejection seen at some point. Ignore any reference to BD and FJ

c1A1: All six arcs BC, EH, BE, EF, FG, AG chosen correctly in order and no additional arcs. Ignore any reference to BD and FJ. Do not accept only a list of weights for this mark

c2A1: CAO all selections and rejections correct in the correct order and at the correct time. Ignore any reference to BD and FJ. Do not accept only a list of weights for this mark – do not need to see explicit rejection of BG, DA and/or BA for this mark

Listing all the arcs in order and then listing those arcs in the tree in the correct order is fine for full marks as this implies that rejections are correct and at the correct time
Listing all the arcs in order and just drawing the MST is M0

No misread if candidates use any other arcs instead of BD and/or FJ

D1 June 2016 Q4

EdexcelOld spec12 marksMinimum Spanning Trees Shortest Path

Figure 3: weighted network of tram tracks with vertices A to K — Figure 3

Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.

(a) Use Dijkstra’s algorithm to find the shortest path from A to F. State your path and its length. (6)

On another day, Sarah wishes to travel from A to F via J.

(b) Find a route of minimal length that goes from A to F via J and state its length. (2)

(c) Use Prim’s algorithm, starting at G, to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree. (3)

(d) State the length, in miles, of the minimum spanning tree. (1)

Dijkstra labelling: A 1 0; B 2 5; E 3 18; C 4 22; K 5 25; D 6 37; J 7 40; H 8 42; G 9 46; F 10 48 — Mark scheme (a)

Mark scheme (c)

Scheme	Marks
Prim starting at G: GF, GH, FJ, DG, JK, EK, BE, AB, CD or GF, GH, FJ, DG, CD, JK, EK, BE, AB	M1 A1 A1
	(3)

Notes

c1M1: First four arcs correctly chosen in order (GF, GH, FJ, DG) or first five nodes correctly chosen in order (G, F, H, J, D). If any explicit rejections seen at any point then M1 (max) only. Do not accept only a list of weights for this mark. Candidates may apply Prim in matrix form so the order of the nodes may be seen at the top of a matrix – accept {-, -, -, 5, -, 2, 1, 3, 4, -} for the M mark

c1A1: First seven arcs correctly chosen in order (GF, GH, FJ, DG, JK, EK, BE or GF, GH, FJ, DG, CD, JK, EK) or all ten nodes correctly chosen in order (G, F, H, J, D, K, E, B, A, C or G, F, H, J, D, C, K, E, B, A) Candidates may apply Prim in matrix form so the order of the nodes may be seen at the top of a matrix – accept {9, 8, 10, 5, 7, 2, 1, 3, 4, 6} or {10, 9, 6, 5, 8, 2, 1, 3, 4, 7} – do not condone any missing numbers e.g. the number 10 must be above either the C or the A

c2A1: CSO – all arcs correctly stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Misread: Starting at a node other than G scores M1 only in (c) – must have the first four arcs (or five nodes) correct (and in the correct order). The most common misread is those that start at A so for M1 only – accept AB, BE, EK, JK or A, B, E, K, J

D1 June 2015 Q5

EdexcelOld spec10 marksMinimum Spanning Trees

Figure 5: weighted network with nine nodes A to J and 17 arcs — Figure 5

The numbers on the 17 arcs in the network shown in Figure 5 represent the distances, in km, between nine nodes, A, B, C, D, E, F, G, H and J.

(a) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)

(b) Starting at G, use Prim’s algorithm to find a minimum spanning tree. You must clearly state the order in which you select the arcs of your tree. (3)

A connected graph V has \(n\) nodes. The sum of the degrees of all the nodes in V is \(m\). The graph T is a minimum spanning tree of V.

(d)

(i) Write down, in terms of \(m\), the number of arcs in V.

(ii) Write down, in terms of \(n\), the number of arcs in T.

(iii) Hence, write down an inequality, in terms of \(m\) and \(n\), comparing the number of arcs in T and V. (3)

Mark scheme (a)

Scheme	Marks
Kruskal: BC, AB, (not AC), DE, CD, DF, (not \(\begin{smallmatrix}\text{BF}\\ \text{CE}\end{smallmatrix}\)), EJ, FH, (not HJ), (not BD), GH	M1 A1 A1
	(3)

Notes

a1M1: Kruskal’s – first four arcs BC, AB, DE, CD,…(or weights 6, 7, 10, 11, …) chosen correctly in order and at least one rejection seen at some point

a1A1: All eight arcs BC, AB, DE, CD, DF, EJ, FH, GH (or weights 6, 7, 10, 11, 13, 15, 16, 20) chosen correctly in order and no additional arcs

a2A1: CSO All selections and rejections correct (in correct order and at the correct time) – do not accept weights only for this mark

Listing all the arcs in order and then listing those arcs in the tree in the correct order is fine for full marks (this implies that rejections are correct and at the correct time)
Listing all the arcs in order and just drawing the MST is M0

Mark scheme (b)

Scheme	Marks
Prim: GH, FH, DF, DE; CD, BC; AB, EJ	M1; A1; A1
	(3)

Notes

b1M1: First four arcs correctly chosen in order (GH, FH, DF, DE, … or weights 20, 16, 13, 10,…) or first five nodes{G, H, F, D, E,…} correctly chosen in order. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of a matrix/table {-, -, -, 4, 5, 3, 1, 2, - }

a1A1: Prim’s - first six arcs correctly chosen in order (GH, FH, DF, DE, CD, BC,… or weights 20, 16, 13, 10, 11, 6,…) or all nine nodes{G, H, F, D, E, C, B, A, J} correctly chosen in order.. Order of nodes may be seen at the top of a matrix so for the first two marks accept {8, 7, 6, 4, 5, 3, 1, 2, 9} (no missing numbers)

a2A1: CSO - all arcs correctly stated and chosen in the correct order. They must be considering arcs for this final mark (do not accept a list of the weights of each arc, nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Misread: Starting at a node other than G scores M1 only – must have the first four arcs (or five nodes or numbers) correct (and in the correct order) – condone rejections seen for this mark

Starting at	Minimum arcs required for M1	Nodes	Order
A	AB BC CD DE	ABCDE	12345----
B	BC AB CD DE	BCADE	31245----
C	CB AB CD DE	CBADE	32145----
D	DE CD BC AD	DECBA	54312----
E	ED CD BC AD	EDCBA	54321----
F	FD DE CD BC	FDECB	-54231---
H	HF DF DE CD	HFDEC	--5342-1-
J	JE DE CD BC	JEDCB	-5432---1

Mark scheme (d)

Scheme	Marks
(i) \(\dfrac{m}{2}\)	B1
(ii) \(n - 1\)	B1
(iii) \(m \geqslant 2(n - 1)\) (oe)	B1
	(3)
	(10 marks)

Notes

diB1: CAO (oe e.g. \(0.5m\))

diiB1: CAO

diiiB1: CAO (oe, for example, \(n - 1 \leqslant \dfrac{1}{2}m\)) – must include correct bracketing (if required) – do not accept strict inequality

D1 June 2014 Q1

EdexcelOld spec5 marksMinimum Spanning Trees

	Art	Biology	Chemistry	Drama	English	French	Graphics
Art (A)	–	61	93	73	50	48	42
Biology (B)	61	–	114	82	83	63	58
Chemistry (C)	93	114	–	59	94	77	88
Drama (D)	73	82	59	–	89	104	41
English (E)	50	83	94	89	–	91	75
French (F)	48	63	77	104	91	–	68
Graphics (G)	42	58	88	41	75	68	–

The table shows the travelling times, in seconds, to walk between seven departments in a college.

(a) Use Prim’s algorithm, starting at Art, to find the minimum spanning tree for the network represented by the table. You must clearly state the order in which you select the edges of your tree. (3)

(b) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. (1)

Mark scheme (a)

Scheme	Marks
AG, DG, AF; AE BG; CD	M1 A1 A1
	(3)

Notes

a1M1 First three arcs correctly chosen in order (AG, DG, AF, … or weights 42, 41, 48, …) or first four nodes correctly chosen in order. {A.G,D,F,…} If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of the matrix {1, -, -, 3, -, 4, 2} so please check the top of the matrix carefully.

a1A1 First five arcs correctly chosen in order (AG, DG, AF, AE, BG or weights 42, 41, 48, 50, 58,…) or all seven nodes correctly chosen in order. {A,G,D,F,E,B,C}. Order of nodes may be seen at the top of the matrix so for the first two marks accept {1, 6, 7, 3, 5, 4, 2} (do not condone any missing numbers e.g. the number 7 must be above C).

a2A1 CSO - all arcs correct and chosen in the correct order. They must be considering arcs for this final mark (do not accept a list of the weights of each arc, nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen).

Misread: Starting at a node other than A scores M1 only – must have the first three arcs (or four nodes or numbers) correct (and in the correct order).

Starting at	Minimum arcs required for M1	Nodes	Order
A	AG DG AF	AGDF(EBC)	1(6)(7)3(5)42
B	BG DG AG	BGDA(FEC)	41(7)3(6)(5)2
C	CD DG AG	CDGA(FEB)	4(7)12(6)(5)3
D	DG AG AF	DGAF(EBC)	3(6)(7)1(5)42
E	EA AG DG	EAGD(FBC)	2(6)(7)41(5)3
F	FA AG DG	FAGD(EBC)	2(6)(7)4(5)13
G	GD AG AF	GDAF(EBC)	3(6)(7)2(5)41

D1 June 2013 (R) Q2

EdexcelOld spec8 marksMinimum Spanning Trees

	A	B	C	D	E	F
A	–	85	110	160	225	195
B	85	–	100	135	180	150
C	110	100	–	215	200	165
D	160	135	215	–	235	215
E	225	180	200	235	–	140
F	195	150	165	215	140	–

The table shows the average journey time, in minutes, between six towns, A, B, C, D, E and F.

(a) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you selected them. (3)

(b) Draw your tree using the vertices given in Diagram 1 in the answer book. (1)

Kruskal’s algorithm may also be used to find a minimum spanning tree.

(d) State three differences between Prim’s algorithm and Kruskal’s algorithm. (3)

Mark scheme (a)

Scheme	Marks
AB(85), BC(100), BD(135); BF(150), EF(140).	M1 A1; A1
	(3)

Notes

a1M1 Prim’s – first three arcs correctly chosen or first four nodes correctly chosen, in order.{A, B, C, D,….}. Any rejections seen during selection is M0. Order of nodes may be seen across the top of the matrix {1, 2, 3, 4, –, –}

a1A1 First four arcs correctly chosen or all six nodes correctly chosen {A, B, C, D, F, E}. Order of nodes may be seen across the top of the matrix {1, 2, 3, 4, 6, 5}

a2A1 CSO (must be considering arcs for this final mark).

Misread: Starting at a node other than A scores M1 only – must have the first three arcs (or four nodes or numbers) correct.

Starting at	Minimum arcs required for M1	Nodes	order
A	AB BC BD	ABCD(FE)	1234(65)
B	AB BC BD	BACD(FE)	2134(65)
C	BC AB BD	CBAD(FE)	3214(65)
D	BD AB BC	DBAC(FE)	3241(65)
E	EF BF AB	EFBA(CD)	43(56)12
F	EF BF AB	FEBA(CD)	43(56)21

Mark scheme (d)

Scheme	Marks
E.g. (any three) Kruskal starts with the shortest arc, Prim starts with any node. It is necessary to check for cycles when using Kruskal, not with Prim. When using Prim the ‘growing’ tree is always connected. When using Kruskal arcs are considered in ascending order of weight. Prim can be used when the network is given in matrix form. Prim adds nodes to the growing tree, Kruskal adds arcs. Other correct statements also get credit	B1 B1 B1
	(3)
	(8 marks)

Notes

d1B1 One correct statement.

d2B1 A second correct statement.

d3B1 A third correct statement.

In part (d) all technical language must be correct (so do not condone point for vertex/node etc.)

D1 June 2013 Q3

EdexcelOld spec10 marksMinimum Spanning Trees

	A	B	C	D	E	F
A	-	15	6	9	-	-
B	15	-	12	-	14	-
C	6	12	-	7	10	-
D	9	-	7	-	11	17
E	-	14	10	11	-	5
F	-	-	-	17	5	-

The table shows the times, in days, needed to repair the network of roads between six towns, A, B, C, D, E and F, following a flood.

(a) Use Prim’s algorithm, starting at A, to find the minimum connector for this network. You must list the arcs that form your tree in the order that you selected them. (3)

(b) Draw your minimum connector using the vertices given in Diagram 1 in the answer book. (1)

(c) Add arcs from D, E and F to Diagram 2 in the answer book, so that it shows the network of roads shown by the table. (2)

(d) Use Kruskal’s algorithm to find the minimum connector. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum connector. (3)

(e) State the minimum time needed, in days, to reconnect the six towns. (1)

Mark scheme (a)

Scheme	Marks
AC, CD, CE; EF; BC	M1; A1; A1
	(3)

Notes

Accept the weight of each arc to represent the arcs (as each value is unique).

a1M1 Prim’s – first three arcs correctly chosen or first four nodes correctly chosen {A, C, D, E, ...}. Any rejections seen during selection M0. Order of nodes may be seen at the top of the matrix {1, – , 2, 3, 4, –}

a1A1 First four arcs correctly chosen or all six nodes correctly chosen {A, C, D, E, F, B}. Order of nodes may be seen at the top of the matrix {1, 6, 2, 3, 4, 5}

a2A1 CSO (must be considering arcs for this final mark).

Misread: Starting at a node other than A scores M1 only – must have the first three arcs (or four nodes or numbers) correct.

Starting at	Minimum arcs required for M1	Nodes	Order
A	AC CD CE	ACDE(FB)	1(6)234(5)
B	BC AC CD	BCAD(EF)	3124(56)
C	AC CD CE	CADE(FB)	2(6)134(5)
D	CD AC CE	DCAE(FB)	3(6)214(5)
E	EF CE AC	EFCA(DB)	4(6)3(5)12
F	EF CE AC	FECA(DB)	4(6)3(5)21

Network: AB 15, AC 6, AD 9, BC 12, BE 14, CD 7, CE 10, DE 11, DF 17, EF 5 — Mark scheme (c)

Mark scheme (d)

Scheme	Marks
EF, AC, CD, reject AD, CE, reject DE, CB	M1 A1 A1
	(3)

Notes

d1M1 Kruskal’s – first three arcs correctly chosen and at least one rejection seen at some point.

d1A1 All five arcs selected correctly EF, AC, CD, CE, CB.

d2A1 CAO All selections and rejections correct (in correct order and at the correct time).

Listing all the arcs in order and then listing those arcs in the tree in the correct order is fine for full marks (this implies that rejections are correct and at the correct time)
Listing all the arcs in order and just drawing the MST is M0

SC for part (d): If the network diagram is incorrect in part (c) and it is clear that the candidate has used part (c) (instead of the original table) to answer part (d) then award M1 only for the first three arcs correctly chosen and at least one rejection seen at some point provided their network is connected and contains at least nine arcs.

D1 January 2013 Q5

EdexcelOld spec15 marksMinimum Spanning Trees Route Inspection

Figure 5: network of roads A to J with lengths in km — Figure 5

[The weight of the network is 379]

Figure 5 represents the roads in a highland wildlife conservation park. The vertices represent warden stations. The number on each arc gives the length, in km, of the corresponding road.

During the winter months the park is closed. It is only necessary to ensure road access to the warden stations.

(a) Use Prim’s algorithm, starting at A, to find a minimum connector for the network in Figure 5. You must state the order in which you include the arcs. (3)

(b) Given that it costs £80 per km to keep the selected roads open in winter, calculate the minimum cost of ensuring road access to all the warden stations. (2)

At the end of winter, Ben inspects all the roads before the park re-opens. He needs to travel along each road at least once. He will start and finish at A, and wishes to minimise the length of his route.

(c) Use the route inspection algorithm to find the roads that will be traversed twice. You must make your method and working clear. (6)

(d) Find the length of the shortest inspection route. (1)

If Ben starts and finishes his inspection route at different warden stations, a shorter inspection route is possible.

(e) Determine the two warden stations Ben should choose as his starting and finishing points in order that his route has minimum length. Give a reason for your answer and state the length of the route. (3)

Mark scheme (a)

Scheme	Marks
AC (32) CF (14) DF (12) EF (17); BE (15) FI(18); IJ (10) GJ (9) DH (19)	M1 A1; A1
	(3)

Notes

Accept the weight of each arc to represent the arcs (as each value is unique).

a1M1 First four arcs correctly chosen or first five nodes correctly chosen (A, C, F, D, E, …). Any rejections seen during selection scores M0. Order of nodes may be seen at the top of a matrix.

a1A1 First six arcs correctly chosen or all nodes correctly chosen (A, C, F, D, E, B, I, J, G, H). Order of nodes may be seen at the top of a matrix.

a2A1 CSO (must be considering arcs for this final mark).

Misread in (a): Starting at a node other than A scores M1 only – must have the first four arcs (or five nodes or numbers) correct.

Starting at	Minimum Arcs required for M1 only	Nodes	Order
B	BE,EF,DF,CF	B, E, F, D, C	(10)15423(8967)
C	CF,DF,EF,BE	C, F, D, E, B	(10)51342(8967)
D	DF,CF,EF,BE	D, F, C, E, B	(10)53142(8967)
E	BE,EF,DF,CF	E, B, F, D, C	(10)25413(8967)
F	DF,CF,EF,BE	F, D, C, E, B	(10)53241(8967)
G	GJ,IJ,FI,DF	G, J, I, F, D	(10)(86)5(7)41(9)32
H	DH,DF,CF,EF	H, D, F, C, E	(10)(6)4253(9)1(78)
I	IJ,GJ,FI,DF	I, J, G, F, D	(10)(86)5(7)43(9)12
J	GJ,IJ,FI,DF	J, G, I, F, D	(10)(86)5(7)42(9)31

Mark scheme (b)

Scheme	Marks
\(146 \times 80 =\) (£) 11 680	M1 A1
	(2)

Notes

b1M1 \(80 \times\) their MST weight. Accept a value in the interval \([114, 178] \times 80\) for this mark. If no working is seen then M0 unless answer is correct.

b1A1 CAO (11680 with no working scores both marks).

Mark scheme (c)

Scheme	Marks
BF + GH = 32 + 40 = 72 BG + FH = 39 + 25 = 64* BH + FG = 57 + 37 = 94	M1 A3,2,1,0
Roads BE, EG and FH need repeating	A1ft A1
	(6)

Notes

c1M1 Three distinct pairings of their four odd nodes.

c1A1 Any one row correct including pairing and total.

c2A1 Any two rows correct including pairing and total.

c3A1 All three rows correct including pairing and total.

c4A1ft Their smallest arcs repeated (e.g. accept BEG or BG via E but not just BG). BEG (or e.g. BG via E) could appear in their working.

c5A1 CAO BE, EG and FH. Accept BEG or BG via E (could appear in working) but not just BG.

Mark scheme (e)

Scheme	Marks
Ben should choose to repeat FH (25) since this is the shortest.	M1
He should choose B and G as his start and finish vertices	A1
Route length is 379 + 25 = 404 (km)	A1
	(3)
	(15 marks)

Notes

e1M1 FH (or 25) specifically identified as least.

e1A1 B and G identified as the start and finish nodes.

e2A1 404 CAO (condone lack of (or incorrect) units throughout).

D1 June 2012 Q3

EdexcelOld spec7 marksMinimum Spanning Trees

	A	B	C	D	E	F	G
A	-	15	19	-	22	24	-
B	15	-	-	8	13	-	-
C	19	-	-	12	-	16	-
D	-	8	12	-	10	-	18
E	22	13	-	10	-	15	16
F	24	-	16	-	15	-	17
G	-	-	-	18	16	17	-

The table shows the lengths, in km, of a network of roads between seven villages, A, B, C, D, E, F and G.

(a) Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights. (2)

(d) State the weight of the minimum spanning tree. (1)

Arcs from D: DB 8, DE 10, DC 12, DG 18 — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
BD(8), DE(10), CD(12), reject BE(13), {EF(15), AB(15)}, {EG(16), reject CF(16)} reject remainder of arcs.	M1 1A1 2A1
	(3)

Notes

b1M1 First three arcs correctly chosen and at least one rejection seen at some point. (Kruskal not Prim.)

b1A1 First five arcs selected correctly; BD, DE, CD, then (in either order) EF, AB

b2A1 CAO including necessary rejections.

D1 January 2012 Q1

EdexcelOld spec8 marksMinimum Spanning Trees

Figure 1: network with arcs AB 25, AD 19, BC 21, BE 30, CD 11, CF 15, DF 16, DH 39, EF 33, EG 13, FG 37, FH 40, HG 57 — Figure 1

Figure 1 represents the distances, in km, between eight vertices, A, B, C, D, E, F, G and H in a network.

(a) Use Kruskal’s algorithm to find the minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)

(b) Starting at A, use Prim’s algorithm to find the minimum spanning tree. You must clearly state the order in which you selected the arcs of your tree. (3)

(d) State the weight of the tree. (1)

Mark scheme (a)

Scheme	Marks
DC, EG, CF, reject DF; AD, BC, reject AB, BE, reject EF and FG, DH	M1; A1 A1
	(3)

Notes

a1M1: First three arcs correctly chosen and DF rejected. Accept weights for all 3 marks.

Special case: If all 7 arcs, in correct order, but no rejections seen at all, then award M1 only.

a1A1: All arcs/weights in tree selected correctly at correct time.

a2A1: All rejections correct and at the right time.

Mark scheme (b)

Scheme	Marks
AD, DC, CF, CB; BE; EG, DH	M1;A1; A1
	(3)

Notes

b1M1: First four arcs/weights correctly chosen, or first five nodes ADCFB chosen in order.

Special case : If Prim but not starting at A please send to review.

b1A1: First five arcs/weights correctly chosen, or all nodes in order A, D, C, F, B, E, G, H.

b2A1: CSO (must be arcs/weights). E.g no ‘reject’ arcs

D1 June 2011 Q2

EdexcelOld spec8 marksGraphs & Networks Minimum Spanning Trees

Figure 1: network with arcs AC 14, AB 10, BC 13, CF 18, CE 17, BF 20, BE 15, BD 14, DF 19, EF 18, DE 12 — Figure 1

(a) Define the terms

(i) tree,

(ii) minimum spanning tree.

(3)

(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network shown in Figure 1. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)

(d) State whether your minimum spanning tree is unique. Justify your answer. (1)

Mark scheme (a)

Scheme	Marks
(i) A tree is a connected graph with no cycles/circuit	B1
(ii) A minimum spanning tree is a tree that contains all vertices and	B1
the total length of its arcs (weight of tree) is as small as possible.	B1
	(3)

Notes

(a)1B1 Connected + no cycles

2B1 Contains all vertices

3B1 Total length of arcs used minimised or minimum weight. (Not shortest/smallest etc.)

Mark scheme (b)

Scheme	Marks
AB, DE, BC; \(\left\{\begin{matrix}\text{reject AC}\\ \text{BD}\end{matrix}\right\}\) reject BE, reject CE, use either EF or CF	M1; A1 A1
	(3)

Notes

(b)M1 First four arcs selected correctly in correct order.

1A1 Arcs selected correctly at correct time

2A1 Rejections correct and at correct time

Mark scheme (d)

Scheme	Marks
No, there are two solutions since either EF or CF should be used.	B1
	(1)
	(8 marks)

Notes

(d)B1 CAO - mark explanation must specify two arcs of 18 or two 18’s or ref to EF and CF

D1 January 2011 Q3

EdexcelOld spec10 marksMinimum Spanning Trees

Figure 2: network with arcs AB 48, AI 53, BC 39, BI 42, CD 23, CI 19, DI 26, DE 38, EI 34, EF 28, FI 31, FG 43, GI 45, HI 39, HG 46 — Figure 2

(a) Use Kruskal’s algorithm to find a minimum spanning tree for the network shown in Figure 2. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)

(b) Starting at A, use Prim’s algorithm to find a minimum spanning tree for the network in Figure 2. You must clearly state the order in which you include the arcs in your tree. (3)

(c) Draw a minimum spanning tree for the network in Figure 2 using the vertices given in Diagram 1 of the answer book. State the weight of the minimum spanning tree. (2)

A new spanning tree is required which includes the arcs DI and HG, and which has the lowest possible total weight.

(d) Explain which algorithm you would choose to complete the tree, and how the algorithm should be adapted. (You do not need to find the tree.) (2)

Mark scheme (a)

Scheme	Marks
CI CD (not DI) EF FI (not EI not DE) \(\left\{\begin{matrix}\text{BC}\\ \text{HI}\end{matrix}\right\}\) (not BI) GF	M1 A1
(not GI not HG) AB	A1
	(3)

Notes

1M1: Kruskal’s algorithm – first 4 arcs selected chosen correctly.

1A1: All eight non-rejected arcs chosen correctly.(Working seen in (a))

2A1: All rejections correct and in correct order and at correct time.

Mark scheme (b)

Scheme	Marks
AB BC CI CD FI EF IH FG	M1 A1 A1
	(3)

Notes

1M1: Prim’s algorithm – first four arcs chosen correctly, in order, or first five nodes chosen correctly, in order.{A, B,C,I, D} (arcs not arc lengths)

1A1: First six arcs chosen correctly; all 9 nodes chosen correctly, in order.{A,B,C,I,D,F,E,H,G}[1 2 3 5 7 6 9 8 4]

2A1: cso

Mark scheme (d)

Scheme	Marks
Start off the tree with DI and HG and then apply Kruskal’s algorithm	B2,1, 0
	(2)
	(10 marks)

Notes

1B1: Kruskal’s algorithm + some argument

2B1: Kruskal’s algorithm + start with the two arcs. (o.e)

D1 June 2010 Q2

EdexcelOld spec9 marksMinimum Spanning Trees

Figure 1: network with arcs AC 30, AB 31, CF 29, CE 24, CD 22, DE 18, BD 24, DH 34, BH 38, EF 28, EG 26, FG 21, GH 33 — Figure 1

Figure 1 represents the distances, in metres, between eight vertices, A, B, C, D, E, F, G and H, in a network.

(a) Use Kruskal’s algorithm to find a minimum spanning tree for the network.
You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)

(b) Complete Matrix 1 in your answer book, to represent the network. (2)

(c) Starting at A, use Prim’s algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs. (3)

(d) State the weight of the minimum spanning tree. (1)

Mark scheme (a)

Scheme	Marks
DE GF DC \(\left\{\begin{matrix}\text{not CE}\\ \text{BD}\end{matrix}\right\}\) EG (not EF not CF) AC (not AB) GH	M1 A1 A1
	(3)

Notes

1M1: Kruskal’s algorithm – first 4 arcs selected chosen correctly.

1A1: All seven non-rejected arcs chosen correctly.

2A1: All rejections correct and in correct order and at correct time.

Mark scheme (c)

Scheme	Marks
AC CD DE BD GE GF GH	M1 A1 A1
	(3)

Notes

1M1: Prim’s algorithm – first four arcs chosen correctly, in order, or first five nodes chosen correctly, in order.{A,C,D,E,B….}

1A1: First six arcs chosen correctly or all 8 nodes chosen correctly, in order. {A,C,D,E,B,G,F,H}

2A1: All correct and arcs chosen in correct order.

Starting at	Minimum arcs required for M1	Nodes	order
A	AC CD DE DB	ACDEB(GFH)	15234(768)
B	BD DE DC	BDEC(GFAH)	(7)1423(658)
C	CD DE DB	CDEB(GFAH)	(7)4123(658)
D	DE DC DB	DECB(GFAH)	(7)4312(658)
E	ED DC DB	EDCB(GFAH)	(7)4321(658)
F	FG GE ED DC DB	FGEDCB(AH)	(7)654312(8)
G	GF GE ED DC DB	GFEDCB(AH)	(7)654321(8)
H	HG GF GE	HGFE(DCBA)	(8765)4321

D1 January 2010 Q2

EdexcelOld spec9 marksGraphs & Networks Minimum Spanning Trees

2. Prim’s algorithm finds a minimum spanning tree for a connected graph.

(a) Explain the terms

(i) connected graph,

(ii) tree,

(iii) spanning tree.

(3)

(b) Name an alternative algorithm for finding a minimum spanning tree. (1)

	Cambridge	London	Norwich	Oxford	Portsmouth	Salisbury	York
Cambridge (C)	-	60	62	81	132	139	156
London (L)	60	-	116	56	74	88	211
Norwich (N)	62	116	-	144	204	201	181
Oxford (O)	81	56	144	-	84	63	184
Portsmouth (P)	132	74	204	84	-	43	269
Salisbury (S)	139	88	201	63	43	-	248
York (Y)	156	211	181	184	269	248	-

Figure 2

Figure 2 shows the distances by road, in miles, between seven cities.

(c)

(i) Use Prim’s algorithm, starting at London, to find the minimum spanning tree for these cities. You must clearly state the order in which you selected the edges of your tree, and the weight of the final tree.

(ii) Draw your tree using the vertices given in Diagram 2 in the answer book.

(5)

Mark scheme (a)

Scheme	Marks
(i) All pairs of vertices connected by a path, but not describing complete graph.	B1
(ii) No cycles	B1
(iii) All nodes connected (accept definition of minimum spanning tree)	B1
	(3)

Tree: Y–C, C–N, C–L, L–O, O–S, S–P — Mark scheme (c)

D1 June 2009 Q1

EdexcelOld spec5 marksMinimum Spanning Trees

	A	B	C	D	E	F
A	-	135	180	70	95	225
B	135	-	215	125	205	240
C	180	215	-	150	165	155
D	70	125	150	-	100	195
E	95	205	165	100	-	215
F	225	240	155	195	215	-

The table shows the lengths, in km, of potential rail routes between six towns, A, B, C, D, E and F.

(a) Use Prim’s algorithm, starting from A, to find a minimum spanning tree for this table. You must list the arcs that form your tree in the order that they are selected. (3)

(b) Draw your tree using the vertices given in Diagram 1 in the answer book. (1)

Mark scheme (a)

Scheme	Marks
AD, AE, DB; DC, CF	M1 A1; A1
	(3)

Notes

(a) 1M1: Using Prim – first 2 arcs probably but condone starting from another vertex.

1A1: first three arcs correct

2A1: all correct.

Apply the misread rule, if not listing arcs or not starting at A.
So for M1 (only)
Accept numbers across the top (condoning absence of 6)
Accept full vertex listing
Accept full arc listing starting from vertex other than A

[AD AE DB DC CF]	{1 4 5 2 3 6}	ADEBCF
BD AD AE CD CF	{3 1 5 2 4 6}	BDAECF
CD AD AE BD CF	{3 5 1 2 4 6}	CDAEBF
DA AE DB CD CF	{2 4 5 1 3 6}	DAEBCF
EA AD DB DC CF	{2 4 5 3 1 6}	EADBCF
FC CD AD AE BD	{4 6 2 3 5 1}	FCDAEB

D1 January 2009 Q2

EdexcelOld spec8 marksMinimum Spanning Trees

	A	B	C	D	E	F
A	-	24	-	-	23	22
B	24	-	18	19	17	20
C	-	18	-	11	14	-
D	-	19	11	-	13	-
E	23	17	14	13	-	21
F	22	20	-	-	21	-

The table shows the distances, in metres, between six vertices, A, B, C, D, E and F, in a network.

(a) Draw the weighted network using the vertices given in Diagram 1 in the answer booklet. (3)

(b) Use Kruskal’s algorithm to find a minimum spanning tree. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree. (3)

Mark scheme (b)

Scheme	Marks
CD, DE, reject CE, BE, reject BC, reject BD, BF, reject EF, AF 11 13 14 17 18 19 20 21 22	M1 A1 A1
	(3)

Notes

(b) 1M1: First three arcs correctly chosen

1A1: All used acrs selected correctly

2A1: All rejected arcs selected in correct order

D1 June 2008 Q4

EdexcelOld spec8 marksMinimum Spanning Trees

Figure 4: network with vertices A to G and arc weights — Figure 4

(a) State two differences between Kruskal’s algorithm and Prim’s algorithm for finding a minimum spanning tree. (2)

(b) Listing the arcs in the order that you consider them, find a minimum spanning tree for the network in Figure 4, using

(i) Prim’s algorithm,

(ii) Kruskal’s algorithm. (6)

Mark scheme (a)

Scheme	Marks
e.g. Prims starts with any vertex, Kruskal starts with the shortest arc. It is not necessary to check for cycles when using Prim. Prims adds nodes to the growing tree, Kruskal adds arcs. The tree ‘grows’ in a connected fashion when using Prim. Prim can be used when data in a matrix form. Other correct statements also get credit.	B2, 1, 0
	(2)

Notes

(a) 1B1: Generous one correct difference. If bod give B1

2B1: Generous two distinct, correct differences.

Minimum spanning tree: AB 27, AC 25, CF 18, FD 20, DE 19, DG 22 — Mark scheme (b)

D1 January 2008 Q2

EdexcelOld spec10 marksAlgorithms Minimum Spanning Trees

(a)

The list of numbers shown above is to be sorted into ascending order. Apply quick sort to obtain the sorted list. You must make your pivots clear. (5)

Figure 3: network of paths with vertices A to I and arc lengths in metres — Figure 3

Figure 3 represents a network of paths in a park. The number on each arc represents the length of the path in metres.

(b) Using your answer to part (a) and Kruskal’s algorithm, find a minimum spanning tree for the network in Figure 3. You should list the arcs in the order in which you consider them and state whether you are adding it to your minimum spanning tree. (4)

Quick sort passes with pivots circled and fixed pivots boxed, ending 7 9 11 14 15 16 17 18 20 21 23 — Mark scheme (a)

Alternative quick sorts using the middle left and the first item as pivots — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
CF ✓
GI ✓	M1
{ BC or BF – accept one, reject one { CD ✓	A1
EF ✓
DF ✗	A1
HI ✓
BE ✗
AB ✓
AC ✗	A1
EG ✓
Tree complete
	(4)

Notes

(b) 1M1 Using Kruskal – CF then GI

1A1 First 4 arcs chosen correctly

2A1 All arcs chosen correctly (condone lack of rejection here)

3A1 All correct including rejections

D1 June 2007 Q5

EdexcelOld spec7 marksMinimum Spanning Trees

	M	A	B	C	D	E
M	–	215	170	290	210	305
A	215	–	275	100	217	214
B	170	275	–	267	230	200
C	290	100	267	–	180	220
D	210	217	230	180	–	245
E	305	214	200	220	245	–

The table shows the cost, in pounds, of linking five automatic alarm sensors, A,B,C,D and E, and the main reception, M.

(a) Use Prim’s algorithm, starting from M, to find a minimum spanning tree for this table of costs. You must list the arcs that form your tree in the order that they are selected. (3)

(b) Draw your tree using the vertices given in Diagram 1 in the answer book. (1)

(d) Explain why it is not necessary to check for cycles when using Prim’s algorithm. (2)

Mark scheme (d)

Scheme	Marks
(A cycle is formed when an arc is used that connects two vertices already connected to each other in the tree) Prim’s algorithm always selects arcs that bring a vertex not in the tree into the tree, so cycles can’t happen	B2, 1, 0
	(2)
	(7 marks)

D1 January 2006 Q2

EdexcelOld spec15 marksMinimum Spanning Trees Route Inspection

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
\(A\)	–	48	117	92	–	–	–
\(B\)	48	–	–	–	–	63	55
\(C\)	117	–	–	28	–	–	85
\(D\)	92	–	28	–	58	132	–
\(E\)	–	–	–	58	–	124	–
\(F\)	–	63	–	132	124	–	–
\(G\)	–	55	85	–	–	–	–

The table shows the lengths, in metres, of the paths between seven vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\) in a network N.

(a) Use Prim’s algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. You must clearly state the order in which you selected the edges of your tree, and the weight of your final tree. Draw your tree using the vertices given in Diagram 1 in the answer book. (5)

(b) Draw N using the vertices given in Diagram 2 in the answer book. (3)

(c) Solve the Route Inspection problem for N. You must make your method of working clear. State a shortest route and find its length.
(The weight of N is 802.) (7)

Mark scheme (c)

Scheme	Marks
\(AB + CF = 48 + 160 = 208\)	M1 A1
\(AC + BF = 117 + 63 = 180\ *\)	A1
\(AF + BC = 111 + 140 = 251\)	A1 (4)
e.g. \(ABFBGCACDEFDA\)	A1
length \(802 + 180 = 982\) m	M1 A1ft (3)
	(7)
	(15 marks)

Notes

In the scheme the repeated arcs \(BF\) and \(AC\) are marked in the route.

D1 January 2005 Q3

EdexcelOld spec8 marksMinimum Spanning Trees

Figure 2: weighted network on A to J — Figure 2

The network in Figure 2 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.

(a) Find a minimum spanning tree for the network in Figure 2, showing clearly the order in which you selected the arcs for your tree, using

(i) Kruskal’s algorithm, (3)

(ii) Prim’s algorithm, starting from \(A\). (3)

Given that footpaths are already in place along \(AB\) and \(FI\) and so should be included in the spanning tree,

(b) explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.) (2)

Mark scheme (a)

Scheme	Marks
(i) \(FH, AD, DE, CE\), (not \(DC\)), \(\left\{\begin{matrix}BC\\EG\end{matrix}\right.\), (not \(AC\)), \(CF, HI\), (not \(FI\)), \(IJ\) stop	M1 A1 A1
	(3)
(ii) \(AD, DE, EC\), \(\left\{\begin{matrix}BC\\EG\end{matrix}\right.\), \(CF, FH, HI, IJ\) stop.	M1 A1 A1
	(3)

Minimum Spanning Trees

Edexcel

Edexcel · Old spec

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Notes

Additional notes for (a)

Notes

Notes

Notes

Notes