Graphen und NetzwerkeDie Brücken von Königsberg

Einer der ersten Mathematiker, der sich Gedanken zu Graphen und Netzwerke machte, war Leonhard Euler. Euler war fasziniert von einem alten Problem in Bezug auf die Stadt Königsberg nahe der Ostsee.

Der Fluss Pregel teilt Königsberg in vier voneinander getrennte Teile, die durch sieben Brücken miteinander verbunden sind. Ist es möglich, durch die Stadt zu gehen und alle Brücken genau einmal zu überqueren - aber nicht mehr als einmal? (Start und Ziel können überall sein und müssen nicht unbedingt am selben Ort sein).

Versuche, eine passende Route zu finden, indem du auf diese Karten einen Weg einzeichnest:

Map 1

Map 2

Map 3

Map 4

Im Fall von Königsberg scheint es unmöglich zu sein, eine gültige Route zu finden, aber einige der anderen Städte funktionieren. Euler gelang es, eine einfache Regel zu finden, die auf jede Stadt angewendet werden kann, ohne viele Möglichkeiten ausprobieren zu müssen - mithilfe der Graphentheorie.

Zuerst müssen wir die Stadtpläne in Graphen mit Kanten und Knoten umwandeln. Jede Insel oder Region des Landes wird durch dargestellt und jede Brücke, die zwei Regionen verbindet, wird durch eine/n entsprechende/n dargestellt.

Jetzt ist das Problem, "eine Stadt zu durchwandern, während man jede Brücke genau einmal überquert", zu einem Problem geworden, "einen Graphen mit einem Strich ohne abzusetzen zu zeichnen, während man jede Kante genau einmal nachzieht".

Überlege dir auf dem Papier ein paar unterschiedliche Graphen und versuche dann herauszufinden, welche mit einem einzigen, kontinuierlichen Strich gezeichnet werden können.

Genau wie bei den Stadtplänen zuvor, stellen wir fest, dass einige Graphen möglich sind, während andere nicht möglich sind. Um zu verstehen, warum das so ist, beschriften wir jeden Knoten mit seinem Grad. Dann können wir die Knoten auf verschiedene Weise einfärben und versuchen, ein Muster zu erkennen:

Wert

Größe

Primzahlen

Gerade und ungerade

Diese Graphen sind möglich:

Diese Graphen sind nicht möglich:

Vergleicht man diese Zahlen für Graphen, die möglich sind, und solche, die nicht möglich sind, scheint es, dass ein Graph gezeichnet werden kann, wenn er . Diese Bedingung kann erklärt werden, wenn wir nur einen einzigen Knoten im Graphen betrachten:

Hier siehst du einen einzelnen, vergrößerten Knoten in einem Graphen.

Wenn wir den Graphen zeichnen, werden wir irgendwann eine Kante haben, die zu diesem Knoten führt, und dann eine andere, die wegführt. Auf diese Weise treffen zwei Kanten am Knoten aufeinander.

Vielleicht ist der Knoten eher eine Kreuzung als eine Ecke. In diesem Fall gibt es eine andere Kante, die zum Knoten hinführt, und eine weitere Kante, die wegführt. Jetzt haben wir vier Kanten.

Und in manchen Graphen kann es sogar ein drittes Kantenpaar geben, das auf den Knoten zu und von ihm weg führt. Jetzt gibt es sechs Kanten.

Beachte, dass es in jedem Fall immer eine gerade Anzahl von Kanten gibt, die sich am Knoten treffen.

Die einzigen zwei Ausnahmen sind die Knoten, wo der Pfad beginnt und wo er endet - diese beiden können eine ungerade Anzahl von Kanten haben. Wenn der Start- und Endpunkt derselbe ist, ist der Grad aller Knoten im Graphen gerade.

Wenn du zur Karte von Königsberg zurückscrollst, wirst du feststellen, dass es mehr als zwei Inseln mit einer ungeraden Anzahl von Brücken gibt. Daher ist eine Route, die jede Brücke genau einmal überquert, natürlich unmöglich - und das ist es, was Leonard Euler entdeckt hat.

Eulers Entdeckung mag im wirklichen Leben nicht besonders nützlich erscheinen, aber Graphen sind die Grundlage für viele andere geografische Probleme, wie zum Beispiel das Finden von Wegstrecken zwischen zwei Orten. Wir werden später noch mehr von diesen Anwendungen kennenlernen.

Sprache ändern

Melde dich bei Mathigon an

Teile

Fortschritt zurücksetzen

Glossar

Graphen und NetzwerkeDie Brücken von Königsberg

Map 1

Map 2

Map 3

Map 4