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.