Hamiltonkreisproblem
Sign in to saveAlso known as Hamilton path problem
Berechnungsproblem in der Graphentheorie
Wikidata facts
- Instance of
- computational problem
Show 3 more facts
- facet of
- Hamiltonian path
- Commons category
- Hamiltonian path problem
- computational complexity
- NP-complete
via Wikidata · CC0
Article · Deutsch
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.
Abstract from DBpedia / Wikipedia · CC BY-SA