Königsberger Brückenproblem: Arbeitsblatt mit Lösungen

Für die Lehrkraft: Steckbrief

Klassenstufe: 5 bis 10, je nach Aufgabenauswahl
Zeitbedarf: 45 bis 60 Minuten
Lernziele: Ein Sachproblem als Graph modellieren, den Grad eines Knotens bestimmen, die Gradregel für Eulerwege anwenden, die Summe der Grade als doppelte Kantenzahl erkennen, Begründen statt nur Probieren.
Material: dieses Blatt, Bleistift und Radiergummi, für die Haus-Aufgabe nach Wunsch farbige Stifte.
Bezug zur Lernseite: Eulerwege und Eulerkreise, Hintergrund bei Leonhard Euler

Ablaufvorschlag

Einstieg (5 Minuten): Alle probieren auf der Karte einen Spaziergang über jede Brücke genau einmal. Niemand muss Erfolg haben.
Geschichte und Abbildungen (10 Minuten): Text lesen, Karte und Graph vergleichen, den Grad der Knoten klären.
Aufgaben 1 bis 4 (20 Minuten), danach Aufgabe 5.
Aufgabe 6 als Gespräch oder Hausaufgabe. Wer will, erfindet eigene Brückenstädte.

Das Rätsel von Königsberg

Die Stadt Königsberg in Ostpreußen hieß später Kaliningrad und liegt heute in Russland. Mitten durch die Stadt fließt der Pregel. Er teilt sie in vier Landteile: das Nordufer, das Südufer und zwei Inseln, den Kneiphof und die Lomse. Über den Fluss führten zur Zeit Eulers sieben Brücken.

Unter den Menschen in der Stadt ging eine Frage um: Kann man einen Spaziergang machen, bei dem man jede der sieben Brücken genau einmal überquert? Niemand fand einen Weg, aber niemand konnte erklären, warum es nicht geht. Leonhard Euler hörte von dem Rätsel. Er löste es im Jahr 1735 und zeigte, dass es keinen solchen Weg gibt. Die Karte unten ist stark vereinfacht: A ist der Kneiphof, D die Lomse, B das Nordufer und C das Südufer.

Vereinfachte Karte: vier Landteile (A bis D) und sieben Brücken, dick gezeichnet. Die genaue Form des Flusses spielt keine Rolle.

Eulers Idee war: Die Form der Wege und die Größe der Landteile sind egal. Wichtig ist nur, welche Landteile durch Brücken verbunden sind. Er ersetzte jeden Landteil durch einen Punkt und jede Brücke durch eine Linie. So entsteht ein Graph. Die Punkte heißen Knoten, die Linien Kanten. Die Zahl der Kanten, die an einem Knoten enden, heißt sein Grad.

Der Graph zur Karte: Jeder Landteil ist ein Punkt, jede Brücke eine Linie. Die Zahl am Punkt ist sein Grad, die Zahl der Linien, die dort enden.

Auch das Haus vom Nikolaus ist ein Graph. Es hat fünf Ecken und acht Strecken. Die Aufgabe ist bekannt: Zeichne es in einem Zug, ohne den Stift abzusetzen und ohne eine Strecke zweimal zu ziehen.

Das Haus vom Nikolaus mit nummerierten Ecken. Kannst du es zeichnen, ohne den Stift abzusetzen und ohne eine Strecke zweimal zu zeichnen?

Aufgaben

Versuche auf der Karte einen Spaziergang, der alle sieben Brücken genau einmal benutzt. Du darfst an einem beliebigen Landteil starten. Schreibe deine Versuche als Buchstabenfolge auf, zum Beispiel A B D und so weiter. Was passiert jedes Mal?
Bestimme im Graphen den Grad jedes Knotens. Addiere die vier Grade. Vergleiche das Ergebnis mit der Zahl der Brücken. Was fällt dir auf?
Zeichne das Haus vom Nikolaus in einem Zug. Bestimme den Grad der fünf Ecken. Wo musst du beginnen, wo endest du? Schreibe die Reihenfolge der Ecken auf.
Die Regel von Euler lautet: Ein zusammenhängender Graph lässt sich in einem Zug zeichnen, wenn höchstens zwei Knoten einen ungeraden Grad haben. Entscheide für jede Figur, ob es geht, und sage, wo du beginnst: (a) Quadrat mit beiden Diagonalen, (b) Quadrat mit nur einer Diagonale, (c) die zwölf Kanten eines Würfels, (d) ein Fünfeck mit allen fünf Diagonalen.
Heute stehen an den Stellen von Eulers Brücken nur noch fünf Brücken. Spiele einen möglichen Fall durch: Es fehlen eine der beiden Brücken zwischen A und B und eine der beiden Brücken zwischen A und C. Zeichne den neuen Graphen und bestimme die Grade. Ist der Spaziergang jetzt möglich? Wo muss er beginnen und enden? Gib einen Weg an.
Knobelaufgabe: Du darfst in Eulers Königsberg neue Brücken bauen. Wie viele brauchst du mindestens, damit der Spaziergang möglich wird? Und wie viele, wenn du am Ende wieder am Start ankommen willst? Gib jeweils an, wo du die Brücken baust.

Lösungen

