Nalaganje ...
Projekti / Programi vir: ARIS

Teorija grafov

Obdobja
Raziskovalna dejavnost

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 
Ključne besede
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
Vrednotenje (pravilnik)
vir: COBISS
Raziskovalci (24)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacijŠtev. publikacij
1.  35352  dr. Jernej Azarija  Matematika  Raziskovalec  2015 - 2018  25 
2.  22402  dr. Drago Bokal  Matematika  Raziskovalec  2015 - 2021  242 
3.  17005  dr. Boštjan Brešar  Matematika  Raziskovalec  2015 - 2021  406 
4.  25993  dr. Sergio Cabello Justo  Matematika  Raziskovalec  2015 - 2021  218 
5.  32028  dr. Tanja Dravec  Matematika  Raziskovalec  2016 - 2021  147 
6.  16332  dr. Gašper Fijavž  Matematika  Raziskovalec  2015 - 2020  121 
7.  34564  dr. David Gajser  Matematika  Raziskovalec  2015 - 2021  33 
8.  55745  Jaka Hedžet  Matematika  Mladi raziskovalec  2021 
9.  50518  dr. Vesna Iršič  Matematika  Raziskovalec  2017 - 2021  55 
10.  29919  dr. Marko Jakovac  Matematika  Raziskovalec  2015 - 2021  161 
11.  05949  dr. Sandi Klavžar  Matematika  Vodja  2015 - 2021  1.180 
12.  38147  dr. Tim Kos  Matematika  Mladi raziskovalec  2015 - 2019  24 
13.  22648  dr. Tadeja Kraner Šumenjak  Matematika  Raziskovalec  2015 - 2021  122 
14.  34562  dr. Matjaž Krnc  Matematika  Mladi raziskovalec  2015  95 
15.  37403  dr. Tilen Marc  Matematika  Raziskovalec  2015 - 2021  47 
16.  08727  dr. Uroš Milutinović  Matematika  Raziskovalec  2015 - 2021  348 
17.  01931  dr. Bojan Mohar  Matematika  Raziskovalec  2015 - 2021  1.002 
18.  20839  dr. Iztok Peterin  Matematika  Raziskovalec  2015 - 2021  353 
19.  16013  dr. Ciril Petr  Matematika  Raziskovalec  2015 - 2021  68 
20.  24904  dr. Simon Špacapan  Matematika  Raziskovalec  2015 - 2021  111 
21.  21821  dr. Andrej Taranenko  Matematika  Raziskovalec  2015 - 2021  132 
22.  37537  dr. Niko Tratnik  Matematika  Raziskovalec  2017 - 2021  156 
23.  11666  dr. Aleksander Vesel  Računalniško intenzivne metode in aplikacije  Raziskovalec  2015 - 2021  339 
24.  18504  dr. Petra Žigert Pleteršek  Matematika  Raziskovalec  2015 - 2020  174 
Organizacije (2)
št. Evidenčna št. Razisk. organizacija Kraj Matična številka Štev. publikacijŠtev. publikacij
1.  0101  Inštitut za matematiko, fiziko in mehaniko  Ljubljana  5055598000  20.078 
2.  2547  Univerza v Mariboru, Fakulteta za naravoslovje in matematiko  Maribor  5089638051  18.102 
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
Zgodovina ogledov
Priljubljeno