Hamiltonova pot

Iz Wikipedije, proste enciklopedije

Petersenov graf vsebuje Hamiltonovo pot, nima pa Hamiltonovega cikla
Povečaj
Petersenov graf vsebuje Hamiltonovo pot, nima pa Hamiltonovega cikla

Hamiltonova pot je pot v neusmerjenem grafu, ki gre skozi vsako točko na grafu natanko enkrat. Če sta začetna in končna točka poti enaki, jo imenujemo Hamiltonov cikel. Ime je dobila po irskem matematiku Williamu Rowanu Hamiltonu Za iskanje Hamlitonove poti oz. cikla ne obstaja enostaven algoritem, vendar si lahko pomagamo z naslednjimi izreki:

  1. Če iz grafa odstranimo n točk in graf razpade na strogo več kot n + 1 komponent, potem graf nima hamiltonske poti.
  2. Diracov izrek: Če ima graf G 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 G Hamiltonov cikel.
  3. Orejev izrek: Naj bo G enostaven graf z vsaj 3 točkami. Če za poljubni nesosednji točki a in b je vsota stopenj a in b večja ali enaka številu točk v grafu, potem G vsebuje Hamiltonov cikel.


Ta matematični članek je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.