Hamiltonov cikel

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Hamiltonova pot je v teoriji grafov 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 Hamiltonove poti oz. cikla ne obstaja enostaven algoritem, lahko pa si pomagamo z naslednjima izrekoma.

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.

Orejev izrek
Naj bo G enostaven graf z vsaj 3 točkami. Če je za poljubni nesosednji točki a in b vsota stopenj a in b večja ali enaka številu točk v grafu, potem G vsebuje Hamiltonov cikel.

Opomba: Rečemo, da je nek graf hamiltonov, če vsebuje Hamiltonov cikel.

Primeri: 1) Ali je dani graf hamiltonov? (t. j. ali vsebuje Hamiltonov cikel?)

Slika:primer0.jpg

Najprej preštejemo stopnje točk in vidimo, da je najmanjša stopnja enaka 3. Vseh točk v grafu je 6. Torej je najmanjša stopnja točke enaka polovici vseh točk v grafu. Po Diracovem izreku je graf hamiltonov, torej vsebuje Hamiltonov cikel. Ena izmed možnih rešitev je narisana na spodnji sliki.

Slika:primer0_r.jpg


2) Ali je dani graf hamiltonov? (t. j. ali vsebuje Hamiltonov cikel?)</p>

Slika:primer3.jpg

Graf je hamiltonov. Rešitev lahko prikažemo tudi drugače. Najprej oštevilčimo vozlišča.

Slika:primer3_o.jpg

Ena izmed možnih rešitev je cikel, ki poteka skozi točke: 1 -> 2 -> 3 -> 12 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 1.


Glej tudi

Osebna orodja