Königsberger Brückenproblem

Graphentheorie

Basiswissen｜ Fragestellung｜ Die kombinatorische Explosion｜ Lösung｜ Abstraktion｜ Graphentheorie｜ Hinreichend und notwendig｜ Fußnoten

Basiswissen

Man soll einen Weg über 7 Brücken finden, bei der man jede Brücke nur genau einmal überqueren muss. Tatsächlich gibt es keine Lösung. Interessant ist die Frage, woran man das auf leicht Weise erkennen kann. Das Problem, benannt nach der ehmaligen ostpreußischen Stadt Königsberg, dem heutigen Kaliningrad, gilt auch als die Geburtststunde eines großen Teilgebietes der Mathematik, der Graphentheorie. Das Problem wurde um 1736 von dem schweizer Mathematiker Leonhard Euler bearbeitet und im Jahr 1741 veröffentlicht.^[1]

Bildbeschreibung und Urheberrecht — Gibt es einen Weg, dass man alle sieben Brücken genau einmal abläuft? Man sieht von links nach rechts, wie das Problem zunehmend abstrahiert wurde. Alles für das Denken unwesentliche wurde weggelassen. Tatsächlich gibt es keine Lösung für das Problem. © Bogdan Giuşcă Chrismartin Mark Foskey, Booyabazooka ☛

Fragestellung

Durch die Stadt Königsberg fließt der Fluss Pregel. In dem Fluss liegen zwei Inseln. Zur in Bildern meist links abgebildeten westlichen Insel führen zwei Brücken vom nördlichen und zwei Brücken vom südlichen Ufer. Zur anderen, der rechten Insel, führt je ein Brücke vom nördlichen und eine Brücke vom südlichen Ufer. Und dann gibt es noch eine Brücke, die die zwei Inseln untereinander verbindet. Insgesamt gibt es also 4 verschiedene Landbereiche und 7 verschiede Brücken:

Landbereich 1: nördliche Stadt (im Bild oben)

Landbereich 2: südliche Stadt (im Bild unten)

Landbereich 3: westliche Insel (im Bild links)

Landbereich 4: östliche Insel (im Bild rechts)

Brücke 1: Von der Nordstadt zur Westinsel

Brücke 2: Von der Nordstadt zur Westinsel

Brücke 3: Von der Südstadt zur Westinsel

Brücke 4: Von der Südstadt zur Westinsel

Brücke 5: Von der Nordstadt zur Ostinsel

Brücke 6: Von der Südstadt zur Osttinsel

Brücke 7: Von der Westinsel zur Ostinsel

Zwei verwandte Fragen zusammen bezeichnet man heute als das Königsberger Brückenproblem. Die erste Frage ist die weniger eng formuliert:

Frage 1: gibt es irgendeinen Weg bei dem man jede Brücke nur genau einmal überqueren muss?

Frage 2: gibt es einen geschlossenen Weg bei dem man jede Brücke nur genau einmal überqueren muss?

Bei Frage 1 muss man am Ende nicht unbedingt wieder dort heraus kommen, wo man auch angefangen hat. Erlaub ist ein sogenanter offener Pfad oder Weg. Bei Frage 2 soll man an Ende wieder dort stehen, wo man mit seinem Weg oder Pfad auch begonnen hat. Einen solche Weg oder Pfad bezeichnet man auch als geschlossen oder auch als Eulerkreis.^[2]

Die kombinatorische Explosion

Um nun einen offenen oder geschlossenen Weg zu finden, bei dem man jede Brücke genau einmal benutzt, kann man durch Probieren vorgehen. Findet man einen passenden Weg, ist kann man die entsprechende Frage mit einem Ja beantworten. Die Frage ist dann gelöst. Solange man aber noch keinen Weg gefunden hat, bleibt die Frage unbeantwortet. Die Lösungsmethode des Probieren kann also dazu führen, dass man am Ende alle möglichen Weg ausprobiert haben muss. Obwohl es nur 4 Landflächen und 7 Brücken gibt, ist die Anzahl möglicher Pfade, die man überprüfen müsste, sehr groß. Durch die vielen Varianten unterschiedlicher Reihenfolgenden ensteht eine 👉 Kombinatorische Explosion

Lösung

Abstraktion

Die Lösung über reine Probieren kann sehr schnell sehr aufwändig werden. Kann man das Problem auch denkerisch lösen? Ein erster Schritt hin zu einer denkerischen, analytischen Lösung ist die Abstraktion. Man streift alles von der Fragestellung ab, was für das eigentliche Denken nicht wichtig ist. Dieses Abstreifen nennt man abstrahieren.

Wie die Häuser in Königsberg aussehen ist nicht wichtig.

