Sieben Brücken von Königsberg – Enzyklopädie

Klassisches Problem in der Topologie

Karte von Königsberg zu Eulers Zeiten mit der tatsächlichen Anordnung von den sieben Brücken, die den Fluss Pregel und die Brücken hervorheben

Die Sieben Brücken von Königsberg sind ein historisch bemerkenswertes Problem in der Mathematik. Die negative Resolution von Leonhard Euler aus dem Jahr 1736 [1] legte den Grundstein für die Graphentheorie und stellte die Idee der Topologie in den Vordergrund Darunter befanden sich zwei große Inseln – Kneiphof und Lomse – die durch sieben Brücken miteinander oder mit den beiden Festlandteilen der Stadt verbunden waren. Das Problem bestand darin, einen Spaziergang durch die Stadt zu planen, der jede dieser Brücken einmal und nur einmal überquerte.

Um die logische Aufgabe eindeutig zu spezifizieren, Lösungen, die beides beinhalten

  1. Das Erreichen einer anderen Insel oder eines anderen Festlandufers als über eine der Brücken oder
  2. der Zugang zu einer Brücke ohne Überquerung zu ihrem anderen Ende

ist ausdrücklich inakzeptabel.

Euler bewies, dass das Problem keine Lösung hat. Die Schwierigkeit, mit der er konfrontiert war, bestand in der Entwicklung einer geeigneten Analysetechnik und nachfolgender Tests, die diese Behauptung mit mathematischer Genauigkeit feststellten.

Eulers Analyse

Zunächst wies Euler darauf hin, dass die Wahl der Route innerhalb jeder Landmasse irrelevant ist. Das einzig wichtige Merkmal einer Route ist die Abfolge der überquerten Brücken. Dies ermöglichte es ihm, das Problem in abstrakten Begriffen neu zu formulieren (die Grundlagen der Graphentheorie zu legen), wobei alle Merkmale außer der Liste der Landmassen und der sie verbindenden Brücken beseitigt wurden. In modernen Begriffen ersetzt man jede Landmasse durch einen abstrakten "Eckpunkt" oder Knoten und jede Brücke durch eine abstrakte Verbindung, eine "Kante", die nur dazu dient, aufzuzeichnen, welches Paar von Eckpunkten (Landmassen) durch diese Brücke verbunden ist. Die resultierende mathematische Struktur wird als Graph bezeichnet.


 Konigsberg bridges.png
 7 bridges.svg
 Königsberg graph.svg

Da nur die Verbindungsinformationen relevant sind, kann die Form der bildlichen Darstellungen eines Diagramms auf irgendeine Weise verzerrt werden, ohne dass das Diagramm selbst geändert wird. Nur die Existenz (oder Abwesenheit) einer Kante zwischen jedem Knotenpaar ist signifikant. Beispielsweise spielt es keine Rolle, ob die gezeichneten Kanten gerade oder gekrümmt sind oder ob sich ein Knoten links oder rechts von einem anderen befindet.

Als nächstes beobachtete Euler, dass man (außer an den Endpunkten des Weges) den Scheitelpunkt immer dann verlässt, wenn man einen Scheitelpunkt über eine Brücke betritt. Mit anderen Worten, bei jedem Durchgang in der Grafik entspricht die Häufigkeit, mit der ein nicht-terminaler Scheitelpunkt betreten wird, der Häufigkeit, mit der er verlassen wird. Wenn nun jede Brücke genau einmal überquert wurde, ergibt sich, dass für jede Landmasse (mit Ausnahme derjenigen, die für Start und Ziel ausgewählt wurden) die Anzahl der Brücken, die diese Landmasse berühren, oder sein muss ( die Hälfte von ihnen wird in der bestimmten Durchquerung "auf" die Landmasse zu "durchquert"; die andere Hälfte "davon weg"). Alle vier Landmassen des ursprünglichen Problems werden jedoch von einer ungeraden Anzahl von Brücken berührt (eine wird von 5 Brücken berührt, und jede der anderen drei Brücken wird von 3 berührt). Da höchstens zwei Landmassen als Endpunkte eines Spaziergangs dienen können, führt der Vorschlag eines Spaziergangs, der jede Brücke einmal durchquert, zu einem Widerspruch.

