Hamiltonkreis

Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Ob ein solcher Kreis in einem gegebenen Graph besteht, ist ein fundamentales Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem alle Kanten genau einmal durchlaufen werden, ist das Hamiltonkreisproblem NP-vollständig.