Wie lang und breit die Inseln sind nicht nicht wichtig.

Wo der Pregel welche Biegung macht ist nicht wichtig.

Die Länge und Breite der Brücken sind nicht wichtig.

Was am Ende eines konsequenten Abstrahierens übrig bleibt sind nur die für die Problemlösun wichtigen Aspekte des ursprünglichen Problems. Und das ist hier:

Es gibt 4 Landmassen, die vier Inseln. Diese kann man als reine Kreise darstellen.

Es gibt 7 Verbindungen zwischen den vier Landmassen. Diese kann man als reine Linien darstellen.

Was also am Ende der Abstraktion übrig bleibt sind vier Kreise und sieben Linien, die passend Punkte miteinander verbinden. Man nennt die Kreise Knoten und die Linien. Das Auge wird jetzt nicht mehr von vielleicht interessanten aber an sich unwichtigen Details abgelenkt. Mit diesem stark vereinfachten Bild kann man denken. Das ganze Bild heißt 👉 planarer Graph

Graphentheorie

Die stark vereinfachte Darstellung des Problems kann jetzt innerhalb der Graphentheorie betrachtet werden. Dort kann man das Problem noch weiter vereinfachen. Man könnte sich erst einmal Beispiel mit nur zwei Knoten und drei Kanten oder ähnliche einfache Versionen betrachten. Über solche Vereinfachungen kriegt man dann oft Ideen für allgemeine Regeln. Solche einfachen und allgemeinen Regeln für alle sogenannten zusammenhängende planaren Graphen sind:

Einen Weg, der jede Kante genau einmal benutzt (Eulerpfad), gibt es nur, wenn genau 0 oder 2 Knoten eine ungerade Anzahl von Kanten haben.

Einen Rundgang (Eulerkreis) gibt es nur, wenn alle Knoten eine gerade Anzahl von Kanten haben sind.

In welche Richtung ein Begründung oder ein Beweis gehen können, deutete der amerikanische Mathematiker Joel David Hamkins an. In einem Schulprojekt mit 8 Jahre alte Mädchen schrieb er im Jahr 2014:

ZITAT:

"Wir haben besprochen, dass manche Graphen keinen Eulerweg oder -kreis besitzen. Existiert ein Kreis, so verlässt man jeden Knoten an einer neuen Kante; daher muss an jedem Knoten eine gerade Anzahl von Kanten vorhanden sein. Bei einem Eulerweg haben Start- und Endknoten (sofern verschieden) einen ungeraden Grad, während alle anderen Knoten einen geraden Grad haben."^[7]

Oft kommt es vor, dass man mit der Methode der Vereinfachung gute Idee für allgemeine Regeln bekommt, der strenge mathematische Beweis aber erst lange Zeit später - bis zu 300 Jahre! - kommt.^[6] Für das spezielle Problem der 7 Brücken über den Pregel in Königsberg gilt dann.

Im Königsberger Graphen hat jeder der vier Knoten eine ungerade Anzahl von Brücken.

Damit gibt es weder einen Eulerpfad (offener Weg) noch einen Eulerkreis (geschlossener Weg).

Die Antwort, ob es einen offenen oder geschlossenen Weg gibt, bei dem man jede Brücke nur genau einmal überquert ist also ein klares Nein.^[5]

Hinreichend und notwendig

Das Königsberger Brückenproblem und seine allgemeine Lösung zeigt auch noch sehr schon auf was eine notwendige und eine hinreichende Bedingung ist. Betrachten wir uns noch einmal die Bedingungen für eine Lösung. Für die Lösung für irgendeinen planaren Graphen gilt:

Offener Pfad: einen Weg, der jede Kante genau einmal benutzt (Eulerpfad), gibt es nur, wenn genau 0 oder 2 Knoten eine ungerade Anzahl von Kanten haben.

Geschlossner Pfad: einen Rundgang (Eulerkreis) gibt es nur, wenn alle Knoten eine gerade Anzahl von Kanten haben sind.

Beide Bedingungen sind für ihren jeweiligen Fall notwendig. Sie müssen erfüllt sein. Sie sind aber gleichzeitig auch hinreichend.^[8] Das heißt, wenn man sie beim Zeichnen eines planaren Graphen einhält, dann hat man sicher einen solchen Graphen vor sich, für den es eine Lösung gibt. Die Lösung zu finden kann äußerst schwer werden. Aber man kann sicher sein, dass sich die Suche lohnen wird. Siehe auch Hinreichend und notwendig (externer Link)

Fußnoten

