4. Euler-Züge und Hamilton-Kreise

Wir beginnen nun mit der Untersuchung algorithmischer Fragen der Graphentheorie. Den Anfang bildet eine klassische Problemstellung:

Kann ein gegebener Graph so durchlaufen werden, dass jede Kante des Graphen genau einmal besucht wird und wir am Ende wieder bei der Startecke ankommen?

Seine historischen Wurzeln hat diese Frage im Königsberger Brückenproblem (1736): Damals wurde die Frage gestellt, ob es eine Stadtbesichtigung gibt, die jede der sieben Königsberger Brücken genau einmal überquert. Euler zeigte mit graphentheoretischen Methoden, dass dies nicht möglich ist. Die Mathematik, die sich aus der Frage ergibt, ist erstaunlich reichhaltig und wir werden im Verlauf der Untersuchung auch offene Fragen kennenlernen. Als überraschend schwierig erweist sich das analoge Problem, einen Graphen so in einem geschlossenen Kantenzug zu durchlaufen, dass alle Ecken genau einmal besucht werden. Die Frage nach der Existenz derartiger Hamilton-Kreise führt uns zum P ≠ NP-Problem der Komplexitätstheorie.