Königsberger Brückenproblem

Die Sieben Brücken von Königsberg ist ein historisch berühmtes Problem der Mathematik. Leonhard Euler löste das Problem 1735. Dies führte zum Beginn der Graphentheorie. Dies führte dann zur Entwicklung der Topologie.

Die Stadt Königsberg in Preußen (heute Kaliningrad, Russland) wurde auf beiden Seiten des Pregels errichtet. Sie umfasste zwei große Inseln, die durch sieben Brücken miteinander und mit dem Festland verbunden waren.

Das Problem bestand darin, einen Weg durch die Stadt zu finden, indem jede Brücke nur einmal überquert werden musste. Die Inseln konnten auf keinem anderen Weg als über die Brücken erreicht werden. Jede Brücke muss jedes Mal vollständig überquert worden sein. Der Spaziergang muss nicht an der gleichen Stelle beginnen und enden. Euler bewies, dass es für das Problem keine Lösung gibt.

Karte von Königsberg zur Zeit Eulers, die den tatsächlichen Grundriss der sieben Brücken zeigt, wobei der Fluss Pregel und die Brücken hervorgehoben sind

Eulersche Analyse

Zunächst wies Euler darauf hin, dass die Wahl der Route innerhalb jeder Landmasse keine Rolle spielt. Die einzige wichtige Eigenschaft einer Route ist die Reihenfolge, in der die Brücken überquert werden. Daher änderte er das Problem in abstrakte Begriffe. Damit legte er die Grundlagen der Graphentheorie. Er entfernte alle Merkmale mit Ausnahme der Liste der Landmassen und der sie verbindenden Brücken. In der Sprache der Graphentheorie ersetzte er jede Landmasse durch einen abstrakten "Vertex" oder Knoten. Dann ersetzte er jede Brücke durch eine abstrakte Verbindung, eine "Kante". Eine Kante (Straße) hielt fest, welche zwei Scheitelpunkte (Landmassen) verbunden waren. Auf diese Weise bildete er einen Graphen.

→ →

Die gezeichnete Grafik ist ein abstraktes Bild des Problems. Die Kanten können also beliebig miteinander verbunden werden. Wichtig ist nur, ob zwei Punkte verbunden sind oder nicht. Eine Änderung des Bildes des Graphen verändert nicht den Graphen selbst.

Als nächstes bemerkte Euler, dass man (außer an den Endpunkten des Spaziergangs) immer dann, wenn man einen Scheitelpunkt über eine Brücke betritt, den Scheitelpunkt über eine Brücke verlässt. Bei jedem Durchgang des Graphen ist die Anzahl der Eintritte in einen Scheitelpunkt gleich der Anzahl der Austritte aus dem Scheitelpunkt. Wenn jede Brücke genau einmal überquert worden ist, folgt daraus, dass für jede Landmasse (mit Ausnahme der für Start und Ziel gewählten) die Anzahl der Brücken, die diese Landmasse berühren, gerade sein muss. Denn wenn es n Brücken gibt, wird sie genau 2n Mal überquert. Alle vier Landmassen des ursprünglichen Problems werden jedoch von einer ungeraden Anzahl von Brücken berührt (eine Brücke wird von 5 Brücken berührt, und jede der anderen drei wird von 3 berührt). Es gibt höchstens zwei Massen, die die Endpunkte einer Wanderung sein können. Der Vorschlag eines Spaziergangs, bei dem jede Brücke einmal überquert wird, führt also zu einem Widerspruch.