[1] Eulers original Fassung auf Latein: "Problema autem hoc, quod mihi satis notum esse perhibebatur, erat sequens: Regiomonti in Borussia esse insulam A der Kneiphof dictam, fluuiumque eam cingentem in duos diuidi ramos, quemadmodum ex figura videre licet: ramos vero huius fluuii septem instructos esse pontibus, a, b, c, d, e, f, et g. Circa hos pontes iam ista proponebatur quaestio, num quis cursum ita instituere queat, vt per singulos pontes semel et non plus quam semel transeat." Auf Deutsch: "Das Problem, das mir als hinreichend bekannt galt, war folgendes: In Königsberg in Preußen soll es eine Insel A geben, genannt Kneiphof, und der sie umgebende Fluss soll sich in zwei Arme teilen, wie man aus der Abbildung sieht; diese Arme sollen mit sieben Brücken versehen sein, bezeichnet a, b, c, d, e, f und g. Über diese Brücken wurde nun die Frage gestellt, ob jemand eine Route so einrichten könne, dass er über jede einzelne der Brücken einmal und nicht mehr als einmal hinweggehe." In: Leonhard Euler: Solutio problematis ad geometriam situs pertinentis., in: Commentarii Academiae Scientiarum Imperialis Petropolitanae, Bd. 8 (gedruckt 1736, erschienen 1741), S. 128–140. Online: https://la.wikisource.org/wiki/Solutio_problematis_ad_geometriam_situs_pertinentis

[2] Bei einem Eulerpfad oder Eulerweg wird offen gelassen, ob man am Ende wieder am Startpunkt herauskommen muss. Bei einem Eulerkreis, der immer geschlossen sein muss, ist das nicht erlaubt. Siehe auch 👉 Eulerkreis

[3] Gustav Theodor Hoffheinz: Die sieben Brücken in Königsberg. In: Altpreußische Monatsschrift, N. F., 1881, 18, S. 282 ff.

[4] Wladimir Velminski: Leonhard Euler. Die Geburt der Graphentheorie. Kulturverlag Kadmos, Berlin 2008, ISBN 978-3-86599-056-3.

[5] Die Antwort nach Leonhard Euler: "In casu igitur pontium transeundorum Regiomontano [Figura 1.], quia in insulam A quinque pontes deducunt a, b, c, d, e, necesse est, ut in designatione transitus per hos pontes littera A ter adeo debeat, litterarum vero B, C, et D unaquaeque bis; id quod in serie litterarum omnino fieri nequit. Ex quo perspicuum est, per septem pontes Regiomontanos talem transitum institui non posse." Auf Deutsch: "Im Fall der zu überquerenden Brücken von Königsberg ([Abbildung 1]), da in die Insel A fünf Brücken führen (a, b, c, d, e), muss in der Darstellung des Durchgangs durch diese Brücken der Buchstabe A dreimal vorkommen; die Buchstaben B, C und D dagegen je zweimal. Dies aber kann in einer Buchstabenfolge überhaupt nicht geschehen. Daraus ist klar ersichtlich, dass ein solcher Durchgang über die sieben Brücken von Königsberg nicht möglich ist." In: Leonhard Euler: Solutio problematis ad geometriam situs pertinentis., in: Commentarii Academiae Scientiarum Imperialis Petropolitanae, Bd. 8 (gedruckt 1736, erschienen 1741), S. 128–140.

[6] Schon um das Jahr 1650 wurde die Vermutung geäußert, dass es für die Gleichung aⁿ+bⁿ=cⁿ keine Lösung gibt, wenn man nur mit natürlichen Zahlen für die Buchstaben a, b, c und n einsetzen darf. Es dauerte über 300 Jahre, bis die Vermutung dann auch endlich bewiesen wurde. Siehe dazu 👉 Großer Fermatscher Satz

[7] "We discussed the fact that some graphs have no Eulerian path or circuit. If there is a circuit, then every time you enter a vertex, you leave it on a fresh edge; and so there must be an even number of edges at each vertex. With an Eulerian path, the starting and ending vertices (if distinct) will have odd degree, while all the other vertices will have even degree." In: Joel David Hamkin: Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits. 29. Mai 2014. Online: https://jdh.hamkins.org/math-for-seven-year-olds-graph-coloring-chromatic-numbers-eulerian-paths/

[8] "It is a remarkable fact that amongst connected finite graphs, those necessary conditions are also sufficient. One can prove this by building up an Eulerian path or circuit (starting and ending at the two odd-degree nodes, if there are such); every time one enters a new vertex, there will be an edge to leave on, and so one will not get stuck. If some edges are missed, simply insert suitable detours to pick them up, and again it will all match up into a single path or circuit as desired." Joel David Hamkin: Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits. 29. Mai 2014. Online: https://jdh.hamkins.org/math-for-seven-year-olds-graph-coloring-chromatic-numbers-eulerian-paths/