Hamiltonov problem

 

Kot smo že omenili, je leta 1843 Hamilton odkril kvaternione. S tem v zvezi je povezan tudi naslednji problem: na pravilnem dodekaedru poišči iz dane začetne točke cikel, ki obišče vsa oglišča dodekaedra. Splošnejša oblika tega problema, torej iskanje cikla v katerem obiščemo vsako točko danega grafa imenujemo po njem iskanje Hamiltonovega cikla. Graf, v katerem obstaja kak Hamiltonov cikel imenujemo Hamiltonov graf.

Iz povedanega problema je Hamilton naredil igro, ki jo je poimenoval ikozaedrska igra  (Icosian game), v kateri mora igralec z danimi začetnimi oglišči  na  mreži dodekaedra poiskati Hamiltonov cikel.   Hamilton je idejo za igro prodal nekemu trgovcu za 25 funtov in igro so začeli prodajati skupaj z navodili. Izkazalo pa se je, da je bila kupčija slaba - za trgovca.

Posvetimo se sedaj ugotavljanju, kateri grafi so Hamiltonovi in kateri ne. Na prvi pogled je  iskanje Hamiltonovega cikla na grafu podobno iskanju Eulerjevega obhoda na grafu, vendar temu ni tako, saj ne poznamo nobenega pogoja, ki bi bil hkrati potreben in zadosten pogoj za hamiltonovost grafa. Poznamo pa dva pogoja, ki sta zadostna - to sta Orejev in Diracov pogoj. Ta dva pogoja na danem grafu ni težko preveriti in če sta izpolnjena torej zagotavljata hamiltonovost grafa.

Preden pa si ju ogledamo, si oglejmo nekaj grafov, ki so Hamiltonovi. Recimo graf

graf

 

je Hamiltonov. Če začnemo v točki 1, je ena od možnosti za hamiltonov cikel pot 1 - 2 - 3 - 4 - 5 - 1. Tudi 1 - 3 - 5 - 2 - 4 - 1   je rešitev, torej rešitev, če obstaja ni nujno samo ena.

Prav tako je naslednji graf Hamiltonov.

graf

 

Če začnemo v 1, je ena od rešitev   1 - 4 - 2   - 3 - 1.

Za navedena grafa ni bilo težko preveriti, da sta Hamiltonova. Problemi pa se pojavijo, ko ima graf veliko točk in povezav. Takrat včasih prideta prav  že omenjena zadostna pogoja. Prvega je leta 1952 dokazal in objavil A.Dirac, glasi pa se takole.

Diracov izrek.  Naj bo G enostavni graf z n točkami, n > 2. Če je stopnja vsake točke v grafu večja                         ali kvečjemu enaka n/2, je graf G Hamiltonov.

Preverimo ta pogoj na prvem grafu. Na grafu je pet točk, stopnje vseh točk na grafu pa so enake štiri. Pogoj v Diracovem izreki je izpolnjen, torej je graf res Hamiltonov. Opazimo pa še tole: na prvem grafu iz dane točke vodijo vse možne povezave v ostale točke. Take grafe imenujemo polni grafi in jih označimo s K(n), kjer je n število točk v grafu. Za polne grafe je stopnja poljubne točke na grafu enaka (n-1) in ker je n-1 > n/2 za n > 2, so vsi polni grafi z več kot dvema točkama Hamiltonovi.

Preverimo še drugi graf. Imamo štiri točke, stopnja poljubne točke na grafu pa je enaka 2. Pogoj v Diracovem izreku je izpolnjen in graf je Hamiltonov.

Drugi zadostni pogoj pa je Orejev pogoj. Ta je bil dokazan leta 1960.

Orejev izrek.  Naj bo G enostavni graf z več kot dvemi točkami. Če za poljubni nesosednji točki v in                         w   velja

deg v  +  deg  w  >   n - 1 ,

                       potem je graf G Hamiltonov.

Ponazorimo uporabo obeh izrekov na naslednjem grafu. Graf

 

graf

 

ima pet točk, stopnja prve točke pa je enaka dve, torej Diracovega izreka ne moremo uporabiti. Vendar pa  za poljubni točki v in w na grafu velja

