Zwei Inseln, zwei Ufer, sieben Brücken. Die Brücken nach Ufern gezählt ergeben 3, 3, 3 und 5, und die Grade summieren sich zu 3 + 3 + 3 + 5 = 14 (erster Link; der dritte Link erhält dieselben 14 als 3 × 3 + 5, die schnellere Gruppierung). Die Hälfte dieser Summe ist die Zahl der Brücken – der zweite Link dividiert zu 7 –, und die Beziehung ist nicht speziell für diese Karte: Jede Brücke trägt zu zwei Ufern bei, die Grade müssen also doppelt so groß sein wie die Zahl der Kanten. Der vierte Link, 4 × 3/2 = 6, ist die Zahl der Landmassen-Paare, die durch eine Brücke verbunden werden können, und es gibt sieben Brücken für sechs Paare, mindestens ein Landmassen-Paar wird also von zwei Brücken statt einer verbunden.
Eulers Argument ist, dass ein Spaziergang, der jede Brücke einmal überquert, jede Landmasse, die er passiert, paarweise betreten und verlassen muss, jeder als Halt benutzte Knoten hat also geraden Grad; nur der erste und der letzte Knoten des Spaziergangs sind ausgenommen, und es gibt nur zwei davon. Königsberg hat vier ungerade Knoten, es existiert also kein Spaziergang der verlangten Art, und der Beweis ist vollständig, bevor jemand einen Fluss vermisst. Das ist der Grund, warum die Arbeit als erster Satz der Graphentheorie behandelt wird und nicht als Lösung eines Rätsels: Die Entfernungen, die Formen der Ufer und die Breiten des Pregel sind alle belanglos, und Euler sagt das, indem er das Problem in eine Geometrie der Lage statt einer Geometrie der Größe stellt. Zwei der sieben Brücken wurden 1944 zerstört und nie wieder aufgebaut, heute ist die Frage also eine touristische; die Arithmetik hier betrifft die Karte, die Euler 1735 zugeschickt wurde.
Antwort
14
So lesen Sie sie
Die Summe der vier Grade. Der zweite Link halbiert sie zu den sieben Brücken, der dritte addiert sie anders, der vierte zählt die Landmassen-Paare.
Quelle
Leonhard Euler, 'Solutio problematis ad geometriam situs pertinentis', 1736, the founding paper of graph theory; the Königsberg bridges on the Pregel were seven in Euler's map, two of which were destroyed in 1944 and not rebuilt
Im Rechner durchrechnen
Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.