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.