Hamiltonski indeks grafa
The hamiltonian index of a graph
M. Lovrečič Saražin, Inštitut za kovinske materiale in tehnologije, Lepi pot 11, Ljubljana
Članek povzema predavanje na 42. Posvetovanju o metalurgiji in kovinskih gradivih i/ Portorožu 3. oktobra 1991, v katerem je avtor na kratko predstavil svoje magistrsko delo, izdelano v okviru Akcije 2000 novih raziskovalcev.
The author's M aster Thesis was presented on the 42nd Colloquium on Metali urgy in Portorož at October 3rd 1991. The Thesis was developed at the Institute of Metals and Technologies under the program "2000 New Researchers" and it is shortly resumed in this article.
1 Uvod
Eno najzanimivejših področij v matematiki je gotovo teorija grafov. Zdi se, da je zelo malo znana zunaj srenje matematikov, za razliko od klasične matematike (kamor spadajo npr. analiza realnih funkcij, klasična algebra, diferencialni in integralni račun itd.), o katere "uporabnosti" ne gre dvomiti. Pa vendar je možno rezultate teorije grafov uporabiti na vrsti konkretnih problemov. Razlog za nepoznavanje je dejstvo, da je teorija grafov razmeroma mlada matematična disciplina, ki se je na široko razvila šele v tem stoletju, predvsem po II. svetovni vojni. Uvrščamo jo v diskretno matematiko, tj. tisti del matematičnih raziskav, ki se ukvarja s končnimi množicami. Za primerjavo povejmo, da je klasična analiza funkcij zasnovana na množici realnih števil, ki jo konstruiramo iz množice naravnih števil, obe pa sta neskončni. V diskretno matematiko spadajo med drugim tudi abstraktna teorija algoritmov, programskih jezikov in formalnih jezikov nasploh ter teoretično računalništvo.
Predmet obravnave teorije grafov je abstraktni pojem grafa. Graf je urejen par G — (V, E), pri čemer je
l'	poljubna neprazna končna množica, katere
elemente imenujemo točke grafa;
E	poljubna množica (neurejenih) parov točk iz
\ , ki jim rečemo povezave.
Če sta npr. t/, r £ l' točki grafa G in {u, c} G E povezava v G, potem jo na kratko označimo kar z uv in rečemo, da veže točki u in v. Seveda je vu isto kot uv. Če je uv povezava grafa G, pravimo, da sta si točki u in v sosedni. Primer grafa se nahaja na sliki 1. Točke so narisane kot krožci, povezave pa kot črte, ki vežejo krožce.
Kaj lahko počnemo z. grali? Na teh abstraktnih objektih je možno definirati zelo veliko raznih lastnosti. Tipičen problem je poiskali neki graf ali kar vse grafe, ki ustrezajo tem in onim lastnostim. V praksi običajno pridemo do opti-mizacijskega problema, kot kaže naslednji primer: trgovski potnik mora na nekem območju (ki ima cestno omrežje) obiskati določeno število strank. Kako naj to naredi, da bi si prihranil čim več prevoženih kilometrov in časa? Problem lahko abstrahiramo tako, da stranke proglasimo za "točke" nekega "grafa", cestne zveze med strankami pa za "povezave". Vsaki "povezavi" priredimo neko število ("dolžino"), ki je dejansko dolžina ustrezne ceste. Za trgovskega potnika moramo tedaj najti "obhod", katerega
Figure 1. An example of a graph.
skupna "dolžina" bo najmanjša možna pri pogoju, da gre skozi vsako "točko". Pojme, ki so opremljeni z narekovaji, lahko povsem precizno definiramo. Na ta način smo formulirali abstraktni problem, ki mu v matematiki rečemo problem trgovskega potnika (angl. the travelling salesman problem). Obstaja pa še mnogo drugih problemov, ki jih lahko rešujemo v okviru teorije grafov.
2 Magistrsko delo
Pri izdelavi magistrskega dela je imel avtor dva motiva. Najprej povejmo še enkrat, da je vsak graf natanko določen z dvema množicama: množico točk in množico povezav. V matematiki je zelo pogosta metoda zamenjave vloge elementov dveh množic med seboj. V teoriji grafov se lahko vprašamo naslednje: ali pri danem grafu G = (V, E) obstaja graf L(G), ki bi imel E za množico točk, V pa za množico povezav? Odgovor je pozitiven, vendar vlogi točk in povezav ni mogoče povsem zamenjati. Tukaj ne moremo natančneje razložiti, kaj to pomeni, povejmo le, da je treba poleg sosednosti točk definirati še sosednost povezav. Grafu L(G) rečemo graf povezav grafa G in je z G popolnoma določen. Nekatere lastnosti grafa G se ohranijo tudi v L(G). Še bolj zanimiva je obratna pot: raziskovati tiste lastnosti grafa L(G), ki jih lahko najdemo tudi v G, ne da
bi študirali strukturo grafa G. Ta postopek pride do izraza takrat, kadar je L(G) za obravnavo "enostavnejši" od G.
Drugi motiv je v računanju karakterističnih števil, ki jih priredimo grafom. V splošnem lahko karakteristična števila prirejamo mnogim matematičnim pojmom. Npr. vsaki množici priredimo njeno moč, tj. število elementov, ki jih vsebuje*, vsaki odvcdljivi funkciji pa odvod v dani točki, ali integral na določenem intervalu, itn.
Slika 3. Graf s Hamiltonovim ciklom in graf brez njega. Figure 3. A graph u-ith hamiltonian cycle and a graph without it.
grafa G graf povezav L(G). Na isti način lahko iz L(G) naredimo njegov graf povezav L(L(G)) — L~(G), itn. Rezultat tega procesa je celo zaporedje grafov povezav
Slika 2. Dva grafa.
Figure 2. Two graphs.
Grafu lahko priredimo število njegovih točk ali pa število povezav. Vsa ta števila so nedvoumno določena in neodvisna od konkretne predstavitve objekta. Kaj to pomeni, bomo pojasnili pri grafih. Za dani graf ni pomembno, kaj so njegove točke, marveč le, kako so točke povezane. To se pravi, da imamo lahko na različnih množicah točk isti graf, in za vsako "implementacijo" grafa je število točk enako. Zaradi tega rečemo karakterističnim številom invariante. Npr. število povezav danega grafa je njegova invarianta. Invarianta sama še ne določa objekta povsem natanko. Na sliki 2 sta narisana dva grafa, ki imata enako število točk in enako število povezav, pa kljub temu nista enaka. Zanimivo bi bilo vedeti, ali obstaja končna množica invariant, ki bi natanko določala vsak graf. Ta trditev do sedaj še ni niti dokazana niti ovržena. Ce bi bila dokazana, bi to pomenilo, da imamo končno mnogo (recimo 1134) invariant in vsak graf bi bil določen s tisoč stoštiriintridesetimi naravnimi števili. Zdi se, da je do take množice invariant težko priti, če je to sploh mogoče. Kljub temu pa vsaka invarianta vsaj nekaj pove o določenem grafu.
Ena od grafovskih invariant se imenuje hamiltonski indeks, pred njegovo definicijo pa potrebujemo še en pojem. Po grafu G se lahko "sprehajamo" tako, da se postavimo v neko točko x, gremo po povezavi .rt/ do točke y, itn. Hamiltonov obhod (ali tudi Hamiltonov cikel) je tak obhod v G, ki se začne in konča v isti točki ter gre skozi vsako točko natanko enkrat*. Nekateri grafi posedujejo enega ali celo več Hamiltonovih ciklov (glej levi graf na sliki 3, Hamiltonov cikel je označen s puščicami), nekateri pa nobenega (desni graf na isti sliki). Naredimo zdaj iz
G = L°(G), L(G) = L1 (G), L2(G).
(D
Izkaže se, da za skoraj vse grafe G (razen nekaj trivialnih in nezanimivih primerov) obstaja v zaporedju (1) vsaj en tak graf, ki vsebuje Hamiltonov cikel. Najmanjši ji, za katerega Ln(G) vsebuje Hamiltonov cikel, imenujemo hamiltonski indeks grafa G. O tej invarianti je zelo malo znanega; v splošnem jo je zelo težko izračunati. Preostane nam, da skušamo dobiti zgornje in spodnje meje za hamiltonski indeks, ki se izražajo z drugimi, laže izračunljivimi grafovskimi invariantami. V magistrskem delu je avtor uspel najti nekaj novih in učinkovitih omejitev. Napisani so trije članki in poslani v objavo v dve tuji matematični reviji.
"Mimogrede povejmo, da tudi neskončnim množicam prirejamo moč: množica vseh naravnih števil ima moč števne neskončnosti (označeno z N0. tj. hebrejsko črko "alef" z indeksom 0), množica vseh realnih števil pa ima moč kontinuuma (N, "alef" brez indeksa). Simbola N0 in K predstavljata dva primera t.i. tninsfinitiuh števil.
'W. R. Hamilton je znani angleški matematik iz prejšnjega stoletja.