In moderner Sprache zeigt Euler, dass es von den Graden der Knoten abhängt, ob ein Gang durch einen Graphen, der jede Kante einmal überquert, möglich ist oder nicht. Der Grad eines Knotens ist die Anzahl der Kanten, die ihn berühren. Euler zeigt, dass eine notwendige Bedingung für den Gang ist, dass der Graph verbunden ist und genau null oder zwei Knoten ungeraden Grades hat. Dieses von Euler angegebene Ergebnis wurde später von Carl Hierholzer bewiesen. Eine solche Wanderung wird heute als Euler'scher Weg oder Eulersche Wanderung bezeichnet. Wenn es Knoten ungeraden Grades gibt, dann beginnt jeder Euler'sche Pfad bei einem von ihnen und endet bei dem anderen. Da der Graph, der das historische Königsberg darstellt, vier Knoten ungeraden Grades hat, kann es keinen Euler'schen Pfad geben.

Eulers Werk wurde am 26. August 1735 an der St. Petersburger Akademie vorgestellt. Es wurde als Solutio problematis ad geometriam situs pertinentis (Die Lösung eines Problems im Zusammenhang mit der Geometrie der Position) in der Zeitschrift Commentarii academiae scientiarum Petropolitanae im Jahre 1741 veröffentlicht. Sie ist in englischer Sprache in The World of Mathematics erhältlich.

Bedeutung in der Geschichte der Mathematik

In der Geschichte der Mathematik gilt die Euler'sche Lösung des Königsberger Brückenproblems als der erste Satz der Graphentheorie. Die Graphentheorie ist ein Fach, das heute allgemein als ein Zweig der Kombinatorik angesehen wird.

Gegenwärtiger Zustand der Brücken

Zwei der sieben ursprünglichen Brücken wurden bei der Bombardierung von Königsberg im Zweiten Weltkrieg zerstört. Zwei weitere wurden später abgerissen. Sie wurden durch eine moderne Autobahn ersetzt. Die drei anderen Brücken sind erhalten geblieben, obwohl nur zwei von ihnen aus der Zeit Eulers stammen (eine wurde 1935 wieder aufgebaut). Somit gab es im Jahr 2000 im Kaliningrader Gebiet fünf Brücken.

In Bezug auf die Graphentheorie haben jetzt zwei der Knoten den Grad 2 und die anderen beiden den Grad 3. Daher ist ein Eulerianischer Pfad jetzt möglich, aber da er auf einer Insel beginnen und auf der anderen enden muss, ist er für Touristen unpraktisch.

Fragen und Antworten

F: Was ist das Problem der Sieben Brücken von Königsberg?

A: Die Sieben Brücken von Königsberg sind ein berühmtes mathematisches Problem, bei dem es darum geht, einen Weg durch die Stadt zu finden, indem man jede der sieben Brücken einmal und nur einmal überquert.

F: Wer hat das Problem der sieben Brücken von Königsberg gelöst?

A: Leonhard Euler löste das Problem der sieben Brücken von Königsberg im Jahr 1735.

F: Wozu hat die Lösung des Problems der Sieben Brücken von Königsberg geführt?

A: Die Lösung des Problems der Sieben Brücken von Königsberg führte zu den Anfängen der Graphentheorie, die dann zur Entwicklung der Topologie führte.

F: Wo befindet sich Königsberg?

A: Königsberg liegt in Preußen, das heute zu Kaliningrad, Russland, gehört.

F: Wie war der Grundriss von Königsberg?

A: Königsberg wurde auf beiden Seiten des Flusses Pregel angelegt und umfasste zwei große Inseln, die durch sieben Brücken miteinander und mit dem Festland verbunden waren.

F: Was waren die Voraussetzungen, um das Problem der sieben Brücken von Königsberg zu lösen?

A: Die Aufgabe bestand darin, einen Weg durch die Stadt zu finden, bei dem jede Brücke nur einmal überquert wird, wobei jede Brücke jedes Mal vollständig überquert werden muss. Die Inseln konnten nur über die Brücken erreicht werden, und der Spaziergang musste nicht am selben Ort beginnen und enden.

F: Hat Euler bewiesen, dass das Problem der sieben Brücken von Königsberg eine Lösung hat?

A: Nein, Euler hat bewiesen, dass es für das Problem der sieben Brücken von Königsberg keine Lösung gibt.