Hamiltonkreis |
| 12.02.2009, 18:04 | N24 | Auf diesen Beitrag antworten » |
| Hamiltonkreis 1. Hamiltonkreisproblem ist ein fundamentales, NP-vollständiges Problem (also ob ein gegebener Graph einen Hamiltonkreis enthält) 2. Jeder Graph mit mindestens Minimalgrad hat einen Hamiltonkreis. Die 2te Bedingung kann ich in polynomieller Zeit für jden Graphen nachprüfen dasbedeutet doch aber, dass das Hamiltonkreisproblem nich NP-vollständig ist. Könnte mir das jemand erklären? Schonmal vielen dank im vorraus |
||
| 12.02.2009, 20:04 | kiste | Auf diesen Beitrag antworten » |
Nur weil für eine spezielle Klasse von Graphen das Problem lösbar ist, heißt das nicht dass es allgemein schnell lösbar ist. Formeln in DNF lassen sich auch in Linearzeit auf erfüllbarkeit testen, trotzdem ist SAT NP-Vollständig. |
||
| 12.02.2009, 22:58 | N24 | Auf diesen Beitrag antworten » |
Ich kann das aber für jeden Graphen prüfen |
||
| 12.02.2009, 23:02 | kiste | Auf diesen Beitrag antworten » |
Du kannst auch für jede Formel überprüfen ob sie in DNF vorliegt... Dein Verfahren funktioniert eben nur für eine spezielle Klasse von Graphen für die HK existieren. Nicht alle Graphen mit HK haben diese Eigenschaft! |
||
| 12.02.2009, 23:18 | N24 | Auf diesen Beitrag antworten » |
ok danke |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
