Die sieben Brücken von Königsberg

Die Bewohner der Stadt Königsberg im 18. Jahrhundert haben lange Zeit ein Rätsel gelöst: Der Fluss Pregola fließt durch die Stadt und bildet zwei Inseln. Es gibt sieben Brücken, die über den Fluss zu den Inseln führen. Ist es möglich, alle Brücken bei einem Sonntagsspaziergang zu überqueren, aber jede nur einmal? Schauen wir uns einmal an, wie die Brücken über den Fluss gebaut wurden:

Ist es möglich, dass wir unseren Spaziergang an einem bestimmten Punkt beginnen und alle Brücken nur einmal überqueren? Wir können es versuchen, indem wir unten links beginnen und uns nach oben und dann allmählich nach rechts vorarbeiten, etwa so:

Wir sehen, dass wir sechs der sieben Brücken überquert haben und eine der Brücken übersehen haben. Wir können einen anderen Weg versuchen...

Wieder haben wir nur sechs der sieben Brücken unserer Königsbrücke passiert. Es scheint fast unmöglich zu sein, jede Brücke nur einmal zu überqueren. Eines Tages stieß der berühmte Mathematiker Leonhard Euler auf dieses Problem. Was heißt berühmt - Euler war eine mathematische Legende, nach der sogar die Eulersche Zahl benannt ist. Euler dachte, er würde das Rätsel knacken. Er begann damit, die Inseln oder Teile der Stadt zu markieren, zu denen und von denen Brücken führten:

Euler stellte nun folgende Überlegung an: Wenn eine Insel eine gerade Anzahl von Brücken hat, die zu ihr führen, können wir diese Brücken in einem Spaziergang überqueren, egal wo wir beginnen. Kurz gesagt, wir kommen über eine Brücke auf die Insel und verlassen sie über eine andere - die Zahl der Brücken, die wir nicht mehr überqueren können, hat sich um zwei verringert. Um über die eine Brücke auf die Insel zu gelangen und über die andere die Insel zu verlassen, brauchen wir zwei Brücken. Wenn sechs Brücken zur Insel führen, besuchen wir die Insel dreimal. Nehmen wir zum Beispiel an, es gäbe vier Brücken, die zur Insel B führen, wie folgt:

Dann können wir in einem Sonntagsspaziergang über alle Brücken gehen, egal wo wir anfangen. Probieren Sie es aus! Auf dem Bild habe ich einen Weg markiert. Aber nehmen wir an, es gäbe eine weitere Brücke, die von der Insel D zur Insel B führt:

Wir sehen, dass der von uns gewählte Weg nicht ausreicht, um alle Brücken einmal zu überqueren. Wir müssten über eine der Brücken zurück zur Insel B gehen und dann zur Insel D. Aber wir können einen anderen Weg wählen. Wir können unsere Wanderung auf der Insel B beginnen und können dann alle Brücken nur einmal überqueren:

Wir beginnen unseren Spaziergang auf Insel B, gehen hinauf zum Gebiet A, nehmen dann die Brücke zurück nach B, zum Gebiet C, dann zurück zur Insel B und schließlich zur Insel D. Wenn wir also auf einer Brücke beginnen, die eine ungerade Anzahl von Brücken hat, können wir alle Brücken nur einmal überqueren. Man kann aber auch den umgekehrten Weg gehen - man kann auf der Insel D beginnen und auf der Insel B enden.

Euler stellte also fest, dass man alle Brücken nur einmal überqueren kann, wenn entweder alle Inseln eine gerade Anzahl von Brücken haben, oder wenn es zwei Inseln mit einer ungeraden Anzahl von Brücken gibt - wir beginnen also auf einer Insel mit einer ungeraden Anzahl von Brücken und enden auf der anderen. Alle anderen Inseln müssen eine gerade Anzahl von Brücken haben. Wenn wir uns die ursprünglichen sieben Brücken in King:

sehen wir, dass jede Insel eine ungerade Anzahl von Brücken hat! Insel A hat 3, B hat 5, V hat 3 und D hat ebenfalls 3. Das Rätsel ist also nicht lösbar - es ist unmöglich, dass wir bei einem Sonntagsspaziergang alle sieben Brücken nur einmal überquert haben. Wenn wir eine der Brücken abreißen würden, hätte das Rätsel plötzlich eine Lösung. Reißen wir zum Beispiel eine der Brücken zwischen den Inseln B und C ab:

Wir sehen, dass Insel B plötzlich vier Brücken hat und Insel C zwei Brücken. Die Inseln A und D haben die gleiche Anzahl von Brücken. Plötzlich haben wir zwei Inseln mit einer geraden Anzahl von Brücken und zwei Inseln mit einer ungeraden Anzahl von Brücken. Wenn wir unseren Spaziergang auf einer der Inseln beginnen, die eine ungerade Anzahl von Brücken haben, können wir alle Brücken nur einmal überqueren. In der Abbildung haben wir auf der Insel A begonnen und auf der Insel D geendet.

Leonhard Euler löste also ein weiteres berühmtes mathematisches Problem und legte damit mehr oder weniger den Grundstein für das, was wir heute als Graphentheorie bezeichnen, und nach seiner Rechnung wird der Weg, bei dem wir alle Brücken nur einmal überqueren, in der Graphentheorie als Eulerscher Weg bezeichnet.