Minimum Spanning Trees | Edexcel A Level Further Maths: Decision Maths 1 Exam Questions 2017

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.

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?

Did this page help you?

3 marks

	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.

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.

How did you do?

1 mark

State the weight of the minimum spanning tree.

How did you do?

2 marks

	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.

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.

How did you do?

2 marks

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

How did you do?

Did this page help you?

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

Minimum Spanning Trees (Edexcel A Level Further Maths: Decision Maths 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	–