Rücken Sie Ihre Sitzgelegenheit zurecht, machen Sie es sich bequem, seien Sie bereit für eine virtuelle Zeitreise; wir begeben uns zurück ins 18. Jahrhundert.
Wir befinden uns jetzt im damaligen Königsberg (heute Kaliningrad). Nach einem gemütlichen Spaziergang durch die Stadt kommen wir schließlich an den Pregel. Wir überqueren eine der sieben Brücken und stehen inmitten der sogenannten Kneiphof-Insel.
Ein älterer Mann kommt auf uns zu und bietet eine Wette: “Schaffen Sie es, jede der sieben Brücken genau einmal zu passieren und am Ende wieder hier an ihrem Ausgangspunkt zu landen? Ich biete einen Reichstaler.” (Anm.: Kaufkraft im 18.Jh etwa 15€)
Lageskizze der Königsberger Brücken
Sollten Sie diese Wette annehmen?
Natürlich nicht! Es ist unmöglich, einen solchen Weg zu finden. Doch warum? Und wie lässt sich das beweisen? (Diese beiden Fragen hängen oft eng miteinander zusammen.)
Setzen wir zur Auflösug unseren Stadtrundgang fort. Wir kommen zu einem kleinen Haus, irgendwo in Königsberg. Es ist das Haus Leonhard Eulers, einer der größten Mathematiker der Geschichte. Euler war es, der unsere Fragen im Jahre 1736 beantworten konnte.
Dazu tat er etwas für die Mathematik seiner Zeit noch recht ungewöhnliches: Er ließ die genauen Details des Brückenplans weg und untersuchte nur ihre Struktur, die Beziehung der Wege untereinander. Die genauen Maße der Wege waren uninteressant.
So wandelte Euler das praktische Problem um in eines der Graphentheorie, dessen Anfang heute bei diesen Entdeckungen Eulers gesehen wird. Er verwandte neue Begriffe, die “Knoten” und die “Kanten”, die zusammen einen Graphen bilden.
Graph der Königsberger Brücken
Die Knoten sind dabei die vier zu erreichenden Teile der Stadt; die Kanten als Verbindungen zwischen den Knoten stellen unsere Brücken dar.
Gesucht ist nun ein Weg, der bei demselben Knoten beginnt und endet und dabei jede Kante genau einmal benutzt.
Wir sehen schnell, dass an jedem der Knoten eine ungerade Anzahl von Kanten liegt (man spricht von einem ungeraden Grad der Knoten). Ein Knoten, der zugleich Start- und Endknoten unserer Reise ist, müsste allerdings einen geraden Grad besitzen, ansonsten muss mindestens eine Brücke zweimal überquert werden. Das ist uns jedoch nicht erlaubt, wir können also keinen solchen Weg finden.
(Für eine sehr gut gestaltete nähere Erläuterung des Themas siehe http://www.matheprisma.uni-wuppertal.de/Module/Koenigsb/)
Ein wirklich schönes Rätsel, dass du gut erklärt hast ;)
Unmathematisch könnte man es schwammig ebenfalls mit den drei Brücken erläutern, so wie du es auch getan hast, nur ohne die ganzen Graphen. Die verstehen vermutlich wenige von denen, die sich nicht für die Mathematik interessieren :D
Danke Hannes, für dein Lob.
Mag sein, dass es für manche Leser ohne die graphentheoretischen Begriffe einfacher zu verstehen wäre, aber ich denke diesen kleinen Schritt der Abstraktion zu gehen ist nicht allzu schwierig.