Eulers Linien

Wer kennt es nicht, das „Haus des Nikolaus“? Die Aufgabe besteht darin, die Verbindungslinien zwischen fünf Punkten (in der Abbildung 1, 2, 3, 4, 5) „in einem Zug“ so zu zeichnen, dass jede dieser acht Linien genau einmal durchlaufen wird.

Abbildung 1: Das Haus des Nikolaus

Eine von vielen möglichen Lösungen dieser Aufgabe ist: 1-3-5-4-2-3-4-1-2. Im ERLEBNISLAND MATHEMATIK findet man drei ähnliche Aufgaben, bei denen es darum geht, eine Schnur über vorgegebene Linien jeweils genau einmal um vorgegebene Punkte herum zu legen. Je mehr Punkte und Linien es gibt, desto schwieriger ist es, eine Lösung zu finden.


Und nun … die Mathematik dazu:

Bei dem „Haus des Nikolaus“ und den im ERLEBNISLAND MATHEMATIK gezeigten drei Figuren handelt es sich — mathematisch formuliert — um sogenannte ungerichtete Graphen. Ein ungerichteter Graph besteht aus einer Menge von Punkten, zwischen denen Linien verlaufen. Die Punkte nennt man Knoten oder Ecken, die Linien nennt man Kanten. Ein derartiger Graph heißt zusammenhängend, falls jeder Knoten mit jedem anderen durch einen „Weg“ verbunden ist, also durch eine Folge miteinander (an Knoten) gebundener Kanten. Das „Haus des Nikolaus“ ist so ein zusammenhängender Graph. Er hat fünf Knoten: 1, 2, 3, 4, 5 und acht Kanten: 1-2, 1-3, 1-4, 2-3, 2-4, 3-4, 3-5, 4-5.

Das einfachste Modell im ERLEBNISLAND MATHEMATIK stellt ebenfalls einen zusammenhängenden Graphen dar. Er besitzt 6 Knoten und 12 Kanten.

Zusammenhängende Graphen werden nach dem Mathematiker Leonhard Euler (1707–1783) als Eulersche Linien, „geschlossener“ Eulerkreis oder Eulerzug bezeichnet. In der Mathematik (speziell in ihrem Teilgebiet der Graphentheorie) handelt es sich um einen Zyklus, der alle Kanten eines Graphen genau einmal enthält. Einen zusammenhängenden Graph, der eine Eulersche Linie besitzt, bezeichnet man auch als einen Eulerschen Graphen. Euler löste im Jahre 1736 das sogenannte Königsberger Brückenproblem: Durch das ehemals ostpreußische Königsberg (seit 1945 russisch: Kaliningrad) fließt die Pregel. Zur Zeit Eulers gab es sieben Brücken über diesen verzweigten Fluss. Man stellte sich die Frage, ob ein Rundweg bestehe, bei dem jede Brücke genau einmal überquert würde.

Abbildung 2: Das Königsberger Brückenproblem

Gibt es einen solchen Rundweg, dann besteht der Beweis seiner Existenz einfach darin, diesen Weg aufzuzeigen. Ein ernsthaftes mathematisches Problem ist es hingegen nachzuweisen, dass es einen solchen Weg nicht geben kann. Leonhard Euler konnte in seiner „Solutio problematis ad geometriam situs pertinentis“ beweisen, dass es einen solchen Rundweg nicht gibt, wenn es mehr als zwei Inseln oder angrenzende Gebiete gibt, die über eine ungerade Anzahl von Brücken erreichbar sind. Eulers Überlegungen führten direkt zur Graphentheorie als Teildisziplin der modernen Mathematik.


Literatur

[1] Diestel, R.: Graphentheorie, 3. Auflage, Berlin / Heidelberg, 2006.

[2] Fellmann, E. A.: Leonhard Euler, Basel, 2006.

[3] Jungnickel, D.: Graphen, Netzwerke und Algorithmen, 3. Auflage, Darmstadt, 1994.

[4] Velminski, W.: Leonhard Euler. Die Geburt der Graphentheorie, Berlin, 2008.