Historischer Stadtplan Königsbergs mit Flussarmen, Inseln und Brücken
Mathematik als Wissenschaft Florence  

Das Königsberger Brückenproblem: Wie Leonhard Euler mit einem Spaziergang die Graphentheorie erfand

Das Rätsel der sieben Brücken von Königsberg

Im Königsberg des 18. Jahrhunderts teilte der Fluss Pregel die Stadt in mehrere Landbereiche. Zwei Inseln und die angrenzenden Ufer waren durch insgesamt sieben Brücken miteinander verbunden. Für die Bewohner entstand daraus eine scheinbar harmlose, aber erstaunlich hartnäckige Knobelaufgabe: Konnte man einen Spaziergang planen, bei dem jede der sieben Brücken genau einmal überquert wurde?

Dabei durfte eine Brücke weder ausgelassen noch ein zweites Mal benutzt werden. Start- und Zielpunkt durften grundsätzlich verschieden sein. Gerade diese einfache Formulierung machte das Rätsel so reizvoll. Einzelne Wege ließen sich leicht finden, doch bei jedem neuen Versuch blieb am Ende mindestens eine Brücke übrig oder eine bereits benutzte Brücke musste erneut überquert werden.

Der typische Denkfehler besteht darin, immer neue konkrete Routen auszuprobieren. Bei sieben Brücken gibt es bereits viele mögliche Reihenfolgen, und die Zahl wächst schnell, sobald Verzweigungen berücksichtigt werden. Leonhard Euler wählte deshalb einen grundlegend anderen Ansatz. Statt die Stadt Schritt für Schritt abzulaufen, fragte er, welche Struktur hinter allen möglichen Wegen steckt. Damit wurde aus einem Spaziergangsproblem eine präzise mathematische Untersuchung.

Eulers Geniestreich der radikalen Abstraktion

Euler erkannte, dass für die entscheidende Frage viele Eigenschaften der wirklichen Stadt völlig unerheblich sind. Die Länge einer Brücke spielt keine Rolle. Auch die genaue Form der Inseln, die Breite des Flusses oder die Gehgeschwindigkeit verändern nicht, welche Landbereiche durch welche Brücken verbunden sind. Relevant ist allein die Beziehung zwischen den Bereichen und den Übergängen.

Aus dieser Einsicht entstand eine einfache, aber mächtige Darstellung. Jeder zusammenhängende Stadtteil wird als Knoten oder Ecke dargestellt. Jede Brücke wird als Kante oder Verbindungslinie eingezeichnet. Die reale Karte wird dadurch zu einem schematischen Graphen. Man kann die Knoten verschieben, die Linien gerade oder gebogen zeichnen und die Größenverhältnisse verändern, ohne die mathematische Information zu verlieren.

  • Ein Knoten steht für einen erreichbaren Landbereich.
  • Eine Kante steht für eine Brücke zwischen zwei Bereichen.
  • Die Reihenfolge der Kanten beschreibt den Spaziergang.
  • Die Form und Länge der Darstellung sind für die Grundfrage unwichtig.
Abstrakte Darstellung eines Netzwerks aus Knoten und verbindenden Wegen
Durch die Reduktion auf Knoten und Kanten wird sichtbar, welche Verbindungen für einen vollständigen Rundgang entscheidend sind.

Euler bezeichnete diesen Zugang als Geometria situs, also als Geometrie der Lage. Im Mittelpunkt stehen nicht Längen, Winkel oder Flächen, sondern Positionen und Verbindungen. Seine historische Abhandlung Solutio problematis ad geometriam situs pertinentis legte dar, dass es bei solchen topologischen Fragestellungen nicht auf Messgrößen, sondern auf die Struktur der Beziehungen ankommt. Damit berührte Euler sehr früh Ideen, die später für Topologie und Graphentheorie zentral wurden.

Die Abstraktion ist mehr als eine elegante Zeichentricktechnik. In der Stadtkarte können zahlreiche Details vom Wesentlichen ablenken. Im Graphen wird die Frage sichtbar: Lässt sich jede Kante genau einmal in einer einzigen zusammenhängenden Kantenfolge durchlaufen? Sobald das Problem so formuliert ist, wird systematisches Zählen wichtiger als zufälliges Ausprobieren.

Der mathematische Beweis über den Grad der Knoten

