Ein Hamiltonscher Weg ist ein geschlossener Kantenzug, in dem jeder Knoten (=jede Ecke) genau einmal vorkommt. |
Die geringe Abweichung von der Forderung beim Eulerschen Weg führt hier zu einer ganz anderen Problemklasse. Insbesondere zeigt sich, dass wir es in diesem Fall mit einem echten Suchproblem, sogar mit einem sehr schweren Suchproblem zu tun haben.
Bei den Hamiltonschen Wegen geht es wie bei den Eulerschen Wegen zunächst allein um die Frage: Gibt es einen Weg ? Es geht also um ein Entscheidungsproblem, das mit den Antworten ja und nein versehen werden kann. In vielen Anwendungsfällen -vergessen Sie nicht, dass die Graphen in den meisten Fällen nur Modellierungen real ganz anders aussehender Probleme darstellen- gehen die Ansprüche aber über die Frage der Existanz einer Lösung hinaus.
In vielen Fällen wird man sehr viele mögliche Lösungen haben und für diese vielen möglichen Lösungen nun zusätzlich fragen: Welche der vielen möglichen Lösungen ist die beste ?
Zur grundsätzlichen Entscheidung dieser Frage sind natürlich Bewertungen der Lösungen nötig. Beim Ariadne - Problem läßt sich ein Kriterium sehr einfach in der Länge des Weges finden, jeder wird sicher erhebliches Interesse haben, das Labyrinth auf kürzestem Wege zu verlassen. Zunächst einmal ließe sich dies aus der Zahl der Kanten errechnen. Das ist aber nur dann sinnvoll, wenn die Kanten in diesem Fall -zumindest fast- gleiche Kantenlänge aufweisen. Ist das nicht der Fall, muss man deren unterschiedliche Länge kennen und mit berücksichtigen.
Damit beschreiben wir das Problem aber mit einem anderen Typ von Graphen: Wir haben von einem unbewerteten Graphen zu einem bewerteten Graphen gewechselt.
Anmerkung: W.R. Hamilton, irischer Mathematiker (1805 - 1865)