Back Hamiltonian path problem English Problema del camino Hamiltoniano Spanish ハミルトン閉路問題 Japanese Problema do caminho hamiltoniano Portuguese Problema drumului hamiltonian Romanian Задача о гамильтоновом пути Russian Проблем Хамилтоновог пута Serbian Hamilton yolu problemi Turkish Задача про гамільтонів шлях Ukrainian 哈密顿路径问题 Chinese
Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Die Frage, ob ein solcher Kreis in einem gegebenen Graphen existiert, ist ein wichtiges Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem ein Kreis gesucht wird, der alle Kanten genau einmal durchläuft, ist das Hamiltonkreisproblem NP-vollständig.
Man unterscheidet das Gerichtete Hamiltonkreisproblem in gerichteten Graphen und das Ungerichtete Hamiltonkreisproblem in ungerichteten Graphen. Eine Verallgemeinerung des Hamiltonkreisproblems ist das Problem des Handlungsreisenden, bei dem nach einem kürzesten Hamiltonkreis in einem Graphen mit Kantengewichten gefragt wird.