Ein Elementarkreis in einem Graphen, der alle Knoten des Graphen genau einmal durchläuft, heißt Hamiltonkreis. Ist ein Graph mit Knoten und Kanten gegeben, so kann nach einem solchen Hamiltonkreis gesucht werden.
Mitunter kann man auf einem Graphen keinen geschlossenen Hamiltonkreis finden: Es gelingt nicht, zum Anfangsknoten zurückzukehren. Ist es trotzdem möglich, jeden Knoten genau einmal zu erreichen, ohne den Weg zu schließen, so spricht man von einem Hamilton-Pfad.
Auch auf den Kanten von Polyedern kann es Hamiltonkreise und -Pfade, d.h. Hamilton-Wege, geben. In der Abbildung ist zum Beispiel ein geschlossener Hamilton-Weg auf einem Dodekader zu sehen.
In diesem Teilprogramm können verschiedene Polyeder dargestellt werden. Anschließend können Hamilton-Wege gesucht werden.
Ermittlung des Hamiltonkreises oder -pfades
Nach Auswahl des Polyeders in der Liste und der Darstellung über den entsprechenden Schalter können Sie nach Hamiltonkreisen oder -wegen suchen lassen. Klicken Sie dazu auf den Schalter Hamilton-Wege.
Das Programm beginnt sofort mit der Suche. Dabei wird stets ab dem ersten Eckpunkt des Polyeders gesucht. Neben dem Schalter werden die gefundenen Ergebnisse in einer Liste angezeigt, und zwar in der Reihenfolge der besuchten Eckpunkte.
Wird kein geschlossener Hamiltonkreis ermittelt, so können Sie auch nur nach Hamiltonwege suchen lassen, indem Sie das Feld markieren.
Bei größeren Polyedern mit relativ vielen Kanten kann die Suche sehr viel Zeit in Anspruch nehmen. Abbrechen können Sie jederzeit über den Schalter Abbruch.
Das Programm stoppt automatisch, wenn 100000 Kreise bzw. Pfade gefunden wurden. Während der Suche zeigt das Programm die Anzahl der schon gefundenen Kreise und Pfade an.
Anzeige eines Hamiltonkreises bzw. -pfades
Wurden Ergebnisse gefunden, so können Sie diese nach beendeter Suche veranschaulichen. Markieren Sie dazu einen Eintrag in der Liste. Im rechten Fensterteil wird der Hamilton-Weg dargestellt.
Wie bei anderen Polyederdarstellungen können die Polyeder mithilfe der Standardschalter vergrößert oder verkleinert dargestellt bzw. gedreht werden (linke Maustaste oder Schalter Rotation).
Markieren Sie Punkte beschriften, so zeigt das Programm die Nummer des im Hamilton-Pfad genannten Punktes auch in der rechten Darstellung an.
| Hamilton-Wege auf Polyedern |
|---|
|
| Herunterladen |
Download
Dieser Programmteil steht als einzelnes Programm zum Download bereit.