In der modernen Sprache zeigt Euler, dass die Möglichkeit, durch einen Graphen zu gehen und jede Kante genau einmal zu durchlaufen, von den Graden der Knoten abhängt. Der Grad eines Knotens ist die Anzahl der Kanten, die ihn berühren. Das Argument von Euler zeigt, dass eine notwendige Bedingung für das Gehen der gewünschten Form ist, dass der Graph verbunden ist und genau null oder zwei Knoten ungeraden Grades hat. Diese Bedingung erweist sich auch als ausreichend – ein Ergebnis, das von Euler angegeben und später von Carl Hierholzer bewiesen wurde. Ein solcher Weg wird nun zu seinen Ehren als Euler-Weg oder Euler-Weg bezeichnet. Wenn es Knoten ungeraden Grades gibt, beginnt jeder Eulersche Pfad an einem von ihnen und endet am anderen. Da der Graph, der dem historischen Königsberg entspricht, vier Knoten ungeraden Grades hat, kann er keinen Eulerschen Pfad haben.

In einer alternativen Form des Problems wird ein Pfad angefordert, der alle Brücken überquert und auch denselben Start- und Endpunkt hat. Eine solche Wanderung nennt man eine Euler-Runde oder eine Euler-Tour . Eine solche Schaltung existiert nur dann, wenn der Graph verbunden ist und es überhaupt keine Knoten ungeraden Grades gibt. Alle Eulerschaltungen sind ebenfalls Eulerschaltungen, aber nicht alle Eulerschaltungen sind Eulerschaltungen.

Eulers Werk wurde am 26. August 1735 der Petersburger Akademie vorgestellt und als Solutio problematis ad geometriam situs pertinentis (Die Lösung eines Problems der Positionsgeometrie) in der Zeitschrift Commentarii academiae scientiarum Petropolitanae aus dem Jahr 1741. [3] Es ist in englischer Sprache in The World of Mathematics erhältlich.

Bedeutung in der Geschichte und Philosophie der Mathematik [

In der Geschichte der Mathematik gilt Eulers Lösung des Königsberger Brückenproblems als erster Satz der Graphentheorie und der erste wahre Beweis in der Theorie der Netzwerke, [4] ein Thema, das heute allgemein als Zweig der Kombinatorik angesehen wird. Kombinatorische Probleme anderer Art wurden seit der Antike in Betracht gezogen.

Die Erkenntnis von Euler, dass die Schlüsselinformation die Anzahl der Brücken und die Liste ihrer Endpunkte (und nicht ihre exakten Positionen) war, war ein Vorbote für die Entwicklung der Topologie. Der Unterschied zwischen dem tatsächlichen Layout und dem Diagrammschema ist ein gutes Beispiel für die Idee, dass sich die Topologie nicht mit der starren Form von Objekten befasst.

Wie Euler erkannte, handelt es sich bei der "Geometrie der Position" also nicht um "Messungen und Berechnungen", sondern um etwas Allgemeineres. Dies stellte die traditionelle aristotelische Auffassung in Frage, dass Mathematik die "Wissenschaft der Quantität" sei. Diese Ansicht passt zwar zur arithmetischen und zur euklidischen Geometrie, sie passte jedoch nicht zur Topologie und zu den abstrakteren Strukturmerkmalen, die in der modernen Mathematik untersucht wurden geht es nicht um eine Abstraktion oder ein Modell der Realität, sondern direkt um die reale Anordnung von Brücken. Daher kann die Gewissheit des mathematischen Beweises direkt auf die Realität zutreffen. [5]

Variationen

Die oben angegebene klassische Aussage des Problems verwendet nicht identifizierte Knoten Das heißt, sie sind alle gleich, mit Ausnahme der Art und Weise, wie sie miteinander verbunden sind. Es gibt eine Variante, bei der die Knoten identifiziert werden – jedem Knoten wird ein eindeutiger Name oder eine eindeutige Farbe zugewiesen.

Eine Variante mit roten und blauen Schlössern, einer Kirche und einem Gasthaus.

Das nördliche Ufer des Flusses wird vom Schloß oder der Blauer Prinz ; der Süden von dem des Roten Prinzen. Das Ostufer beherbergt die Ritcher-Kirche (19459027) der Brücke. und auf der kleinen Insel in der Mitte befindet sich ein Gasthaus.

Es versteht sich, dass die folgenden Probleme der Reihe nach behandelt werden sollten und mit einer Erklärung des ursprünglichen Problems beginnen sollten:

Da es unter den Einwohnern üblich ist, nach einigen Stunden im Gasthaus zu versuchen, die Brücken zu betreten sind viele zurückgekehrt, um sich zu erfrischen und Erfolg zu verschaffen. Keiner hat es jedoch geschafft, das Kunststück im Lichte des Tages zu wiederholen.

Brücke 8: Der Blaue Prinz der das Brückensystem der Stadt mit Hilfe der Graphentheorie analysiert hat, gelangt zu dem Schluss, dass die Brücken nicht begehbar sind. Er entwirft einen heimlichen Plan, um eine achte Brücke zu bauen, damit er abends auf seinem Schloß beginnen, über die Brücken laufen und am Gasthaus enden kann, um mit seinem Sieg zu prahlen. Natürlich möchte er, dass der Rote Prinz den Triumph des Roten Schlosses nicht wiederholen kann. Wo baut der Blaue Prinz die achte Brücke?

Brücke 9: Der Rote Prinz wütend auf die gordische Lösung seines Bruders, will eine neunte Brücke bauen, mit der er bei seiner beginnen kann ] Schloß über die Brücken gehen und am Gasthaus enden, um dem Bruder Schmutz ins Gesicht zu reiben. Als zusätzliche Rache sollte sein Bruder dann nicht mehr in der Lage sein, die Brücken von seinem Schloss bis zum Gasthaus wie zuvor zu betreten. Wo baut der Rote Prinz die neunte Brücke?

