Route Inspection Problem
Is the problem of traversing a graph \( G \) such that you cover every edge in the graph once and then return to your start point.
The algorithm for this has us convert a non-traversable network into a traversable one by repeating one or more edges on an odd node to ensure it has an even valency (making the graph eulerian).
The algorithm is:
- List all odd vertices.
- Form all possible pairings of odd vertices.
- For each pairing find the shortest distance between the pairs.
- Choose the pair with the shortest sum. Constructing a route that repeats these edges (effectively making all vertices even.)