Rundreiseprobleme

Das Königsberger Brückenproblem

In Königsberg (heute Kaliningrad) teilt der Fluss Pregel die Stadt in mehrere Stadtteile auf. Der Stadtplan hebt die Brücken hervor, die die Stadtteile miteinander verbinden.

Der Mathematiker Euler (1707-1782) beschäftigte sich mit der Frage, ob es einen Rundgang durch Königsberg gibt, der jede der sieben Brücken über den Fluss Pregel genau einmal benutzt.

Aufgabe 1

(a) Versuche erst einmal, das Problem von Euler zu lösen.

(b) Der folgende Graph zeigt die Brückensituation in Königsberg in einer abstrahierenden Darstellung. Was stellen die Knoten des Graphen, was die Kanten dar?

(c) Wie viele Kanten gehen von den jeweiligen Knoten aus? Was hat das mit der Lösung des Problems von Euler zu tun?

Das Dodekaeder-Problem von Hamilton

Ein Dodekaeder ist ein Körper, der aus 12 regelmäßigen 5-Ecken besteht.

Der Mathematiker Hamilton (1805-1865) erfand 1859 ein Spiel, bei dem man eine Rundreise längs der Kanten eines Dodekaeders finden soll, so dass alle Ecken des Dodekaeders - außer der Start- und Zielecke - genau einmal besucht werden.

Um eine bessere Übersicht über die Rundreise zu gewinnen, wird das Spiel meist in einer zweidimensionalen Form angeboten (siehe etwa icosian game). Statt des dreidimensionalen Körpers wird eine etwas abstraktere Darstellung der Ecken und Kanten in Form eines Graphen mit Knoten und Kanten gewählt.

Aufgabe 2

(a) Versuche, das Problem von Hamilton zu lösen.

(b) Wie könnte man systematisch vorgehen, um die gesuchte Rundreise zu finden?