Hamiltonovská kružnice

Z Wikipedie, otevřené encyklopedie

Hamiltonovská kružnice
Hamiltonovská kružnice

Hamiltonovská kružnice grafu je taková cesta, která projde právě jednou všechny uzly grafu a mezi jejíž výchozím a konečným uzlem existuje platná cesta.

Každý graf nemusí mít nutně Hamiltonovskou kružnici. Nutnými (avšak nikoli postačujícími) podmínkami je, že graf musí být souvislý a každý uzel musí mít stupeň nejméně rovný dvěma (ke každému uzlu musí vést alespoň 2 hrany).

Problém nalezení Hamiltonovské kružnice je NP-úplný.