Einführung: Graphen

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?

Lösungen

Um derartige Fragestellungen in informatischen System modellieren zu können, müssen wir uns nun ein paar Gedanken machen.

Welche der folgenden Informationen wichtig für die Suche nach Rundtouren sind:

• Name der Inseln
• Größe der Inseln
• Entfernung zwischen den Häfen
• Welche Inseln sind mit Fährrouten verbunden?
• genauer Verlauf der Fahrtroute