Geschrieben von blasalat am 26.06.2013 um 10:04:
Fehler in Beweis finden: Hamiltonkreis ist NP-vollständig
Meine Frage:
Hallo ich komme bei folgender Aufgabe nicht so ganz weiter:
In einer anderen Aufgabe mussten wir einen Algorithmus angeben um einen Kreis in einem gerichteten Graphen in linearer Zeit zu finden, dieser sei für diese Aufgabe gegeben.
Theorem: Hamiltonkreis kann deterministisch in polynomieller Zeit gelöst werden
Beweis: Unser Kreis-Algorithmus löst das Problem für jede beliebige Instanz in polynomieller Zeit, also auch für alle Instanzen G, in der keine Kreise der Länge < |V|
existieren. In einer solchen Instanz G kann also, wenn ein Kreis existiert, dieser Kreis nur alle Knoten besuchen. Wenden wir nun unseren Kreis-Algorithmus auf G an, lösen
wir das HamiltonKreis-Problem.
Meine Ideen:
Leider habe ich keinen Schimmer was daran nicht stimmen kann
Würde mich über Tipps sehr freuen