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