What is a semi-Eulerian network?

One with exactly two odd nodes: a route using each arc once exists between those two nodes.

Length of the shortest closed route with odd nodes?

Total weight plus the least total of the shortest paths in a pairing of the odd nodes.

Shortest route that need not close, with four odd nodes?

Total weight plus the smallest shortest distance between a pair of odd nodes; start and finish at the other two.

What is the classical TSP?

Find the shortest tour visiting every node exactly once and returning, on a complete network.

What does nearest neighbour give?

A tour, so an upper bound for the shortest tour.

How do you find a lower bound for the TSP?

Delete a vertex, find the MST of the rest, add the two shortest arcs at the deleted vertex.

How do you write the interval for the optimal tour?

Largest lower bound \le shortest tour \le smallest upper bound.

How does the practical TSP differ from the classical one?

Nodes may be visited more than once, and the network need not be complete; use shortest distances.

Give two ways to refine a network model.

Use times instead of distances, or use directed arcs for one-way roads.

Route inspection and travelling salespersonAQA A-Level Further Maths: Flashcards

Card 1 of 130 of 13 known

Question

What is route inspection?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What is route inspection?: Finding the shortest route that traverses every arc at least once and returns to the start.
What is the shortest closed route if all nodes are even?: The total weight of all arcs.
How many pairings of 4 odd nodes are there?: Three.
What is a semi-Eulerian network?: One with exactly two odd nodes: a route using each arc once exists between those two nodes.
Length of the shortest closed route with odd nodes?: Total weight plus the least total of the shortest paths in a pairing of the odd nodes.
Shortest route that need not close, with four odd nodes?: Total weight plus the smallest shortest distance between a pair of odd nodes; start and finish at the other two.
What is the classical TSP?: Find the shortest tour visiting every node exactly once and returning, on a complete network.
What does nearest neighbour give?: A tour, so an upper bound for the shortest tour.
How do you find a lower bound for the TSP?: Delete a vertex, find the MST of the rest, add the two shortest arcs at the deleted vertex.
Which lower bound is the best?: The largest one.
How do you write the interval for the optimal tour?: Largest lower bound $\le$ shortest tour $\le$ smallest upper bound.
How does the practical TSP differ from the classical one?: Nodes may be visited more than once, and the network need not be complete; use shortest distances.
Give two ways to refine a network model.: Use times instead of distances, or use directed arcs for one-way roads.

Exam questions on Route inspection and travelling salesperson

A network has six nodes $A$ to $F$ . The arcs and their weights, in km, are $AB$ 6, $AC$ 5, $BC$ 4, $BD$ 7, $CD$ 3, $CE$ 8, $DE$ 6, $DF$ 9 and $EF$ 5. The total weight of all the arcs is 53 km.
The route may now start and finish at different nodes. State where it should start and finish and the length of the shortest such route that traverses every arc at least once.2 marks
A van starts at depot $A$ , must visit each of depots $B$ , $C$ , $D$ and $E$ exactly once and return to $A$ . The distances in km between each pair of depots are $AB$ 8, $AC$ 5, $AD$ 6, $AE$ 14, $BC$ 11, $BD$ 9, $BE$ 4, $CD$ 12, $CE$ 13 and $DE$ 15.
Delete vertex $B$ instead, to find a lower bound. Use it, with your answer to part (a), to write down an interval for the length of the shortest tour.2 marks
A courier based at $A$ must deliver parcels to $B$ , $C$ and $D$ and return to $A$ , visiting each at least once. The roads, with lengths in km, are $AB$ 4, $BC$ 3, $CD$ 5, $DA$ 6 and $BD$ 9.
Show that the shortest distance from $B$ to $D$ is 8 km, and find the shortest distance from $A$ to $C$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).