Projekti / Programi
01. januar 2015
- 31. december 2021
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.00 |
Naravoslovje |
Matematika |
|
| 1.07.00 |
Naravoslovje |
Računalniško intenzivne metode in aplikacije |
|
| 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 |
matematika, teorija grafov, topološka teorija grafov, metrična teorija grafov, grafovski produkti, kemijska teorija grafov, geometrijski grafi, grafovske invariante, algoritmična teorija grafov, uporabe teorije grafov
Raziskovalci (24)
Organizacije (2)
Povzetek
Cilj programa je razvijati osrednja področja teorije grafov ter s tem krepiti vlogo, prepoznavnost in vpliv slovenske teorije grafov kot enega izmed svetovnih centrov tega področja matematike. Med področji, ki jih nameravamo še posebno razvijati, so topološka teorija grafov, metrična teorija grafov, grafovski produkti, kemijska teorija grafov, geometrijski grafi, grafovske invariante, algoritmična teorija grafov ter aplikacije naštetih področij. Navedimo nekaj osrednjih problemov in tematik, ki jih bomo raziskovali.
Prioritete raziskav v topološki teoriji grafov bodo iskanje minorjev in vtopitev (imerzij) v grafe, ki so vloženi v sklenjene ploskve, študij strukturnih značilnosti problema prekrižnega števila grafov ter raziskave na področju risanja grafov. V metrični teoriji grafov bomo raziskovali razrede grafov medianskega tipa, za katere je bila dokazana lokalno-globalna karakterizacija njihovih kompleksov in so motivirani z geometrijsko teorijo grup. Raziskali bomo druge naravne posplošitve medianskih grafov in sicer glede na njihovo umeščenost v šibko modularnih grafih in njihove lastnosti, kot so izrek o fiksni točki, kontraktibilnost in retraktibilnost iz produktnih prostorov. Študirali bomo možnosti merjenja razdalje med grafi zasnovane na pojmu Hausdorffove grafovske razdalje. To je povsem nova ideja, ki smo jo pred kratkim začeli razvijati v naši skupini. Na grafovskih produktih bomo nadaljevali raziskave konveksnosti (Steinerjeva, geodetska), raziskovali bomo različne označitve produktov in njihove algoritmične vidike. Na področju kemijske teorije grafov bomo med drugim raziskovali aktualno področje ogljikovih nanocevk, v posebnem nas bo zanimala struktura in lastnosti resonančnih grafov teh nanocevk. Clarovo število je znano le za nekatere posebne razrede benzenoidni grafov. Nameravamo tudi razviti polinomski algoritem, ki bi izračunal Clarovo število za bolj splošne grafe, kot so posebni razredi benzenoidnih grafov. Naš glavni raziskovalni cilj na področju geometrijskih grafov bo raziskati, katere probleme lahko rešimo učinkoviteje za grafe, ki so določeni z geometrijskimi omejitvami. Na področju grafovskih invariant nas bodo po eni strani zanimali razredi grafov, ki dopuščajo pragovna barvanja, po drugi strani ovirami-kritični grafi, t.j. najmanjšimi grafi, ki pragovnega barvanja ne dopuščajo. Nadaljevali bomo z raziskavami dominacijskih problemov na produktih grafov in z raziskavami dominacijske igre na grafih. Med ostalimi invariantami, ki nas bodo posebej zanimale, naj izpostavimo b-barvanja vozlišč in povezav, učinkovito odprto in totalno dominacijo in L(p,q,r)–označevanja. Med vsemi našimi raziskavami bomo stalno imeli v mislih tudi algoritmične vidike. Na primer, poskušali bomo izboljšati časovno zahtevnost dekompozicijskega algoritma za krepki produkt, razviti hitre algoritme za posebne ravninske grafe in hitre algoritme za geometrijske presečne grafe.
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.
Pričakujemo, da bomo rezultate tega raziskovalnega programa objavili v vodilnih mednarodnih revijah s področja diskretne matematike in predstavili na mednarodnih znanstvenih konferencah. Pričakujemo, do bomo imeli večje število vabljenih plenarnih predavanj, kar bo še povečalo pomen naših raziskovalnih dosežkov. S tem bomo še okrepili že sedaj 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, še trije zagovori doktoratov so predvideni do konca tega leta. 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, v posebnem je vodja programa glavni organizator konference.
Najpomembnejši znanstveni rezultati
Letno poročilo
2015,
vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Letno poročilo
2015,
vmesno poročilo
