1.4.7 Eulerian Cycle / Chinese Postman
INPUT OUTPUT
Input Description:
A graph G=(V,E).}
Problem:
Find the shortest tour of G visiting each edge at least once.
Excerpt from
The Algorithm Design Manual:
Suppose you are given the map of a city and charged with designing the routes for garbage trucks, snow plows, or
postmen. In all of these applications, every road in the city must be completely traversed at least once in order
to ensure that all deliveries or pickups are made. For efficiency, you seek to minimize total drive time, or
equivalently, the total distance or number of edges traversed.
Such applications are variants of the Eulerian cycle problem, best characterized by the children's puzzle
that asks them to draw a given figure completely without lifting their pencil off the paper and without repeating
any edges. We seek a path or cycle through a graph that visits each edge exactly once.
Recommended Books
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
An Introduction to Parallel Algorithms
Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica
Introduction to Algorithms
Combinatorial Optimization: Networks and Matroids
Graph Theory 1736-1936
Recreations Mathematiques
