Projekti / Programi
Hamiltonski cikli v točkovno tranzitivnih grafih
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.05 |
Naravoslovje |
Matematika |
Teorija grafov |
| Koda |
Veda |
Področje |
| P110 |
Naravoslovno-matematične vede |
Matematična logika, teorija množic, kombinatorika |
| Koda |
Veda |
Področje |
| 1.01 |
Naravoslovne vede |
Matematika |
hamiltonski cikel, hamiltonska pot, točkovno tranzitiven graf, Cayleyjev graf
Raziskovalci (1)
| št. |
Evidenčna št. |
Ime in priimek |
Razisk. področje |
Vloga |
Obdobje |
Štev. publikacijŠtev. publikacij |
| 1. |
24997 |
dr. Klavdija Kutnar |
Matematika |
Vodja |
2011 - 2013 |
251 |
Organizacije (1)
Povzetek
Pot (cikel), ki vsebuje vse točke grafa, imenujemo hamiltonska pot (hamiltonski cikel). Zaradi povezave s problemom štirih barv in problemom trgovskega potnika so bili hamiltonski cikli v teoriji grafov predmet številnih raziskav. Graf je točkovno tranzitiven, če za poljubni njegovi točki u in v obstaja avtomorfizem, ki slika točko u v točko v. Leta 1969 je Lovasz povezal omenjena koncepta z naslednjim vprašanjem: Ali vsak povezan točkovno tranzitiven graf premore hamiltonsko pot? Obravnava tega vprašanja je pripeljala do vprašanja: Ali vsak povezan Cayleyjev graf premore hamiltonski cikel? (Cayleyjev graf je graf, katerega grupa avtomorfizmov premore podgrupo, ki deluje regularno na množici točk grafa.) Čeprav problema raziskujejo že več kot 40 let, sta še vedno oba nerešena, je pa objavljenih veliko delnih rezultatov. Številni med njimi so bili dobljeni v okviru doktorskega usposabljanja vodje predlaganega projekta. Cilj predlaganega projekta so novi rezultati na problemu hamiltnoskost točkovno tranzitivnih grafov (HPC problem). Natančneje, rešiti HPC problem za posebne neskončne družine točkovno tranzitivnih grafov in Cayleyjevih grafov z restrikcijami na posebne rede, posebne valence in posebna delovanja grupe avtomorfizmov. Najprej bomo končali že začete raziskave: HPC problem za kubične CG grup G z (2,s,3) -prezentacijo, t.j. G=(a,x | a2= xs=(ax)3=1, …); HPC problem za točkovno tranzitivne grafe reda pq, p in q praštevili. Potem bomo obravnavali HPC problem za točkovno tranzitivne grafe reda pk, p praštevilo, in drugih posebnih redov kot tudi za Cayleyjeve grafe grup z (2,s,t) –prezentacijo (posplošitev zgornjega rezultata). Med predlaganim projektom bodo obravnavani tudi drugi problemi povezani s točkovno tranzitivnimi grafi, kot so odprt problem polregularnosti (Marušič, 1981), strukturne lastnosti točkovno tranzitivnih grafov in lastnosti grup avtomorfizmov. Namreč, pogosto uporabljena metoda za iskanje hamiltonskih ciklov v točkovno tranzitivnih grafih sloni na kvocientiranju glede na neprimitivnostni sistem blokov grupe avtomorfizmov ali glede na polregularen avtomorfizem (Metoda dviga). Pri raziskovanju HPC problema za kubične Cayleyjeve grafe bomo posplošili inovativno metodo - metodo Hamiltonskih dreves na ploskvah. Med drugim bomo uporabljali tudi rezultate iz splošne teorije grafov, kombinatorične tehnike skupaj z njihovo uporabo v teoriji permutacijskih grup in algebraične metode. Pričakovani rezultati sodijo med najpomembnejše naslednje korake, ki jih je potrebno narediti za popolno rešitev HPC problema. Objavljeni bodo v SCI revijah. Njihova posledica bodo zagotovo številna povabila na raziskovalne obiske in vabljena predavanja po svetu. Tako bodo tudi pripomogli k mednarodni prepoznavnosti Slovenije.
Pomen za razvoj znanosti
Pomembnost raziskovalnih rezultatov projekta je razvidna iz obsežne svetovne bibliografije in citiranosti le-teh. Rezultati projekta sodijo med najpomembnejše naslednje korake, ki jih je bilo potrebno narediti za popolno rešitev problema obstoja hamiltonskih ciklov in poti v točkovno tranzitivnih grafih. Poleg tega bodo rezultati morda prispevali pomembne napredke pri reševanju drugih aktualnih odprtih problemov na področju algebraične teorije grafov (kot na primer, problem obstoja polregularnih avtomorfizmov v točkovno tranzitivnih grafih in problem ne-obstoja snarkov med kubičnimi Cayleyevimi grafi).
Pomen za razvoj Slovenije
S tem projektom je Slovenija ohranila stik s svetovnimi trendi v matematiki na tistih področjih, ki jih je projekt pokrival. Rezultati projekta so bili predstavljeni na mednarodnih znanstvenih konferencah, srečanjih in poletnih šolah po celem svetu, šestkrat kot vabljeno/plenarno predavanje, kot tudi na prestižnih univerzah v tujini (Vanderbilt University, FU Berlin, The University of the Basque Country, ...). S tem je projekt pripomogel k promociji slovenske znanosti v tujini. Mednarodna vpetost projekta, in torej Slovenije, se kaže tudi v velikem zanimanju za doktorska in podoktorska usposabljanja tujcev pri raziskovalni skupini na Univerzi na Primorskem, ki deluje na področju algebraične teorije grafov (raziskovalci prihajajo iz Madžarske, Kitajske, ZDA, ...).
Najpomembnejši znanstveni rezultati
Letno poročilo
2011,
2012,
zaključno poročilo,
celotno poročilo na dLib.si
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Letno poročilo
2011,
2012,
zaključno poročilo,
celotno poročilo na dLib.si
