Eulerwege

Ein klassisches Problem der Graphentheorie ist das Eulerweg-Problem, wobei nach Wegen bzw. Kreisen, die alle Kanten eines gegebenen Graphen enthalten, gesucht wird.

Die Aufgabenstellung wurde erstmals durch folgende Frage formuliert:
Der Fluss Pregel teilt die Stadt Königsberg (heute Kaliningrad) in fünf Stadtteile, die untereinander durch sieben Brücken verbunden sind. Ist ein Rundgang möglich, bei dem man jede Brücke genau einmal passiert?

Diese Frage lässt sich als graphentheoretisches Problem auffassen (Stadtteile als Knoten, Brücken als Kanten) und verallgemeinern und wurde als solches 1736 von Leonhard Euler gelöst: Ein solcher Rundweg existiert genau dann, wenn kein oder zwei Knoten ungeraden Grad besitzen.
Besitzt kein Knoten ungeraden Grad, so erhält man einen Eulerkreis, besitzen jedoch zwei Knoten einen ungeraden Grad, so ist nur ein Eulerweg möglich, dessen Endpunkte eben diese zwei Knoten sind.

Ein Algorithmus zur Lösung dieses Problems ist der Hierholzer - Algorithmus.