Fehler in Beweis finden: Hamiltonkreis ist NP-vollständig |
| 26.06.2013, 10:04 | Auf diesen Beitrag antworten » |
| 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 |
|
|
|
| 30.07.2013, 06:48 | Auf diesen Beitrag antworten » |
| sdjkfsfsdfsd | RE: Fehler in Beweis finden: Hamiltonkreis ist NP-vollständig Der Algorithmus funktioniert nicht bei Inputs, die einen Kreis aber keinen Hamiltonkreis besitzen. |
|
|
