Direkt zum Inhalt

Die fabelhafte Welt der Mathematik: Das unmögliche Haus vom Nikolaus

Wer versucht, das berühmte Häuschen von einem der drei oberen Punkte aus zu zeichnen, wird bald frustriert sein. Die Graphentheorie erklärt, warum Scheitern vorprogrammiert ist.
Verschiedene Häuser im Schnee
Welches ist wohl das Haus vom Nikolaus?

Bald steht der Nikolaustag vor der Tür. Falls Sie jemanden an diesem Tag ärgern möchten, könnten Sie die Person auffordern, das »Haus vom Nikolaus« zu zeichnen – und sie dabei an einem der drei oberen Ansatzpunkte beginnen lassen. Bei der berühmten Aufgabe, die von dem Kinderreim »Das ist das Haus vom Ni-ko-laus« begleitet wird, muss man fünf Punkte (vier davon sind in einem Quadrat angeordnet, der fünfte befindet sich mittig über den oberen zwei Punkten), ohne den Stift abzusetzen, zu einem kleinen Häuschen verbinden. Dabei darf keine Linie doppelt gezeichnet werden. Es gibt viele verschiedene Möglichkeiten, das umzusetzen. Doch wenn man an einem der drei oberen Punkte startet, mündet das zwangsläufig in eine Sackgasse. Warum das so ist, hat Leonhard Euler im 18. Jahrhundert herausgefunden.

Der Kinderreim hängt nämlich mit einem Problem zusammen, das auf den ersten Blick vollkommen anders aussieht: dem Königsberger Brückenproblem. Im 18. Jahrhundert standen in der damaligen preußischen Stadt, die heute Kaliningrad heißt und zu Russland gehört, sieben Brücken, die über die Pregel führten. Der Fluss teilte die Stadt in vier Gebiete auf, zwei davon waren sogar Inseln: Lomse (heute Oktyabrsky-Insel) und Kneiphof (dort gab es wirklich einige Kneipen). Die Bürger der Stadt suchten irgendwann nach einer Route für einen Spaziergang, bei dem man jede Brücke genau einmal überquert. Doch niemandem gelang es, einen solchen Weg zu finden – gleichzeitig konnte niemand zweifelsfrei beweisen, dass es keinen gibt.

Die sieben Brücken im alten Königsberg

Gelöst hat das Problem niemand Geringerer als der große Mathematiker Leonhard Euler (1707–1783), der selbst nie in Königsberg gewohnt hat. Die knifflige Aufgabe teilte ihm mutmaßlich sein Bekannter Karl Leonhard Gottlieb Ehler mit, der damalige Bürgermeister von Danzig. Dieser hatte einen Teil seines Studiums in Königsberg absolviert und stand in Kontakt mit Euler. Anfangs zeigte sich der Mathematiker wenig begeistert, wie aus einem 1736 verschickten Brief deutlich wird: »(...) diese Art von Lösung hat wenig mit Mathematik zu tun, und ich verstehe nicht, warum Ihr sie von einem Mathematiker und nicht von einem anderen erwartet, denn die Lösung beruht allein auf der Vernunft (...)«

Viele Menschen denken, Mathematik sei kompliziert und öde. In dieser Serie möchten wir das widerlegen – und stellen unsere liebsten Gegenbeispiele vor: von schlechtem Wetter über magische Verdopplungen hin zu Steuertricks. Die Artikel könnt ihr hier lesen.

Offenbar ließ ihn das Problem aber doch nicht ganz los. Denn 1735 veröffentlichte Euler eine Lösung, welche die Mathematik nachhaltig prägen sollte. Dabei stützte er sich wohl auf einen Ansatz seines Kollegen Gottfried Wilhelm Leibniz (1646–1716), die so genannte Geometria situs (Geometrie des Ortes). Dabei geht es darum, die Position von Objekten zu untersuchen, ohne explizit Distanzen einzuführen oder zu verwenden. Es kommt also nicht mehr auf die exakten geometrischen Details einer Figur an, sondern auf ihre groben Eigenschaften (Hat sie Löcher? Ist sie zusammenhängend?).

Über sieben Brücken musst du gehen

Euler erkannte, dass auch das Königsberger Brückenproblem nicht von einzelnen Details abhängt: Die Aufgabe verändert sich nicht, wenn eine Brücke länger oder kürzer wird oder weiter rechts oder links auf der Landkarte positioniert ist. Wenn man das Problem auf das Wesentliche zusammenstampft, lässt es sich viel einfacher ausdrücken: Es gibt vier Punkte (die vier Stadtbezirke), die durch sieben Linien (die Brücken) miteinander verbunden sind. Ist es möglich, die Linien mit einem Stift (ohne abzusetzen) so nachzuzeichnen, dass man jeden Weg genau einmal durchläuft?

Ein Graph für das Königsberger Brückenproblem | Die schwarzen Linien sind die Brücken, die grünen Punkte die damit verbundenen Stadtteile.

