Existenz von Eulerwegen und -kreisen
Ragnarök: Das Ende der Welt
In Walhalla tobt Krieg. Die nordischen Götter kämpfen gegen allerlei Ungeheuer, da taucht die große Schlange Jörmungandr auf und verschlingt ganz Walhalla. Danach verschmilzt ihr Körper mit sich selbst – übrig bleibt eine verschlungene Masse ohne Kopf und Schwanz.
Odin lädt Thors Hammer Mjölnir mit der Kraft der Blitze auf. Thor muss über die gesamte Schlange laufen und jeden Teil ihres Körpers spalten. Aber: Kein Teil darf zweimal betreten werden – dort ist die Schlange ja schon gespalten, Thor würde hineinfallen. Er darf aber über einen Spalt springen, also eine Stelle kreuzen. Und lässt er auch nur ein Stück aus, regeneriert sich die Schlange.
Empfohlen: Schau das Video (englisch) bis zur Aufforderung, es anzuhalten („Pause the video now“) – danach wird die Lösung verraten. Löse das Rätsel dann hier selbst.
Das Video liegt bei YouTube. Erst wenn du es lädst, werden Daten an YouTube (Google) übertragen.
Zustimmung zurücknehmen:
Wie viele Knoten der Schlange haben einen ungeraden Grad?
Erkenntnis
Jedes Mal, wenn ein Weg einen Knoten betritt und wieder verlässt, benutzt er zwei Kanten an diesem Knoten. Nur am Start und am Ende ist es anders: Den Startknoten verlässt man, ohne ihn betreten zu haben, den Endknoten betritt man, ohne ihn zu verlassen.
Aufgabe 1: eine Regel finden
Aufgabe 1: Bestimme in jedem Graphen die Grade der Knoten und finde heraus, welche einen Eulerweg bzw. einen Eulerkreis haben. Formuliere eine Regel.
Merke
Ein zusammenhängender Graph, der einen Eulerkreis besitzt, heißt eulersch. Enthält er nur einen Eulerweg und keinen Eulerkreis, heißt er semieulersch.
Die Königsberger Brücken
Leonhard Euler fand 1736 eine Antwort auf die Frage: „Kann man eine Runde durch Königsberg gehen, bei der man jede der sieben Brücken genau einmal überquert?“ Dabei kommt es nicht auf die genaue Lage der Brücken an, sondern nur darauf, welche Brücke welche Stadtteile verbindet.
Aufgabe 3: Abstrahiere die Situation als Graphen: Stadtteile als Knoten (N = Nordufer, S = Südufer, I = Insel, O = Ostteil), Brücken als Kanten. Zwei Brücken zwischen denselben Stadtteilen sind zwei Kanten.
Aufgabe 3: Abstrahiere die Situation als Graphen: Stadtteile als Knoten (N = Nordufer, S = Südufer, I = Insel, O = Ostteil), Brücken als Kanten. Zwei Brücken zwischen denselben Stadtteilen sind zwei Kanten.
Gibt es den gesuchten Rundgang über alle sieben Brücken?