Eulerwege und Eulerkreise – das Königsberger Brückenproblem

Was sie zeigt

1736 fragte sich Leonhard Euler, ob ein Spaziergang durch Königsberg jede der sieben Brücken genau einmal überqueren kann. Indem er Landstücke durch Ecken und Brücken durch Kanten ersetzte, zeigte er, dass die Antwort nur von den Graden abhängt. Ein zusammenhängender Graph besitzt einen Eulerkreis, wenn alle Ecken geraden Grad haben, und einen Eulerweg, wenn genau zwei Ecken ungeraden Grad haben; der Weg beginnt dann an der einen und endet an der anderen. Die Simulation erlaubt mehrere Kanten zwischen denselben zwei Ecken, aber keine Schlingen, und die Karte von Königsberg ist vereinfacht.

So funktioniert es

Beginnen Sie mit Königsberger Brücken und lesen Sie Grade und Ergebnis ab. Stellen Sie den Modus auf Selbst gehen und tippen Sie Kanten an, um jede Brücke einmal zu überqueren. Fügen Sie im Modus Zeichnen / verschieben Ecken hinzu oder verbinden Sie sie, bis sich das Ergebnis ändert; wählen Sie dann Fleury (Brücken meiden) oder Hierholzer (Kreise einfügen) und drücken Sie Schritt oder Starten, um den Aufbau der Route zu verfolgen.

Einstellbare Parameter

• Anfangsgraph Königsberger Brücken, Haus vom Nikolaus (in einem Zug), Zwei Dreiecke mit gemeinsamer Ecke, Vollständiger Graph mit 5 Ecken (K5), Leere Seite – selbst zeichnen
• Algorithmus Fleury (Brücken meiden), Hierholzer (Kreise einfügen)
• Animationstempo 0,5–4 Kanten/s

Fragen zum Erkunden

1. Warum kann man die sieben Brücken von Königsberg nicht jeweils genau einmal überqueren?
2. Wie viele Brücken müssen Sie mindestens hinzufügen, damit es einen Eulerweg gibt, und wo?
3. Warum muss ein Eulerweg an einer ungeraden Ecke beginnen und an der anderen enden?