ABSTRACT
Eulerian circuits and Eulerian paths arise in puzzles as well as in real-world situations in which service vehicles need to traverse all the streets of a road network. The overall task is to trace out a continuous route, possibly returning to the starting point. In some cases, all of the graph edges have to be traversed exactly once (forming an Eulerian path/circuit). In other cases, repetition is unavoidable in traversing the edges and we wish to minimize these repetitions (Chinese Postman Problem). A more general optimal routing problem is also studied in which the objective is to minimize the total time required to traverse all edges of a weighted graph at least once.