Einige von Ihnen werden spätestens jetzt die Ähnlichkeit zu unserer ursprünglichen Fragestellung, nämlich dem Haus vom Nikolaus, wiedererkennen. Denn auch hier ging es darum, Punkte mit Linien zu verbinden und dabei jede genau einmal abzufahren. Indem Euler das Brückenproblem derart abstrahierte, hat er – wahrscheinlich ohne es zu ahnen – ein neues Gebiet der Mathematik geschaffen: die Graphentheorie. Das ist die Wissenschaft von Netzwerken, also von Punkten, die durch Kanten verbunden sind. Dabei ist es irrelevant, wie lang eine Kante ist oder wo genau der Punkt positioniert ist – es geht nur um die Beziehungen der Punkte zueinander. Als Euler den Graphen betrachtete, der sich aus dem Königsberger Brückenproblem ergibt, stellte er fest, dass alle Knoten eine ungerade Anzahl an Kanten besitzen. Und genau das führt zu Problemen.

Anzahl der Linien an jedem Knoten | In den zwei Graphen lässt sich nachvollziehen, wie viele Kanten von jedem Knoten ausgehen.

Um das zu verstehen, können wir den südlichsten Punkt (nennen wir ihn A) im Graphen betrachten, der drei Verbindungen zu den anderen Knoten hat. Man kann den Punkt theoretisch so oft betreten, wie man möchte, allerdings soll man jede Kante nur einmal durchlaufen. Angenommen, der Startpunkt der Route war ein anderer Punkt, dann ist man durch eine bestimmte Kante bei A angekommen. Möchte man A wieder verlassen, muss man also eine andere Brücke entlanggehen. Damit landet man bei anderen Punkten im Graphen, läuft dort irgendwie herum und wird dann zwangsweise wieder über eine andere Kante (da ja alle durchlaufen werden müssen) bei A landen. Dort angekommen kann man allerdings nicht mehr fliehen: Man ist bereits auf allen drei Brücken entlanggegangen (die eine führte hin, die zweite weg und die dritte schließlich wieder zu A). Das heißt: Wenn A drei Kanten hat und nicht der Startpunkt ist, muss der Knoten Endpunkt der Route sein.

Im Königsberger Brückenproblem gibt es weitere Knoten mit drei Verbindungen, zum Beispiel der östlichste, nennen wir ihn B. Dieser kann unmöglich Endpunkt der Tour sein, da das ja bereits A ist. Aber es gibt eine andere Möglichkeit, um jede Kante, die an B grenzt, nur einmal zu durchlaufen: wenn B der Startpunkt der Route ist. Man beginnt den Spaziergang also bei B, überquert eine Brücke, läuft irgendwie durch Königsberg herum, nimmt dann wieder eine andere Brücke zu B und verlässt den Ort wieder entlang der letzten, die übrig blieb. Solange A also der Zielort ist und B der Startpunkt, ist das Königsberger Brückenproblem lösbar.

Es gibt keine perfekte Route

Doch es gibt einen Haken: Es existiert ein dritter Punkt C (ganz im Norden), von dem drei Kanten ausgehen. Da Start und Ziel der Route bereits vergeben sind, kann man unmöglich jede der an C grenzenden Brücken nur einmal durchlaufen. Entweder man überquert sie nicht oder mehrmals. Gleiches gilt übrigens für jeden anderen Punkt mit einer ungeraden Anzahl von Verbindungen.

Mit dieser Erkenntnis konnte Euler auch den allgemeinen Fall des Brückenproblems beweisen: Man kann genau dann alle Kanten eines Graphen exakt einmal ablaufen, wenn jeder Knoten bloß eine gerade Anzahl von Verbindungen besitzt – oder wenn es genau zwei Knoten mit ungeraden Verbindungen gibt. Falls Letzteres gilt, ist der eine Knoten der Start- und der andere der Endpunkt der Route.

Beispiele für abgeänderte »Häuser vom Nikolaus« | Das Spiel »Das Haus vom Nikolaus« funktioniert bloß dann, wenn von jedem Punkt nur eine gerade Anzahl von Linien ausgeht – oder es exakt zwei Punkte mit einer ungeraden Anzahl von Linien gibt.

Das ist der Fall beim Haus vom Nikolaus: Die unteren beiden Punkte haben je drei Verbindungen, alle anderen besitzen hingegen eine gerade Anzahl an Kanten. Das heißt: Um das Häuschen zu zeichnen, muss man zwangsläufig in einer der unteren Ecken starten und in der anderen enden. Sonst scheitert der Versuch. Wenn Sie mir nicht glauben, versuchen Sie es ruhig! Und wenn Sie schon dabei sind: Können Sie herausfinden, auf wie viele Arten man das Haus vom Nikolaus zeichnen kann? Auf »Spektrum.de« hatten wir dazu auch schon ein Rätsel, viel Spaß damit!

​​Was ist euer Lieblingsmathetheorem? Schreibt es gerne in die Kommentare – und vielleicht ist es schon bald das Thema dieser Kolumne!

Schreiben Sie uns!

2 Beiträge anzeigen

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Partnerinhalte