Erwartungshorizont: Jeder Versuch scheitert. Entweder bleibt eine Brücke übrig, oder man müsste eine Brücke zweimal benutzen. Das ist kein Zufall: Es gibt in Königsberg wirklich keinen solchen Spaziergang. Der Grund steht in den Aufgaben 2 und 4.
A hat Grad 5, B hat Grad 3, C hat Grad 3, D hat Grad 3. Die Summe ist 5 + 3 + 3 + 3 = 14. Das ist doppelt so viel wie die Zahl der Brücken, 2 · 7 = 14. Jede Brücke hat zwei Enden und wird bei beiden Landteilen mitgezählt. Alle vier Grade sind ungerade.
Die Grade: Ecke 1 (unten links) hat Grad 3, Ecke 2 (unten rechts) hat Grad 3, Ecke 3 (oben rechts) hat Grad 4, Ecke 4 (oben links) hat Grad 4, Ecke 5 (die Dachspitze) hat Grad 2. Nur die Ecken 1 und 2 haben ungeraden Grad. Man beginnt in einer der beiden unteren Ecken und endet in der anderen. Ein möglicher Weg: 1, 2, 3, 4, 1, 3, 5, 4, 2. Das sind acht Strecken, jede kommt genau einmal vor. Insgesamt gibt es 88 solcher Wege, 44 von jeder der beiden unteren Ecken aus.
(a) Nein: Jede der vier Ecken hat Grad 3 (zwei Seiten und eine Diagonale). Vier ungerade Knoten sind zu viele. (b) Ja: Nur die beiden Ecken, an denen die Diagonale endet, haben Grad 3. Man beginnt in einer dieser Ecken und endet in der anderen. (c) Nein: Alle acht Ecken haben Grad 3. (d) Ja: Jede Ecke hat Grad 4 (zwei Seiten und zwei Diagonalen), auch jeder Schnittpunkt der Diagonalen im Inneren hat Grad 4 und ändert nichts. Alle Grade sind gerade, deshalb gibt es sogar einen geschlossenen Weg, der am Startpunkt endet. Man kann überall beginnen.
Der neue Graph hat die fünf Kanten A-B, A-C, A-D, B-D und C-D. Die Grade sind A: 3, B: 2, C: 2, D: 3, die Summe ist 10 und damit doppelt so groß wie die Zahl der Brücken. Nur A und D haben ungeraden Grad, das sind die beiden Inseln. Der Spaziergang ist also möglich und muss auf der einen Insel beginnen und auf der anderen enden. Ein Weg: A, B, D, C, A, D. Er benutzt die fünf Brücken A-B, B-D, D-C, C-A und A-D. Das passt zu den bekannten Angaben für das heutige Kaliningrad: Zwei Landteile haben dort den Grad 2, zwei den Grad 3, und ein solcher Spaziergang geht von einer Insel zur anderen.
Eine Brücke reicht für einen Weg, zum Beispiel zwischen B und C. Dann haben B und C den Grad 4, und nur A (Grad 5) und D (Grad 3) sind ungerade. Der Weg beginnt in A und endet in D (oder umgekehrt). Für einen Rundweg müssen alle Grade gerade sein. Dafür braucht man mindestens zwei neue Brücken, zum Beispiel eine zusätzliche zwischen A und B und eine zusätzliche zwischen C und D. Dann gilt A: 6, B: 4, C: 4, D: 4. Eine einzelne Brücke genügt nicht, denn sie ändert den Grad von nur zwei Knoten, und es sind vier ungerade Knoten.

Hinweise für die Lehrkraft

Typische Schwierigkeiten: Der Grad wird als Zahl der Nachbarn gezählt, nicht als Zahl der Brücken (zwischen A und B liegen zwei Brücken). Bei Zeichnungen mit Schnittpunkten (Diagonalen) bleibt unklar, ob der Schnittpunkt ein Knoten ist. Man darf ihn mitzählen, sein Grad ist 4 und ändert nichts. „Es geht nicht“ wird mit „ich habe keinen Weg gefunden“ verwechselt. Tipp: Das Argument mit „hinein und wieder hinaus“ laut besprechen.
Leichter: Aufgaben 1 bis 3. Die Grade im Graphen vorgeben, das Haus vom Nikolaus mit nummerierten Ecken vorgeben.
Schwerer: Das Argument selbst formulieren: Ein Knoten, der nicht Start oder Ziel ist, wird beim Durchgang über zwei Kanten betreten und verlassen, also muss sein Grad gerade sein. Das Handschlaglemma (die Summe der Grade ist 2 mal die Zahl der Kanten) nutzen und daraus folgern, dass die Zahl der Knoten mit ungeradem Grad immer gerade ist. Außerdem muss der Graph zusammenhängen.
Quellenlage: Euler legte seine Lösung am 26. August 1735 der Petersburger Akademie vor. Die Abhandlung wird auf das Jahr 1736 datiert und erschien 1741 im Druck. Euler sprach noch nicht von Graphen, er sprach von der „Geometrie der Lage“. Heute stehen an den Stellen der Brücken noch fünf Brücken: Zwei der ursprünglichen sieben wurden im Zweiten Weltkrieg zerstört, zwei weitere später abgerissen und durch eine Schnellstraße ersetzt. Von den drei erhaltenen Brücken stammen nur zwei aus Eulers Zeit. Welche Brücken fehlen, lässt das Blatt offen, deshalb spielt Aufgabe 5 einen möglichen Fall durch.
Weiterführung: Hamiltonkreise (jeden Knoten genau einmal besuchen) bei der Graphentheorie, das Handschlaglemma hier, der Vierfarbensatz als weiteres Graphenproblem: Vierfarbensatz. Mehr Rätsel bei den Knobelrätseln.

Arbeitsblatt von geschichtedermathematik.de/geschichte-koenigsberger-bruecken/ · kostenlos für Unterricht und Lernen

Für die Lehrkraft: Steckbrief

Ablaufvorschlag

Das Rätsel von Königsberg

Aufgaben

Lösungen

Hinweise für die Lehrkraft

Weiterlesen

Graphentheorie

Leonhard Euler

Kombinatorik

Wichtige Mathematiker