# 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. ##### Chinese Postman

The Chinese Postman Problem can be solved by combining the Matching Algorithms and the Hierholzer Algorithm presented above. ##### Hierholzer's Algorithm

The Hierholzer Algorithm computes an Eulerian Tour in a graph (if one exists). ##### Traveling Salesperson Problem

Try to find an optimal TSP tour yourself and compare it with an optimal solution in this little game.