# Routing

A classical problem in graph theory is the *Eulerian Path Problem*, which asks for paths or cycles that traverse all edges of a given graph exactly once. The problem was first formulated in the following form: ‘The river Pregel divides the town of Königsberg (Kaliningrad nowadays) into five parts that are connected by seven bridges. Is there a tour that passes each bridge exactly once?’

The aim of the related *Chinese Postman Problem* is to find a shortest path in a graph, such that this path uses each edge (directed or undirected) at least once and returns to the starting point. The most prominent example for this problem is a postman that delivers mail in some part of town and thus has to walk down every street at least once.
In the *Traveling Salesperson Problem* the objective is to find a minimum length tour through all nodes of a graph, starting and ending at the same point.