A classical problem of graph theory is the Eulerian Path Problem
, which asks for paths or cycles that cover all arcs of a given graph.
The problem was first formulated by the following question:
The river Pregel divides the town Königsberg (Kaliningrad nowadays) in five parts, that are connected among themselves by seven bridges. Can one do a tour that passes each bridge exactly once?
This question can be interpreted and generalized as a graph theoretic problem (city parts as nodes, bridges as edges) and was thus solved by Leonhard Euler in 1736:
Such a tour exists if and only if no or two nodes have odd degree.
If no nodes has odd degree, there is an Eulerian Cycle; if on the other hand two nodes have odd degree, only an Eulerian Path that starts and ends in different nodes is possible.
The aim of the related Chinese Postman Problem
is to find a shortest path in a graph, such that this path uses each edge at least once and returns to the starting point.
The most prominent example for this problem is a postman that delivers mail in a part of his town. He has to visit each street once and he needs to return to the post office at the end, all while using as little time as possible. The problem's name originates exactly from the postman's problem and from the fact that it was first examined by a Chinese.
A similar example occurs for winter services: Each street has to be visited in order to remove snow, and each shift has to end at the depot where it started.
|The Hierholzer Algorithm computes an Eulerian Tour in a graph (if one exists).
|The Chinese Postman Problem can be solved by combining the Matching Algorithms and the Hierholzer Algorithm presented above.