Hamilton Kreise Übung

Aus ProgrammingWiki
Archivierte Version vom 2015-12-08T14:51:29+00:00. Aktuelle Version

Übung Teil 1: Hamilton Graphen und Travelling Salesman Problem

Wir haben folgenden Graphen:
Jowolf_LandkreisGörlitzGraph.png


Aufgaben:

  1. Stellen sie einen 2. Graphen auf, der die Fahrzeit beinhaltet. Die Durschnittsgeschwindigkeit beträgt 70 km/h. (Mögliches Mittel: GeoGebra)
  2. Erstellen Sie einen Hamiltonweg und einen Hamiltonkreis für den Graphen mit der Fahrzeit und der Strecke. Ihr Startpunkt wird Ihnen zugeteilt. Geben Sie zum Vergleich die Länge bzw. die Gesamtfahrzeit des Kreises bzw. Graphen an.
  3. Markieren Sie eine Dreiecksungleichung.

Zusatzaufgabe:
Entwickeln sie einen Pseudocode für die erschöpfende Suche.