Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

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.

Königsberger Brückenproblem[1]

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?

Brücken in Königsberg

Das Dodekaeder-Problem von Hamilton

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

Bild eines Dodekaeder[2]

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.

Dodekaeder als Graph[3]

Aufgabe 2

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

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

Quellen

X

Fehler melden

X

Suche