Route inspection and travelling salesperson

Route inspection and travelling salesperson Flashcards

Spec DB3–DB4 · AQA A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

13 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

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.

Flashcards