Der entscheidende Begriff ist der Grad eines Knotens. Er gibt an, wie viele Kanten an diesem Knoten anliegen. Ein Stadtteil mit drei Brücken besitzt also den Grad drei, ein Bereich mit fünf Brücken den Grad fünf. Für den historischen Königsberger Graphen ergeben sich für die vier Landbereiche die Knotengrade 3, 3, 3 und 5.

Warum sind diese Zahlen so wichtig? Stell dir einen Spaziergang vor, der einen Stadtteil als Zwischenstation erreicht. Für das Betreten wird eine Brücke benötigt, für das Verlassen eine weitere. Die benutzten Kanten treten an einem solchen Zwischenknoten daher paarweise auf. Jede Ankunft muss mit einem späteren Abgang ausgeglichen werden. Deshalb ist der Grad eines gewöhnlichen Durchgangsknotens gerade.

Eine Ausnahme gibt es am Anfang und am Ende. Am Startpunkt kann eine unbenutzte Brücke zunächst nur zum Verlassen dienen. Am Zielpunkt kann eine Brücke nur zum Ankommen dienen. Genau zwei Knoten dürfen deshalb bei einem offenen Rundgang einen ungeraden Grad haben. Beginnt und endet der Spaziergang am selben Ort, fällt auch diese Ausnahme weg, sodass alle Knotengrade gerade sein müssen.

Landbereich Anzahl der angrenzenden Brücken Knotengrad
Bereich A 3 Brücken ungerade
Bereich B 3 Brücken ungerade
Bereich C 3 Brücken ungerade
Bereich D 5 Brücken ungerade

Damit besitzt der Königsberger Graph vier ungerade Knoten. Das ist zu viel: Für einen offenen Weg wären höchstens zwei ungerade Knoten erlaubt, für einen geschlossenen Rundgang gar keiner. Die gewünschte Überquerung ist folglich unmöglich. Wichtig ist, dass dieser Schluss nicht auf dem Scheitern einiger Versuche beruht. Er beweist, dass jede denkbare Route scheitern muss.

Ein weiterer Kontrollblick bestätigt die Struktur. Die Summe der Knotengrade beträgt 3 + 3 + 3 + 5 = 14. Jede der sieben Brücken wird an zwei Enden gezählt, daher muss die Summe genau 2 mal 7 = 14 ergeben. Diese einfache Zählregel, oft als Handschlaglemma bezeichnet, zeigt zugleich, warum in jedem endlichen Graphen die Zahl der Knoten mit ungeradem Grad gerade ist. Vier ungerade Knoten sind also möglich, aber für die gewünschte Traversierung nicht ausreichend günstig.

Vom Spaziergang zur präzisen Graphentheorie

Aus Eulers Argument lässt sich ein allgemeiner Satz gewinnen. In einem zusammenhängenden Graphen existiert eine geschlossene Eulertour, also eine Kantenfolge, die jede Kante genau einmal benutzt und zum Ausgangspunkt zurückkehrt, genau dann, wenn jeder Knoten geraden Grad besitzt. Ein offener Eulerweg, der an einem anderen Knoten endet als er beginnt, existiert genau dann, wenn es genau zwei Knoten mit ungeradem Grad gibt.

Die Begriffe lassen sich Schritt für Schritt auseinanderhalten. Eine Kantenfolge darf Knoten mehrfach besuchen. Ein Weg wird je nach Definition strenger gefasst, in elementaren Darstellungen meist als Folge ohne wiederholte Knoten. Für Eulers Problem ist jedoch vor allem entscheidend, dass keine Kante wiederholt werden darf. Ein Eulerweg ist deshalb eine Kantenfolge ohne Kantenwiederholung, die sämtliche Kanten des Graphen erfasst. Ein geschlossener Eulerweg wird Eulerkreis oder Eulertour genannt.

  1. Prüfe zunächst, ob alle relevanten Knoten in einem zusammenhängenden Bereich liegen.
  2. Zähle für jeden Knoten die anliegenden Kanten.
  3. Bei null ungeraden Knoten ist ein geschlossener Eulerweg möglich.
  4. Bei genau zwei ungeraden Knoten ist ein offener Eulerweg möglich, der an diesen beiden Knoten beginnt und endet.
  5. Bei mehr als zwei ungeraden Knoten ist eine vollständige Kantenüberquerung ohne Wiederholung unmöglich.

