Hamiltonova pot je v teoriji grafov pot v neusmerjenem grafu, ki gre skozi vsako točko na grafu točno enkrat. Če sta začetna in končna točka poti enaki, se imenuje Hamiltonov cikel. Ime je dobila po irskem matematiku Williamu Rowanu Hamiltonu. Graf, ki vsebuje Hamiltonov cikel, se imenuje Hamiltonov graf.
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Petersen_graph.svg/640px-Petersen_graph.svg.png)
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Ljubljana_graph_hamiltonian.svg/640px-Ljubljana_graph_hamiltonian.svg.png)
Za iskanje Hamlitonove poti oziroma cikla ne obstaja enostaven algoritem, vendar se lahko pomaga z naslednjimi izreki:
- Če se iz grafa odstrani točk in graf razpade na strogo več kot komponent, potem graf nima hamiltonske poti.
- Diracov izrek: Če ima graf vsaj 3 točke in velja, da je stopnja točke z najmanjšo stopnjo večja ali enaka polovici števila točk v grafu, potem ima Hamiltonov cikel.
- Orejev izrek: Naj bo enostavni graf z vsaj 3-mi točkami. Če je za poljubni nesosednji točki in vsota stopenj in večja ali enaka številu točk v grafu, potem vsebuje Hamiltonov cikel.
Število Hamiltonovih poti na n-hiperkocki je (OEIS A006070):
- 0, 0, 48, 48384, 129480729600, ...
Glej tudi
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.