Brücke 10: Der Bischof hat diesen wütenden Brückenbau mit Bestürzung beobachtet. Es stört die Weltanschauung der Stadt und trägt schlimmer noch zu übermäßiger Trunkenheit bei. Er möchte eine zehnte Brücke bauen, die es allen Bewohnern erlaubt, über die Brücken zu gehen und in ihre eigenen Betten zurückzukehren. Wo baut der Bischof die zehnte Brücke?

Lösungen Bearbeiten

Reduzieren Sie die Stadt nach wie vor auf ein Diagramm. Färbe jeden Knoten ein. Wie beim klassischen Problem ist kein Eulerlauf möglich; die Färbung beeinflusst dies nicht. Alle vier Knoten haben eine ungerade Anzahl von Kanten.

Brücke 8: Euler-Wege sind möglich, wenn genau null oder zwei Knoten eine ungerade Anzahl von Kanten haben. Wenn wir 2 Knoten mit einer ungeraden Anzahl von Kanten haben, muss der Lauf an einem solchen Knoten beginnen und am anderen enden. Da das Puzzle nur 4 Knoten enthält, ist die Lösung einfach. Die gewünschte Wanderung muss am blauen Knoten beginnen und am orangefarbenen Knoten enden. Somit wird eine neue Kante zwischen den beiden anderen Knoten gezeichnet. Da sie früher jeweils eine ungerade Anzahl von Kanten hatten, müssen sie jetzt eine gerade Anzahl von Kanten haben, die alle Bedingungen erfüllen. Dies ist eine Änderung der Parität von einem ungeraden zu einem geraden Grad.

Brücke 9: Die 9. Brücke ist einfach, wenn die 8. Brücke gelöst ist. Der Wunsch ist es, die rote Burg freizugeben und die blaue Burg als Ausgangspunkt zu verbieten; Der orangefarbene Knoten bleibt das Ende der Wanderung und der weiße Knoten bleibt davon unberührt. Um die Parität der roten und blauen Knoten zu ändern, zeichnen Sie eine neue Kante zwischen ihnen.

Brücke 10: Die 10. Brücke führt uns in eine etwas andere Richtung. Der Bischof möchte, dass jeder Bürger zu seinem Ausgangspunkt zurückkehrt. Dies ist eine Euler-Schaltung und erfordert, dass alle Knoten von gleichem Grad sind. Nach der Lösung der 9. Brücke haben der rote und der orange Knoten einen ungeraden Grad. Daher muss ihre Parität geändert werden, indem eine neue Kante zwischen ihnen eingefügt wird.

8., 9. und 10. Brücke

Aktueller Zustand der Brücken

