Hallo,
ich habe eine Frage in Sachen Graphentheorie:
Kann es einen Hamiltonweg auch mit nur zwei Knoten geben? Alle Definitionen für Hamiltonkreise und -wege beziehen sich auf Graphen mit min. drei Knoten. Allerdings ist ein Graph mit zwei verbundenen Knoten mMn. ja auch schon ein Hamiltonweg.
Ist die Definition eines Hamiltonweges wirklich erst ab drei Knoten gültig?
Hallo
Also vorneweg, ich bin kein Mathematiker.
Wiki sagt:
http://de.wikipedia.org/wiki/Glossar_Graphentheorie#Weg
„Weg:
Die Definition eines Weges variiert in der Fachliteratur (…) Äquivalent dazu kann man den Weg auch als die entsprechende Folge von Kanten definieren. Die Varianten der Definition eines Weges ergeben sich nun daraus, ob man zulässt, dass ein Weg mehrmals über einen Knoten verlaufen darf oder gar mehrmals über eine Kante verlaufen darf: Bei Reinhard Diestel bspw. ist dies ausgeschlossen und er fordert in seinem Lehrbuch Graphentheorie von einem Weg zusätzlich, dass die (Kanten) alle paarweise verschieden seien. Angelika Steger wiederum stellt in ihrem Buch Diskrete Strukturen diese Bedingung explizit nicht: Was Diestel als einen Weg definiert, entspricht bei Steger einem Pfad.“
Also anscheinend kommt es auf die jeweils verwendete Definition von „Weg“ an, ob {A->B, B->A} ein Weg ist oder nicht.
In deinem Fall (zwei Knoten) würde wohl Herr Diestel mit „Nein“ antworten, Frau Steger jedoch mit „Ja“
Und ausweichend an dieser Stelle
http://de.wikipedia.org/wiki/Wege,_Pfade,_Zyklen_und…
„Pfade, Zyklen und Kreise
(…) Ein Zyklus oder Kreis heißt trivial, wenn er weniger als drei Knoten enthält. Triviale Kreise oder Zyklen werden meist nicht betrachtet (…)“
Nunja