Dies ist eine alte Version des Dokuments!
Einführung: Graphen
Schiffsverbindungen
(A1)
Die Regionalregierung eines Archipels hat eine Fähre angeschafft, die die vier Inseln des Archipels verbinden soll. Dabei sollen die abgebildeten Fährrouten bedient werden. Idealerweise sollte das Schiff immer wieder eine Rundtour fahren, bei der jede Fährverbindung einmal bedient wird.
- Entscheide, ob es eine derartige Rundtour gibt. Gib die Rundtour gegebenenfalls an.
- Entscheide, ob es möglich ist, eine einzige Strecke zu fahren, bei der jede Route genau einmal bedient wird. Gib an, von welchen Häfen aus dies möglich ist.
- (**) Kannst du angeben, unter welchen Voraussetzungen es eine Rundtour (Starthafen = Zielhafen) gibt, die alle Routen genau einmal abfährt?