Denksportliches Wochenende

Auflösung der vierten Aufgabe

DIE METHODE:
Dies ist eine klassische Aufgabe für den Euler-Zyklus. Die Karte zeigt sieben „Knoten“, an denen die Wege zusammentreffen. Vom Parkplatz gehen nur zwei Wege aus, dieser ist also ein geradzahliger Knoten. Die anderen sechs Knoten sind ungeradzahlig. Bei einer solchen Anordnung gibt es keinen Euler-Zyklus.
Michael muss also Kompromisse eingehen, indem er einzelne Abschnitte auslässt oder manche Wege zweimal durchläuft. Nummerieren wir zunächst einmal die Wegabschnitte.
Es sind insgesamt zehn.
Jetzt versehen wir die Knoten mit Buchstaben. In einem Euler-Zyklus muss an jedem Knoten eine gerade Zahl von Abschnitten zusammentreffen. Einen Abschnitt zweimal zu durchlaufen, entspricht einem neuen Weg. Michael möchte kurze Abschnitte weglassen und längere verdoppeln.
Wenn er von A über B nach C läuft, kann er den Weg 2 weglassen und C geradzahlig machen. Dann läuft er von C über D nach E, womit 6 weggelassen wird und D und G geradzahlig werden. Schließlich läuft er von E über F nach G und wieder zurück nach F. Die zweimalige Nutzung des Abschnitts 9 entspricht einem weiteren Weg, womit F und E geradzahlig werden. Dann läuft er von E nach B. Wenn er nun nochmals den Abschnitt 1 durchläuft, werden auch B und A geradzahlig. Damit haben wir einen Euler-Zyklus. Der Weg ist insgesamt übrigens 2,5 km lang.

DIE LÖSUNG:
Durch Weglassen zweier kurzer Abschnitte und zweimalige Nutzung zweier weiterer Abschnitte lässt sich ein Euler-Zyklus erzeugen. Die Route führt dann über die Wegabschnitte 1 → 3 → 4 → 5 → 9 → 7 → 8 → 9 → 10 → 1.

Die Wege des Herrn Komminform

Ohne Wegabschnitte hinzuzunehmen oder wegzulasen, ergibt sich auf diesem Lageplan kein Euler-Zyklus.

Schreiben Sie einen Kommentar

Ihre E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.