Metraipolis › archive › dc_590b4bccde80

Hamiltonkreisproblem — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Hamiltonkreisproblem
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T18:11:35.217Z
SHA-256 of the archived text
20fb2d58d65e7a07574c9c01fb5004a2719e717c0f2c223cd54de04435c726af
Stable URL of this page
https://metraipolis.com/documento/dc_590b4bccde80

How to cite

Hamiltonkreisproblem — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Hamiltonkreisproblem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_590b4bccde80 (Metraipolis archive dc_590b4bccde80, sha256 20fb2d58d65e7a07574c9c01fb5004a2719e717c0f2c223cd54de04435c726af)
BibTeX
@misc{dc590b4bccde80,
  title = {Hamiltonkreisproblem — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Hamiltonkreisproblem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_590b4bccde80; sha256 20fb2d58d65e7a07574c9c01fb5004a2719e717c0f2c223cd54de04435c726af},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Hamiltonkreisproblem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «Graphentheorie»).
Fonte: Wikipedia in tedesco, voce «Hamiltonkreisproblem» — https://de.wikipedia.org/wiki/Hamiltonkreisproblem
Wikidata Q987652 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q987652
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Hamiltonkreisproblem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 252976545, consultata il 2026-10-07T17:43:59.093Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: eba4f30b5b178b3febf31769088845409360752c0d953a393bd1561fd355ad01