deg v + deg w > 4 ,

torej je graf Hamiltonov po Orejevem izreku.

Diracov in Orejev pogoj sta le zadostna pogoja za to, da je graf Hamiltonov. Če torej nobeden od njiju ni izpolnjen, še ne moremo reči, ali je graf Hamiltonov, ali ne. Da graf ni Hamiltonov, lahko pokažemo na več različnih načinov. Ena (ne preveč privlačna) možnost je pregledovanje vseh možnosti, z upoštevanjem specifičnosti grafa (recimo simetričnosti,...).

Za konec pa si oglejmo še dva problema, povezana z iskanjem Hamiltonovega obhoda. Prvi je t.i. problem skakačevega sprehoda. Problem sam je bil formuliran že veliko pred Hamiltonom, glasi pa se takole: ali lahko skakač obišče vsako polje šahovnice z zaporedjem skokov in zaključi sprehod na začetnem polju?

Zato, da bomo videli povezavo tega problema s problemom iskanja Hamiltonovega cikla v grafu, si poglejmo poenostavljeni problem na šahovnici velikosti 4 *4. Šahovnico lahko predstavimo z grafom, v katerem točke ustrezajo poljem šahovnice, točki pa povežemo, če lahko skakač skoči med ustreznima poljema na šahovnici. Na naslednjem diagramu je 4 4 šahovnica in pripadajoči graf.

šahovnica        pripadajoči graf             

Odgovor na postavljeno vprašanje je torej pozitivno natanko tedaj, ko je pripadajoči graf Hamiltonov. S pomočjo Diracovega in Orejevega izreka lahko za nekatere velikosti šahovnic povemo da je odgovor pritrdilen. Izkaže pa se, da 4.4 šahovnici ni nobenega takega skakačevega obhoda (z nekaj poizkušanja lahko to ugotovite tudi sami.)

Drugi problem je tudi že zelo star.   Posredovanje informacij od ene osebe do druge ali iz enega mesta v drugega ima dolgo zgodovino; razvoj primernih tehnik za dosego tega cilja je bil pogosto obarvan z intrigami (pogosto politične ali vojaške narave). Za zaščito zasebnosti in varnosti so z leti prišle v rabo različne kode, katerih osnovni namen je bil preprečiti nepoklicanim dostop do informacij. V zadnjem času so ob hitri širitvi informacijskih tehnologij kode za predstavitev informacij prišle v široko uporabo. To je v veliki meri posledica vpeljave digitalne tehnike, tako da celo analogne signale (take, ki se zvezno spreminjajo, kot recimo zvočni signal) zdaj običajno "razrežejo na diskretne rezine" in jih predstavijo v digitalni obliki. Rezultat tega razvoja je tudi sprememba besede koda, ki zdaj pomeni končni sistem različnih simbolov, ki jih uporabljamo za procesiranje ali prenašanje digitalizirane informacije po komunikacijskih kanalih.

Recimo, da bi radi predstavili položaj rotorja (z večkratniki kota 45), ki se lahko zvezno spreminja.  

 

                                                        položaj rotorja                                                                                      

 

S tremi krtačkami lahko kot, v katerem je rotor, pretvorimo v trimestno dvojiško številko. Zapišimo številke, ki ustrezajo posameznim kotom:

Na ta način dobimo kodo, ki ji pravimo Grayeva koda. Ko se rotor vrti, se vrednost spremeni ob vsakem prehodu v nov položaj v nov položaj samo za en bit. Zaradi konstrukcije opreme spremembe več bitov hkrati niso možne in deloma so zaradi tega Grayeve kode tako široko uporabne.

Grayeve kode lahko najdemo kot Hamiltonove cikle na grafu t.i. n - dimenzionalne hipeerkocke Q(n). Na primer zgornja koda in koda   000 - 100 - 110 - 010 - 001 - 111 - 101 - 001 - 000 ustrezata hamiltonovima cikloma 3- kocke na spodnji sliki.

                                                               pripadajoči graf

 

                                                                                          nazaj.gif (981 bytes)