Eine Sightseeing-Tour planen
Die folgende Aufgabe wurde von Djamil, Ferdinand und Tayyib aus der achten Klasse eines Berliner Gymnasiums erstellt.
Das Ziel ist, eine optimale Rundfahrt zu den Sehenswürdigkeiten einer Stadt zu planen.
Das Ziel ist, eine optimale Rundfahrt zu den Sehenswürdigkeiten einer Stadt zu planen.
- Findest du eine Rundfahrt, die jeden Knoten des Graphen genau einmal besucht und keine Kanten doppelt verwendet? (Der "Rundfahrt zeigen"-Knopf zeigt dir eine Rundtour an!)
- Findest du noch weitere solche Rundfahrten? Falls ja, welches ist die beste?
- Findest du bessere Touren, wenn du auch das Doppeltfahren einer Straße erlaubst?
- Der "Baum-Lösung zeigen"-Knopf zeigt einen minimalen aufspannenden Baum auf diesem Graphen an.
- Ist dies eine Lösung für die Fragestellung?
- Wie kann man daraus eine Rundfahrt bauen?
- Wie hängt die so erzeugte Tour mit einer optimalen Rundfahrt zusammen?
- Kannst du eine allgemeingültige Aussage herleiten und beweisen?