WOLFRAM|DEMONSTRATIONS PROJECT

Tours through a Graph

​
graph type
small
graph based on grid
small planar graph
large planar graph
show tour
problem type
vehicle routing problem
traveling salesman problem on graph
plotter problem
Chinese postman problem
Shortest cycle through all edges, staying on graph edges, with vertex and edge repetition allowed; like a mailman using streets
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.