von Dr. R. Mildner (Leipzig 2007)
Die Abbildung zeigt ein stilisiert dargestelltes Verkehrsnetz in Deutschland. Mathematisch gesehen ist dieses Verkehrsnetz ein Graph, bestehend aus Knotenpunkten (das sind die Städte) und Kanten (das sind die Verbindungsstraßen zwischen diesen Städten).
a) Versuchen Sie, diesen Verkehrsgraphen - am besten mit einem Farbstift -
in einem Zuge nachzuzeichnen, d. h. ohne den Stift zwischendurch abzusetzen
und so, dass jede Kante nur genau einmal nachgezogen wird, m. a. W., finden
Sie in diesem Graphen einen sog. Euler-Weg! Praktisch gesehen entspräche das
der Aufgabe, mit einem PKW eine Reise zu unternehmen, die in der Stadt X beginnt
und in der Stadt Y endet, und zwar so, dass jede Straße des Verkehrsnetzes
durchfahren wird, aber eben nur genau einmal.
b) Wenn wir noch eine Verbindungsstraße zwischen Leipzig und Magedeburg in unser
Verkehrtsnetz einzeichnen würden, wäre dann die in a) geforderte Aufgabe auch noch
lösbar, d. h. würde dann in diesem Graphen auch noch ein Euler-Weg existieren?