| Die letzten 2 Beiträge |
| sdjkfsfsdfsd |
RE: Fehler in Beweis finden: Hamiltonkreis ist NP-vollständig
Der Algorithmus funktioniert nicht bei Inputs, die einen Kreis aber keinen Hamiltonkreis besitzen. |
| blasalat |
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 |
|
|
