Die sieben Brücken von Königsberg

Die Menschen, die im 18. Jahrhundert in der Stadt Königsberg lebten, beschäftigten sich lange Zeit mit einem Rätsel: Durch die Stadt fließt der Fluss Pregel, der zwei Inseln bildet. Über diesen Fluss führen insgesamt sieben Brücken auf die Inseln. Ist es möglich, bei einem Sonntagsspaziergang alle Brücken zu überqueren, aber jede genau einmal? Schauen wir uns an, wie die Brücken über den Fluss verliefen:

Ist es möglich, dass wir unseren Spaziergang an irgendeiner Stelle beginnen und alle Brücken genau einmal überqueren? Wir können es versuchen, wir beginnen links unten und gehen nach oben und dann nach und nach nach rechts, so:

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

Wieder haben wir nur sechs von sieben Brücken unseres Königsbergs überquert. Es sieht fast so aus, als wäre es nicht möglich, bei einem Spaziergang jede Brücke genau einmal zu überqueren. Eines Tages stieß der berühmte Mathematiker Leonhard Euler auf dieses Problem. Was heißt berühmt – Euler war eine echte Legende der Mathematik, nach ihm ist sogar die eulersche Zahl benannt. Euler nahm sich vor, dieses Rätsel zu knacken. Er begann damit, die einzelnen Inseln oder Stadtteile zu bezeichnen, zu denen und von denen Brücken führten:

Euler stellte nun die folgende Überlegung an: Wenn auf eine Insel eine gerade Anzahl von Brücken führt, können wir diese Brücken bei einem Spaziergang überqueren, egal wo wir beginnen. Kurz gesagt: Über eine Brücke kommen wir auf die Insel, über die andere gehen wir wieder weg – die Anzahl der Brücken, die noch zu überqueren sind, hat sich um zwei verringert. Um über eine Brücke auf die Insel zu kommen und über eine andere wegzugehen, brauchen wir zwei Brücken. Wenn auf eine Insel sechs Brücken führen, besuchen wir die Insel dreimal. Stellen wir uns zum Beispiel vor, dass auf die Insel B vier Brücken führen würden, und zwar so:

Dann können wir bei einem Sonntagsspaziergang alle Brücken überqueren, egal wo wir beginnen. Probiere es aus! In der Abbildung habe ich einen Weg eingezeichnet. Stellen wir uns aber vor, dass auf die Insel B noch eine Brücke von der Insel D führen würde:

Wir sehen, dass uns der Weg, den wir gewählt haben, nicht erlaubt, alle Brücken genau einmal zu überqueren. Wir müssten über eine Brücke zur Insel B zurückkehren und dann auf die Insel D gehen. Aber wir können einen anderen Weg wählen. Wir können unseren Spaziergang auf der Insel B beginnen und dann sind wir in der Lage, alle Brücken genau einmal zu überqueren:

Unseren Spaziergang haben wir auf der Insel B begonnen, sind nach oben zum Gebiet A gegangen, dann über 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 Insel beginnen, die eine ungerade Anzahl von Brücken hat, sind wir in der Lage, alle ihre Brücken genau einmal zu überqueren. Oder wir können es genau umgekehrt machen – wir können auf der Insel D beginnen und auf der Insel B enden.

Euler bemerkte also: Damit man alle Brücken genau einmal überqueren kann, müssen entweder alle Inseln eine gerade Anzahl von Brücken haben, oder es darf zwei Inseln geben, die eine ungerade Anzahl von Brücken haben – auf einer Insel mit ungerader Anzahl von Brücken beginnen wir und auf der anderen enden wir. Alle anderen Inseln müssen eine gerade Anzahl von Brücken haben. Wenn wir uns die ursprünglichen sieben Brücken in Königsberg ansehen:

dann sehen wir, dass jede Insel eine ungerade Anzahl von Brücken hat! Die Insel A hat 3, B hat 5, C hat 3 und D hat auch 3. Deshalb hat das Rätsel keine Lösung – es ist nicht möglich, bei einem Sonntagsspaziergang alle sieben Brücken genau einmal zu überqueren. Wenn wir irgendeine 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 die Insel B plötzlich 4 Brücken und die Insel C zwei Brücken hat. Bei den Inseln A und D hat sich die Anzahl der Brücken nicht geändert. Wir haben auf einmal zwei Inseln mit gerader Anzahl von Brücken und zwei Inseln mit ungerader 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 genau einmal überqueren. In der Abbildung haben wir auf der Insel A begonnen und auf der Insel D geendet.

Leonhard Euler hat also ein weiteres berühmtes mathematisches Problem gelöst und damit mehr oder weniger den Grundstein für das gelegt, was wir heute Graphentheorie nennen, und ihm zu Ehren heißt ein Graph, in dem man alle Kanten genau einmal durchlaufen kann, in der Sprache der Graphentheorie eulerscher Graph.