Diese Regel macht deutlich, warum nicht die Zahl der Knoten, sondern die Art ihrer Vernetzung entscheidend ist. Ein Graph kann viele Knoten besitzen und trotzdem eine Eulertour erlauben. Umgekehrt kann ein kleiner Graph mit wenigen Kanten scheitern, wenn seine ungeraden Grade ungünstig verteilt sind. Eine anschauliche Einführung mit Anwendungen auf Spaziergänge und Buslinien zeigt, wie diese Bedingungen formal aus der Eingangs-Ausgangs-Logik folgen.

Das Haus vom Nikolaus und moderne Anwendungsfälle

Das Zeichenspiel „Das ist das Haus vom Nikolaus“ ist eine direkte Anwendung des Eulerwegs. Die Figur soll in einem Zug gezeichnet werden, ohne den Stift abzusetzen und ohne eine Linie doppelt zu zeichnen. Betrachtet man die Ecken als Knoten und die Linien als Kanten, erkennt man zwei Knoten mit ungeradem Grad. Deshalb muss der Zeichenweg an einer dieser beiden Ecken beginnen und an der anderen enden.

Warum funktioniert ein Start an den unteren Ecken? Dort liegen die ungeraden Knotengrade. Beginnt der Stift an einem solchen Knoten, kann die dortige unausgeglichene Kante den Anfang bilden. An allen inneren Knoten werden die Linien dagegen paarweise betreten und verlassen. Wer an einer falschen Ecke startet, erzeugt unterwegs eine zusätzliche offene Stelle, an der die noch nicht gezeichneten Linien nicht mehr passend erreicht werden können.

  • Für jede Linie wird geprüft, ob sie bereits benutzt wurde.
  • Bei einem Zwischenknoten müssen Ankunft und Weitergang zusammenpassen.
  • Der Start- und der Endknoten tragen die beiden ungeraden Grade.
  • Die Reihenfolge der Linien ist wichtig, nicht die optische Form des Hauses.

Dasselbe Prinzip begegnet in praktischen Verkehrs- und Versorgungsproblemen. Bei der Müllabfuhr oder der Postzustellung sollen bestimmte Straßen möglichst vollständig befahren werden. Hat das Straßennetz zu viele ungerade Knoten, müssen einzelne Straßen wiederholt befahren werden. Das sogenannte Briefträgerproblem sucht dann eine Route, die alle geforderten Kanten abdeckt und die notwendige Wiederholung möglichst gering hält. Aus dem ursprünglichen Unmöglichkeitsbeweis wird so ein Optimierungsproblem.

Auch moderne Kommunikationsnetze lassen sich als Graphen beschreiben. Router oder Rechner sind Knoten, Verbindungen sind Kanten, und Datenpakete folgen Wegen durch dieses Netzwerk. Routingverfahren müssen nicht immer jede Verbindung genau einmal verwenden, doch Eulers abstrakte Denkweise bleibt grundlegend: Zuerst wird festgelegt, welche Objekte verbunden sind, danach werden Eigenschaften wie Erreichbarkeit, Ausfallsicherheit, kürzeste Wege oder Lastverteilung untersucht. So reicht Eulers Idee bis in Informatik, Logistik, Netzwerktechnik und Datenanalyse.

Wie abstrakte Ideen bis heute unsere vernetzte Welt ordnen

Das Königsberger Brückenproblem lehrt eine besonders wertvolle mathematische Haltung. Wenn ein Problem durch seine vielen sichtbaren Einzelheiten unübersichtlich wird, lohnt sich die Frage, welche Informationen tatsächlich Einfluss auf die Lösung haben. Euler ließ Brückenlängen, Uferformen und Entfernungen bewusst weg und behielt nur die Verbindungen. Gerade dieses Weglassen machte den Beweis möglich.

Der wichtigste Merksatz lautet: Bei einer Euleraufgabe zählt der Knotengrad, nicht die Schönheit der Zeichnung. Zähle die ungeraden Knoten, prüfe die Zusammenhangsbedingung und unterscheide zwischen offenem Eulerweg und geschlossenem Eulerkreis. Wer diese Schritte sicher beherrscht, kann nicht nur ein historisches Rätsel lösen, sondern auch Verkehrsnetze, Versorgungsrouten und digitale Verbindungen strukturierter betrachten. Aus einem Spaziergang über sieben Brücken wurde so ein dauerhaftes Werkzeug, mit dem sich eine vernetzte Welt verständlich ordnen lässt.