• Definicija. Naj bo G nek graf na vsaj 3-eh točkah. Če se lahko po grafu sprehodimo tako, da začnemo v neki točki, obiščemo vse ostale točke natanko enkrat, pravimo, da ima graf hamiltonovo pot. Če lahko to pot zaključimo, torej končamo v tisti točki, kjer smo začeli, pravimo, da ima graf G hamiltonov cikel. Ime je dobil po irskem matematiku Williamu Rowanu Hamiltonu. Nek graf je hamiltonov, če ima hamiltonov cikel.

• Spomnimo se - kaj sploh je cikel?

  • Cikel je povezan graf na n točkah, pri katerem so vsa vozlišča stopnje 2.

• Poznamo dva pomembna izreka:
• 1. 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 graf hamiltonov cikel (ni pa rečeno, da je vedno tudi obratno res!)

• 2.Orejev izrek. Naj bo G enostaven graf z vsaj 3-emi točkami. Če je za poljubni nesosednji točki vsota stopenj večja ali enaka vsoti vseh točk v grafu, potem je graf G hamiltonov (ni pa rečeno, da je vedno tudi obratno res!)

• 3. In eno trditev. Če iz grafa odstranimo k vozlišč in graf, ki ostane razpade na več kot k delov, potem ta graf nima hamiltonovega cikla.

• Poglejmo si primer. Dan je graf:

  

Ali na tem grafu obstaja hamiltonov cikel? Pa poskusimo ... Če začnemo npr. v točki F in tvorimo pot F-A-B-C-D-I-H-G-E-F, dobimo hamiltonov cikel tj. obiskali smo vsa vozlišča natanko enkrat in prišli smo v začetno točko. Torej obstaja hamiltonov cikel v danem grafu:

Lahko začnemo tudi v kakšni drugi točki, npr. v H-I-D-C-B-A-F-E-G-H. In spet smo dobili cikel (ki je enak):

• Ugotovili smo, da je dani graf hamiltonov. Pa pokažimo to še s trditvijo na 1. prosojnici. Grafu odstranimo dve točki. Naj bosta to tč.B in tč.E. Dobimo naslednji graf:

  

  Opazimo, da je graf "razpadel" na en del. Torej nam to pove, da je hamiltonov.

Poglejmo si še primer, ko graf ni hamiltonov. Najbolj znan primer je Petersonov graf na desetih točkah:

Lahko poskusimo z iskanjem cikla ... Začnemo v poljubni točki, npr. v A: Tvorimo pot A-B-C-D-E-G-J-H-F-I:

Ali pa recimo F-I-G-J-H-A-E-D-C-B:

in še mnogo takih POTI obstaja. Vidimo pa, da Petersonov graf nima hamiltonovega cikla, saj nikakor ne moremo končati v začetni točki.

Ampak ker ni dovolj, da poskušamo, to dokažimo. Torej, hamiltonov cikel je zaključena pot, ki vsebuje vse točke grafa. V zunanjem ciklu moramo porabiti vsaj 3 povezave, da bodo vsebovane vse točke.

Iz notranjega cikla moramo porabiti še rumene povezave:

In s tem bi ustvarili cikel ustvarili še preden bi končali. Torej petersonov graf ni hamiltonov.

Teorija grafov in kombinatorika, Martin Juvan in Primož Potočnik, 2. natis, Ljubljana, str. 27 - 31