Tours through a Graph
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.
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.