Moderne Karte von Kaliningrad. Die Stellen der verbleibenden Brücken sind grün hervorgehoben, während die zerstörten rot hervorgehoben sind.

Zwei der sieben ursprünglichen Brücken überlebten die Bombardierung von Königsberg im Zweiten Weltkrieg nicht. Zwei weitere wurden später abgerissen und durch eine moderne Autobahn ersetzt. Die drei anderen Brücken sind erhalten geblieben, obwohl nur zwei aus Eulers Zeit stammen (eine wurde 1935 umgebaut). [6] Ab 2000 gibt es also noch fünf Brücken, die mit Eulers Problem zu tun hatten.

In Bezug auf die Graphentheorie haben zwei der Knoten jetzt den Grad 2 und die anderen zwei den Grad 3. Daher ist jetzt ein Eulerscher Pfad möglich, der jedoch auf einer Insel beginnen und auf der anderen enden muss. [7]

Die Universität von Canterbury in Christchurch hat ein Brückenmodell in eine Rasenfläche zwischen der alten Bibliothek der Physikalischen Wissenschaften und dem Erskine-Gebäude eingebaut, in der sich die Abteilungen für Mathematik, Statistik und Informatik befinden. [19659059] Die Flüsse werden durch kurze Büsche ersetzt und die zentrale Insel trägt einen Stein-Tōrō. Das Rochester Institute of Technology hat das Rätsel in den Bürgersteig vor dem Gene Polisseni Center integriert, einer Eishockeyarena, die 2014 eröffnet wurde. [9]

Vergleich der Grafiken der Sieben Brücken von Königsberg (oben) und Fünf-Zimmer-Rätsel (oben) Unterseite). Die Zahlen bezeichnen die Anzahl der Kanten, die mit jedem Knoten verbunden sind. Knoten mit einer ungeraden Anzahl von Kanten sind orange schattiert.

Siehe auch [ Bearbeiten

Bearbeiten [ Bearbeiten

  1. ^ [19659066] Euler, Leonhard (1736). "Problemlösung und Geometrie". Kommentar. Acad. Sci. U. Petrop 8, 128–40.
  2. ^ Shields, Rob (Dezember 2012). "Kulturtopologie: Die sieben Brücken von Königsburg 1736". Theorie, Kultur & Gesellschaft . 29 (4–5): 43–57. doi: 10.1177 / 0263276412451161. Shields diskutiert die gesellschaftliche Bedeutung von Eulers Auseinandersetzung mit diesem populären Problem und dessen Bedeutung als Beispiel für ein (proto-) topologisches Verständnis des Alltags.
  3. ^ The Euler-Archiv, Kommentar zur Veröffentlichung und Originaltext in lateinischer Sprache.
  4. ^ Newman, MEJ Struktur und Funktion komplexer Netzwerke (PDF) . Institut für Physik, University of Michigan.
  5. ^ J. Franklin, Eine aristotelische realistische Philosophie der Mathematik Palgrave Macmillan, Basingstoke, 2014, S. 48–9, 96, 215, 225; J. Franklin, Die Formalwissenschaften entdecken den Stein der Weisen, Studium der Geschichte und Philosophie der Wissenschaften 25 (4) (1994), S. 513–533.
  6. ^ Taylor, Peter (Dezember 2000). "Was ist jemals mit diesen Brücken passiert?" Australischer Mathematik-Trust. Archiviert nach dem Original vom 19. März 2012 . Abgerufen am 11. November 2006 .
  7. ^ Stallmann, Matthias (Juli 2006). "Die 7/5 Brücken von Königsberg / Kaliningrad" . Abgerufen am 11. November 2006 .
  8. ^ "Über – Mathematik und Statistik – Universität von Canterbury". math.canterbury.ac.nz . Abgerufen am 4. November 2010 .
  9. ^ RIT Womens Hockey [@RITWHKY] (19. August 2014). "@ OnlyAtRIT stellen wir das Problem der 7-Brücken-Mathematik in den Zement vor der neuen Hockeyarena @PolisseniCenter #ROC" (Tweet) – via Twitter.

Externe Links bearbeiten ]

Koordinaten: 54 ° 42′12 ″ N 20 ° 30′56 ″ E / 54.70333 ° N 20.51556 ° E / 54.70333; 20.51556


Leave a Reply

Your email address will not be published. Required fields are marked *