Das Hamiltonproblem
Das Hamiltonproblem
Multiple Choice
Aufgabe 1: Gibt es in diesem Graphen einen Hamiltonweg? Gibt es einen Hamiltonkreis?
Freitext
Aufgabe 1: Woran kann man am Graphen erkennen, dass es keinen Hamiltonkreis geben kann?
💡 Zum Speichern deiner Antwort bitte einloggen.
Merke
Das Hamiltonwegproblem bzw. Hamiltonkreisproblem fragt, ob ein gegebener Graph einen Hamiltonweg bzw. -kreis enthält. Für beide ist kein effizienter Algorithmus bekannt. Gibt man aber einen Graphen und eine Knotenfolge vor, lässt sich leicht prüfen, ob sie eine Lösung ist.
Lückentext
Gibt man einen Graphen G und eine beliebige Knotenfolge vor, lässt sich leicht prüfen, ob diese Knotenfolge einen
oder einen
darstellt. Damit liegen beide Probleme in der Problemklasse
.
Graph zeichnen
Aufgabe 2: Dieser Graph hat keinen Hamiltonkreis. Ergänze genau eine Kante, sodass einer entsteht.
Aufgabe 2: Dieser Graph hat keinen Hamiltonkreis. Ergänze genau eine Kante, sodass einer entsteht.