Algorithms on graphs II questions

Practice questions covering algorithms on graphs ii from this specification. Attempt the questions below; real-paper references for this topic are being imported.

Questions to attempt

6 questions on Algorithms on graphs II, each with its mark scheme and worked method. Reveal the answer when you have had a go.

D1-3.1 · Algorithm for finding the shortest route around a network, travelling along every edge at least once and ending at the start vertex (the Route Inspection Algorithm).
Q1
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
1.
A network has vertices $A$ to $F$ and arcs $AB=7$ , $AC=9$ , $AF=12$ , $BC=5$ , $BD=8$ , $CD=6$ , $CE=10$ , $DE=4$ , $DF=14$ , $EF=11$ . Find the odd vertices, the total weight, and the length of the shortest closed route covering every arc.
(7)
(Total for Question 1 is 7 marks)
D1-3.1 · Algorithm for finding the shortest route around a network, travelling along every edge at least once and ending at the start vertex (the Route Inspection Algorithm).
Q2
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
2.
A connected network has total weight $84$ and every vertex has even order. State the length of the shortest closed route that travels along every arc at least once, and justify your answer.
(3)
(Total for Question 2 is 3 marks)
D1-3.1 · Algorithm for finding the shortest route around a network, travelling along every edge at least once and ending at the start vertex (the Route Inspection Algorithm).
Q3
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
3.
For the network with vertices $A$ to $F$ and arcs $AB=7$ , $AC=9$ , $AF=12$ , $BC=5$ , $BD=8$ , $CD=6$ , $CE=10$ , $DE=4$ , $DF=14$ , $EF=11$ , a route must travel along every arc at least once but may start and finish at different vertices. Determine the shortest possible length and the start and finish vertices.
(8)
(Total for Question 3 is 8 marks)
D1-3.2 · The practical and classical Travelling Salesman problems. Determination of upper and lower bounds using minimum spanning tree methods. The nearest neighbour algorithm.
Q4
ORIGINAL
Year 2
Year 2: this is content the exam board adds beyond the AS subject content, for the full A-level.
4.
For the complete network on $A$ to $E$ with $AB=14$ , $AC=20$ , $AD=23$ , $AE=12$ , $BC=9$ , $BD=18$ , $BE=25$ , $CD=11$ , $CE=17$ , $DE=21$ , apply the nearest neighbour algorithm starting at $A$ and comment on the quality of the upper bound it produces.
(5)
(Total for Question 4 is 5 marks)
D1-3.2 · The practical and classical Travelling Salesman problems. Determination of upper and lower bounds using minimum spanning tree methods. The nearest neighbour algorithm.
Q5
ORIGINAL
Year 2
Year 2: this is content the exam board adds beyond the AS subject content, for the full A-level.
5.
Explain the difference between the classical and the practical travelling salesman problems, and state how the practical problem is converted into a classical one.
(3)
(Total for Question 5 is 3 marks)
D1-3.2 · The practical and classical Travelling Salesman problems. Determination of upper and lower bounds using minimum spanning tree methods. The nearest neighbour algorithm.
Q6
ORIGINAL
Year 2
Year 2: this is content the exam board adds beyond the AS subject content, for the full A-level.
6.
For the complete network on $A$ to $E$ with $AB=14$ , $AC=20$ , $AD=23$ , $AE=12$ , $BC=9$ , $BD=18$ , $BE=25$ , $CD=11$ , $CE=17$ , $DE=21$ , calculate the lower bound obtained by deleting each of $A$ , $C$ and $D$ in turn, state the best lower bound, and combine it with the nearest neighbour tour from $B$ to trap the optimal tour length.
(9)
(Total for Question 6 is 9 marks)

Progress is saved on this device for guests and accounts right now; cross-device account sync is not live yet.

Printable question pack — D1-3 Algorithms on graphs IIAll 20 questions across 2 specification points — 14 more than the 6 above — with the full mark scheme. Guest accessible · browser print.

D1-3 Algorithms on graphs II revision notes

Real-paper references

Real-paper references for this module are being imported — the questions above are the site's own, exam-faithful, marked.

Reference rows contain series, paper, question number, marks and classification metadata only. Pearson's question papers open on Pearson's own website.

Questions to attempt

Stuck on algorithms on graphs ii?