Algorithms on graphs II

Explanation

• The route inspection, or Chinese postman, problem asks for the shortest closed route that uses every arc of a network at least once. If every vertex has even order the network is Eulerian and the answer is simply the total weight of the network.
• Otherwise the odd vertices must be paired up and the shortest path between each pair repeated, because repeating a path raises the order of its two endpoints by one and leaves every internal vertex even.
• With four odd vertices there are exactly three pairings to test; with six there are fifteen, which is why the specification limits questions to at most four odd vertices unless extra information restricts the pairings.
• Work out the shortest path for each pair, total each pairing, choose the smallest total, and add it to the weight of the network.
• If the route may start and finish at different vertices, leave the two odd vertices with the largest shortest path between them unpaired and repeat the best pairing of the remaining two.

Explanation

• The travelling salesman problem asks for a tour of minimum length that visits every vertex and returns to the start. In the classical problem each vertex is visited exactly once; in the practical problem a vertex may be revisited.
• The classical problem is set on a complete network satisfying the triangle inequality, that is, the length of any arc is at most the sum of the lengths of the other two in its triangle. Converting the network into a complete network of shortest distances turns the practical problem into a classical one.
• Since the problem cannot be solved exactly at this level, the answer is trapped between bounds. The nearest neighbour algorithm gives an upper bound: from the start vertex repeatedly go to the nearest unvisited vertex, then return to the start.
• Doubling the weight of the minimum spanning tree also gives an upper bound, which short cuts can improve. A lower bound comes from deleting one vertex, finding the residual minimum spanning tree on the remaining vertices, and adding the two shortest arcs at the deleted vertex;
• repeating this for every vertex and taking the largest result gives the best lower bound. When an upper bound equals a lower bound, that common value is the length of the optimal tour.