Tours through a Graph
If we think of a graph as a road system, there are many types of optimal tours through the system that one might seek. This Demonstration shows four such tours, which can be found by various optimization methods. The starting point is shown as a larger gray disk.[more]
Vehicle routing tour: the cycle of shortest length that visits all vertices, with repetition of edges allowed.
Traveling salesman tour: For a graph, this means the shortest Hamiltonian cycle: a cycle passing through all vertices. In one of the four cases, there is no Hamiltonian cycle.
Plotter problem route: the shortest-length route for a plotter pen that visits all edges: thus, additional straight segments where the pen is in the up position are allowed.
Chinese postman tour: the shortest-length tour that visits all edges, with repetitions allowed.
In the images, the optimal cycle starts with red edges and ends with cyan. In the Chinese postman and plotter problem cases, the vertices of odd degree are matched up in a way that minimizes the total extra distance, and that matching is indicated by colors; vertices of even degree are simply colored white.
Unchecking the "show tour" box lets you try to find the optimal cycle yourself.[less]
For graphs of modest size, the method of integer linear programming can be used to solve the routing problem and the traveling salesman problem. The other two problems can be solved even for graphs of very large size by using the blossom algorithm for finding a perfect matching of minimal weight.
For the plotter problem, we form the complete graph whose vertices are all odd-degree vertices, with weights being the straight-line distance between the vertices. Then a minimal-weight perfect matching of this graph tells us which edges can be added so that the resulting graph (possibly with multiple edges) has only vertices of even degree. An Eulerian tour of the resulting graph gives the optimal plotter path, since the pen-up distance is minimized.
For the Chinese postman problem, one takes a similar approach, but the weight of an edge joining two odd-degree vertices is taken to be the length of the shortest path between them in the original network. Again, the blossom algorithm can find a minimal perfect matching, and the resulting even-degree graph is Eulerian. We find an Eulerian cycle and then replace each non-edge by the corresponding shortest path in the original network.