A LevelFurther MathsEdexcelDecision 1Exam QuestionsAlgorithms on GraphsMinimum Spanning Trees

Minimum Spanning Trees (Edexcel A Level Further Maths: Decision 1): Exam Questions

Exam code: 9FM0

40 mins4 questions

2 marks

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	–

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

How did you do?

3 marks

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.

How did you do?

1 mark

State the weight of the minimum spanning tree.

How did you do?

Was this exam question helpful?

5 marks

A network graph with nodes A-J connected by weighted edges, showing values like 34, 42, 50. Total weight is 423. Nodes are labelled with letters.

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.

(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.

How did you do?

3 marks

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.

How did you do?

2 marks

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

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.

How did you do?

2 marks

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

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

How did you do?

1 mark

Interpret the route in terms of the actual towns visited.

How did you do?

Was this exam question helpful?

3 marks

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	–

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.

How did you do?

1 mark

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

How did you do?

1 mark

Draw the minimum spanning tree using the vertices given in Diagram 1 below.

Circular diagram with ten labelled points: A to J, placed equidistantly. Points are marked by dots, each labelled with a letter. Titled 'Diagram 1'.

How did you do?

1 mark

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

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

How did you do?

3 marks

(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.

How did you do?

1 mark

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

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.

How did you do?

2 marks

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

How did you do?

1 mark

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

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.

How did you do?

Was this exam question helpful?

More Revision Notes you might like

View all topics

Algorithms & Graph Theory

Algorithms

Graphs

Algorithms on Graphs

Minimum Spanning Trees

Shortest Path Algorithms

The Route Inspection Algorithm

The Travelling Salesman Problem

Critical Path Analysis

Critical Path Analysis

Linear programming

Linear Programming (LP) problems

Graphical Solution of LP problems

Simplex Algorithm

Minimum Spanning Trees (Edexcel A Level Further Maths: Decision 1): Exam Questions

	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	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	–

	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	–

	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	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	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	–

	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	–

	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	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	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	–

	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	–

	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	–