i

Das Problem

Rundreise durch die Hauptstädte der Europäischen Union

Wenn ein neuer Außenminister im Amt ist, dann versucht er (oder sie), möglichst rasch Antrittsbesuche bei den wichtigsten Bündnispartnern zu machen. Zu diesen Partner gehören natürlich auch die Länder der Europäischen Union (EU).

Wir werden hier folgende Situation durchspielen: Nach einer Bundestagswahl soll der neue Außenminister alle Hauptstädte der EU besuchen. Die Reihenfolge soll sich nicht nach der Bedeutung der Länder oder anderen Kriterien richten. Sie soll so gewählt werden, dass der gesamte Reiseweg für den Minister möglichst gering wird.

Bei der Bestimmung der kürzesten Rundreise durch die Hauptstädte der EU ist zu berücksichtigen, dass die EU einmal sehr klein - mit nur wenigen Bündnispartner - begonnen hat und dass im Laufe der Zeit immer mehr Mitgliedsstaaten hinzu gekommen sind. Die folgende Animation zeigt die Entwicklung der EU.

Staaten der EU zu mehreren Zeitpunkten[1]

Aufgabe 1

Als Willy Brandt 1966 Außenminister wurde, bestand die EU (damals EWG) aus nur 6 Ländern: Deutschland, Frankreich, Italien, Niederlande, Belgien und Luxemburg. Die Tabelle zeigt die Entfernungen der jeweiligen Hauptstädte.

Bonn Paris Rom Den Haag Brüssel Luxemburg
Bonn 0 401 1066 244 195 145
Paris 401 0 1108 383 262 287
Rom 1066 1108 0 1289 1174 989
Den Haag 245 383 1289 0 137 302
Brüssel 195 262 1174 137 0 187
Luxemburg 145 287 989 302 187 0

Versuche, eine möglichst kurze Rundreise mit Start- und Zielort Bonn zu finden. Bestimme auch die Gesamtlänge der Rundreise.

Das Rundreiseproblem und seine Relevanz

Das Rundreiseproblem besteht darin, in einem gegebenen Graphen einen Kreis derart zu bestimmen, dass alle Knoten im Kreis vorkommen und die Länge des Kreises möglichst klein ist.

Weitere interessante Informationen und Anwendungen zum Rundreiseproblem findest du auf den Webseiten Traveling Salesman Problem.

Quellen

Suche

v
4.3.4.1
www.inf-schule.de/algorithmen/graphen/rundreiseningraphen/station_problem
www.inf-schule.de/4.3.4.1

Rückmeldung geben