Wie heißt die Stadt, deren Brücken nicht nur für Leonard Euler ein unlösbares Problem darstellten?

a) Amsterdam
b) Berlin
c) Hamburg
d) Königsberg
e) St. Petersburg

Antwort:

"Über sieben Brücken musst Du gehn..." - in Königsberg wird's allerdings schwierig, zumindest, wenn man den Ehrgeiz hat, jede Brücke genau einmal zu überschreiten. 1736 versuchte sich der Schweizer Mathematiker, Physiker und Astronom Leonard Euler (1707-1783) systematisch an diesem Problem - und konnte zeigen, dass es keine Lösung gibt. Da zumindest in mathematischer Hinsicht der Beweis der Nicht-Lösbarkeit auch eine befriedigende "Lösung" sein kann, ist denn wohl auch der Titel seiner Abhandlung Solutio problematis ad geometriam gerechtfertigt. Immerhin legte das Genie mit dieser Arbeit praktisch den Grundstein für die Graphentheorie - eines der in den letzten Jahrzehnten am schnellsten wachsenden Forschungsgebiete der Mathematik, spielt diese Disziplin doch vor allem bei Optimierungsproblemen eine große Rolle.

Erklärung:

Aber zurück zum Königsberger Brückenproblem. Was genau bereitete den Bewohnern der Stadt und manchem ihrer Gäste Kopfzerbrechen?
Königsberg
© ?
(Ausschnitt)
 Bild vergrößernKönigsberg
Die Frage, die über den damaligen Bürgermeister der Stadt Danzig an Euler herangetragen wurde, war die, ob es einen Rundgang durch Königsberg gäbe, der jede der sieben Brücken genau einmal benutzt. Dazu muss man wissen, dass sich in der Innenstadt von Königsberg Alter und Neuer Pregel zum Fluss Pregel vereinigen und dabei eine Insel, den Kneiphof, bilden. Sowohl zu dieser Insel im Fluss als auch zu den Ufern der beiden Pregel-Arme führen Brücken, und die sind nun einmal gerade so arrangiert, dass kein einfacher Weg über alle führt.

Zwar ist der Stadtplan von Königsberg, insbesondere der Teil, auf den es in diesem Fall ankommt, recht übersichtlich, dennoch macht es Sinn, das Problem in etwas abstrakterer Art und Weise darzustellen: in Form eines Graphen. So ein Graph besteht aus Punkten - mathematisch korrekt: "Knoten" - und Verbindungslinien dazwischen - offiziell "Kanten" genannt. Repräsentiert man die Brücken durch Kanten und reduziert die Stadteile schlicht auf besagte Knoten, dann erhält man den Graphen des Brückenproblems. Euler konnten nun zeigen - oder nahm zumindest an -, dass es keinen Rundgang geben kann, da der Graph Knoten ungeraden Grades besitzt. Das sind Knoten, die mit einer ungeraden Anzahl von Nachbarknoten verbunden sind.

Euler vermutete, dass es nur dann einen Rundweg über alle Kanten geben kann, wenn alle Knoten geraden Grades sind. Den vollständigen Beweis lieferte der Meister jedoch nicht mehr selbst. Dieser gelang erst fast 150 Jahre später Carl Fridolin Bernhard Hierholzer. Auch wenn Euler nur die halbe Arbeit geleistet hatte, so wird doch heute ihm zu Ehren ein geschlossener Kantenzug, der alle Kanten genau einmal benutzt, eulersch genannt - wobei der Kantenzug nicht notwendigerweise an demselben Knoten enden muss, wo er begonnen hat.

Natürlich lässt sich ein solches graphentheoretisches Problem auch umdrehen: Die Königsberger müssten dann nicht alle ihre Brücken überqueren, sondern jeden Stadtteil genau einmal aufsuchen - entsprechend einem geschlossen Weg durch den Graphen, der jeden Knoten genau einmal durchläuft. Ein solcher Weg wird nach dem irischen Mathematiker Sir William Rowan Hamilton (1805-1865) als Hamiltonkreis bezeichnet. Wenngleich sich die Probleme von Euler und Hamilton stark zu ähneln scheinen, so sind doch letztere deutlich kniffliger zu lösen - zumindest verschlingen sie numerisch gelöst mehr Rechenzeit. Während es für das klassische Brückenproblem einen linearen Algorithmus gibt, gehört die Suche nach einem Hamiltonkreis zu den NP-vollständigen Problemen - einer Klasse besonders haariger Aufgaben in der Mathematik. Bislang ist für keines dieser Probleme ein polynominaler Algorithmus bekannt, entsprechend lange dauert die Suche nach einer Lösung.

Möchten Sie sich trotz verschwindender Erfolgsaussichten einmal am Königsberger Brückenproblem versuchen? Die Mathematik-Sammlung MathePrisma hat eine besonders schöne Website dem Thema gewidmet:

www.matheprisma.uni-wuppertal.de/Module/Koenigsb