9459

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+