Hamiltonkreise
Bei Eulerschen Kantenzügen werden alle Kanten eines Netzes1 genau einmal durchlaufen.
Die naheliegende Problemstellung, alle Knoten eines Graphen genau einmal zu durchlaufen, um am Ende wieder am Ausgangspunkt zu landen, geht auf den irischen Mathematiker William Rowan Hamilton (1805-1865) zurück.
Hamilton-Kreis
Ein geschlossener Kantenzug, der jeden Knoten eines Graphen genau einmal enthält, heißt Hamiltonscher Kantenzug oder Hamilton-Kreis.
-
Hamilton-Kreise gesucht! Zeichne sie farbig ein, falls sie vorhanden sind. Ergänze andernfalls eine Kante, so dass ein Hamiltonkreis entsteht und markiere ihn.
-
„Bewertete“ Graphen – Günstige Rundreise gesucht!
(Ein bewerteter Graph enthält wie hier Zusatzinformationen, z.B. die Länge einer Strecke, die nötige Fahrzeit, den Fahrpreis, o.ä.). Eva möchte mit ihren Eltern eine möglichst günstige Bahn-rundreise durch die Städte A, B,C und D machen, aber jede Stadt nur einmal besuchen. Für die Fahrt von einer Stadt zur anderen wird jeweils ein bestimmter Preis verlangt. An den bewerteten Kanten stehen hier die Fahrtkosten (in €). Bestimmt die günstigste Route.
-
„TSP - Travelling Salesman Problem“ (Problem eines Handlungsreisenden)
Deutschlandkarte [CC0] https://commons.wikimedia.org/wiki/File:Karte_Deutschland.png , bearbeitet (abgerufen: 3.4.2018)
Ein Geschätsmann aus Frankfurt muss Kunden in Berlin, Nürnberg und München beraten. Er möchte seine Rundreise so planen, dass er jeden Ort nur genau einmal besucht und die Gesamtfahrstrecke dabei möglichst klein bleibt. Dazu hat er die Entfernungen (in km) in einer Tabelle aufgeschrieben:
Zeichnet einen bewerteten Graphen und ermittelt die kürzeste Reiseroute.
-
Findet ihr die Hamiltonkreise? Zeichnet Sie ein.
1 Ein zusammenhängender Graph wird auch als Netz bezeichnet.
Hamiltonkreise: Herunterladen [odt][168 KB]
Hamiltonkreise: Herunterladen [pdf][137 KB]
Weiter zu Übungen