Projekti / Programi
01. januar 2009
- 31. december 2014
Koda |
Veda |
Področje |
Podpodročje |
1.01.00 |
Naravoslovje |
Matematika |
|
1.07.00 |
Naravoslovje |
Računalniško intenzivne metode in aplikacije |
|
2.07.00 |
Tehnika |
Računalništvo in informatika |
|
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 |
topološka teorija grafov, barvanja grafov, grafovski produkti, metrična teorija grafov, teorija algoritmov, minorji grafov, povezanost, diskretna geometrija.
Raziskovalci (34)
Organizacije (1)
Povzetek
Celotna programska skupina s svojimi raziskavami pokriva precejšnji del področja teorije grafov in njene uporabe v drugih področjih matematike in v drugih vedah. Glavnina raziskav bo posvečena naslednjim področjem. Raziskovali bomo osnovne lastnosti grafov, ki so vloženi na ploskvah. Skušali bomo karakterizirati ovire za obstoj vložitev, razviti učinkovite algoritme za vlaganje. V zvezi s teorijo grafovskih minorjev bomo raziskovali prekrižno število, neizbežne strukture v velikih grafih in prepovedane minorje za nekatere minorsko zaprte družine. Raziskovali bomo spektralne lastnosti (vloženih) grafov, predvsem glede na Laplaceov operator grafa. Ukvarjali pa se bomo še z barvanji grafov, predvsem s seznamskimi barvanji, neponavljajočimi barvanji, krožnim kromatičnim številom, s pretoki v grafih ipd. Obravnavali bomo tudi grafovske produkte, njihove invariante in sorodne probleme. Študirali bomo medianske grafe s poudarkom na problemu prepoznavanja. V povezavi z medianskimi grafi bomo obravnavali tudi različne druge razrede grafov, ki se naravno pojavijo pri tej teoriji: izometrične podgrafe hiperkock, semi-medianske grafe, kvazi-medianske grafe in izometrične podgrafe Hammingovih grafov. Metrično teorijo grafov bomo med drugim uporabili v kemijski teoriji grafov za izračun različnih topoloških invariant. Na področju računalniške matematike se nameravamo posebej posvetiti razvoju hitrih algoritmov za prepoznavanje pomembnih razredov grafov in problemom v zvezi s posplošitvami klasičnega problema hanojskih stolpov. V sodelovanju z Univerzo v Aucklandu na Novi Zelandiji bomo izvedli obsežno računsko delo na mreži več kot 200 računalnikov za preverjanje nekaterih znanih hipotez.
Pomen za razvoj znanosti
Projekt spada med temeljne raziskave s področja matematike. Problemi, ki si jih zastavljamo, so mednarodno pomembni, kar med drugim dokazuje naša bibliografija iz zadnjega obdobja in odmevnost rezultatov. Obravnavani problemi so osrednji v teoriji grafov, hkrati pa imajo aplikacije v drugih znanostih. Tako na primer rezultati o ogljikovih nanoocevkah lahko pripomorejo pri sintezi nanomolekul in pospešijo razvoju nanomaterialov. Razdalja med grafi se uporablja na različnih znanstvenih področjih, kjer se proučujejo podobnosti med objekti. Nov pogled na te probleme s stališča razdalje med grafi pripomore k nadaljnjemu razvoju in novemu pogledu na obstoječe probleme, predvsem s področja biologije, računalništva, kemije, socioloških znanosti in lingvistike. Študija grafovskih invariant obravnava nekatere pomembne realne probleme. Tako na primer pri problemu dodeljevanja frekvenc iščemo optimalno dodelitev frekvenc za oddajnike v brezžičnem omrežju. V radijskem omrežju je vsakemu oddajniku dodeljen frekvenčni kanal. Dva oddajnika se lahko motita??, če sta postavljena preblizu. Tudi če oddajnika uporabljata različne frekvence, se še vedno lahko pojavljajo motnje, če se nahajata blizu drug drugega. Frekvenčni spekter je zaradi vedno večjega povpraševanja vedno bolj dragocen. Naloga dodeljevanja frekvenc je tako čim bolj zmanjšati število frekvenc in se pri tem izogniti motnjam. Rezultati raziskovalnega programa so bili objavljeni v vodilnih mednarodnih revijah s področja diskretne matematike in predstavijeni na mednarodnih znanstvenih konferencah. Imeli smo večje število vabljenih plenarnih predavanj. S tem bomo še okrepili dosedanji zavidljiv mednarodni ugled slovenske šole teorije grafov.
Pomen za razvoj Slovenije
Raziskovalni program je naravnan tako, da omogoča vključevanje najsposobnejših mladih raziskovalcev in s tem omogoča dolgoročno ohranjanje kvalitetnega raziskovalnega dela s področja matematike, kar ima pozitiven vpliv na kvaliteto univerzitetnih programov matematike in drugih znanosti. V obdobju 2009-2014 smo bili v naši skupini mentorji 9 doktorantom. Naši doktoranti se po koncu usposabljanja zaposlujejo tudi v gospodarstvu, kar ima pozitiven vpliv na gospodarstvo. Ker je matematika prisotna na mnogih drugih področjih, kvalitetno raziskovanje matematike posredno vpliva tudi na razvoj vrste drugih disciplin. Znotraj matematike pa program predvsem razvija teorijo grafov in s tem ohranja in krepi njen svetovni nivo. Pričakovani rezultati so predvsem teoretični. Kljub temu pa imajo veliko potencialno uporabo v praksi, kar se posebej nanaša na naša algoritmična in optimizacijska raziskovanja. To dobro potrjujejo dosedanje raziskave, ki so pripeljale do sodelovanja s slovensko industrijo s področja tehnološkega razvoja, predvsem v informacijskih in telekomunikacijskih tehnologijah. V juniju 2015 načrtujemo izvedbo konference “8th Slovenian International Conference on Graph Theory” na kateri pričakujemo 200-300 udeležencev. Gre za eno izmed največjih svetovnih konferenc s področja teorije grafov. Naša programska skupina bo vodila organizacijo dogodka, je vodja programa glavni organizator konference.
Avdiovizualni viri (1)
št. |
Naslov (s povezavo na video) |
Dogodek |
Vir |
1. |
Teorija grafov |
|
Video predstavitev raziskovalnega programa
|
Najpomembnejši znanstveni rezultati
Letno poročilo
2009,
2010,
2011,
2012,
2013,
zaključno poročilo,
celotno poročilo na dLib.si
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Letno poročilo
2009,
2010,
2011,
2012,
2013,
zaključno poročilo,
celotno poročilo na dLib.si