Further Maths - Route Inspection
Flashcards
How could you summarise the route inspection problem?
Find a route of minimum weight that traverses every edge at least once, starting and ending at the same vertex.
Why will a Eulerian trail solve the route inspection problem minimally?
Because it traverses every edge exactly once, so it keeps edge weights to a minimum.
When there are two odd verticies and you’re trying to solve a route inspection problem, what should you do?
Find the shortest route between them and double those edges.
When there are more than two odd vertices in a graph, what should you do before performing the route inspection algorithm?
Consider all the ways they could pair up and pick the two that increase the weight by the smallest amount.
How can you quickly calculate the total cost of the minimum Eulerian trail after doubling up a few verticies?
Add up all the weights and then the weight of the shortest path between the odd vertices.
For route inspection with 4 odd vertices and starting and ending in different places, after tabulating all possible pairings you have a list of path costs between them. Which pair should you choose to double up rather than start and end there?
The pair with the smallest cost should be doubled.
2022-03-17
When doubling up vertices for route inspection, what do you have to consider apart from direct connections?
Whether there is any route going through multiple vertices that’s shorter.