Projekti / Programi
01. januar 2004
- 31. december 2008
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 |
topološka teorija grafov, barvanja grafov, grafovski produkti, metrična teorija grafov, teorija algoritmov, minorji grafov, povezanost, diskretna geometrija.
Raziskovalci (19)
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 bazne 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 centralni v teoriji grafov. Rezultate tega raziskovalnega programa smo objavili v uglednih mednarodnih revijah in predstavili na mednarodnih znanstvenih konferenceh. S tem smo okrepili že sedaj zavidljiv ugled slovenske šole iz teorije grafov. Dobljeni rezultati so predvsem teoretični. Kljub temu pa imajo potencialno uporabo v praksi. Dosedanje raziskave so že pripeljale do sodelovanja s slovensko industrijo s področja tehnološkega razvoja, predvsem v informacijskih in telekomunikacijskih tehnologijah (Hermes Softlab, Iskratel). 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. 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. Naše raziskave so močno vpete v mednarodno sodelovanje, tako na formalni kot tudi na osebni ravni. V svojih znanstvenih delih imajo vsi sodelavci na programu veliko število soavtorjev s celega sveta. Tako plodno sodelovanje je bilo vzpostavljeno v zadnjih 15 letih. V tem obdobju smo tudi formalno sodelovali v okviru različnih mednarodnih projektov: 1. Sodelovanje v projektu ALCOM (Pierre Rosenstiehl, Francija). 2. Sodelovanje z Madžarsko akademijo znanosti: vsakoletna dvotedenska izmenjava. 3. Sodelovanje v evropski znanstveni mreži DIMANET za diskretno matematiko. 4. Večkratni SLO-USA projekt iz teorije grafovskih minorjev (Neil Robertson in John Maharry z Ohio State University v ZDA). 5. Projekta A-SLO 2000-01 in 2002-03 ter dolgoletna izmenjava z Univerzo v Leobnu (Avstrija) in vsakoletna organizacija skupnega seminarja Ljubljana-Leoben. 6. PROTEUS projekt z IMAG v Grenoblu, Francija (Sylvain Gravier in Michel Mollard). 7. SLO-NEM projekt s Tehniško univerzo Ilmenau v Nemčiji (Thomas Bohme in Michael Stiebitz). Vsaka 4 leta organiziramo pomembno mednarodno konferenco iz teorije grafov (Slovenian Graph Theory Conference), ki ima od 100 do 200 udeležencev s celega sveta.
Pomen za razvoj Slovenije
Raziskave, ki jih izvaja programska skupina za teorijo grafov, so bazična oblika raziskav, ki so neposredno uporabne pri izdelavi in upravljanju omrežij, pri nadziranju poslovnih procesov, ter pri drugih optimizacijskih problemih, s katerimi se podjetja vsakodnevno srečujejo. To smo v raziskovalni skupini zaznali in se aktivno usmerili v plasiranje znanja, ki ga posedujemo, v gospodarstvo. Sodelovali smo pri izdelavi novih storitev in širjenju tržišč (projekti za podjetji ICIT in Ultra) ter pri strateških odločitvah za izboljšavo kakovosti napajanja z električno energijo (projekt za Elektroinštitut Milan Vidmar). Rezultati teh projektov so z optimiranjem delovanja podjetij, ki produkte uporabljajo, neposredno vplivali na znižanje stroškov poslovnih procesov ter na zmanjšanje porabe energije, pri naših neposrednih naročnikih pa izdelki predstavljajo novo storitev ter s tem razširitev dejavnosti. Kakovost izdelkov je dovolj visoka, da naši naročniki načrtujejo izvoz tehnologij na tuja tržišča, s čemer smo posledično sodelovali pri večanju njihovega deleža izvoza, zaradi prilagajanja izdelka posameznim naročnikom pa so že odprli tudi nova delovna mesta. Za potrebe uporabe rezultatov naših raziskav so podjetja morala posodobiti svoje tehnološke platforme, da so lahko uporabila izdelek, ki je nastal v sodelovanju z naročniki naših storitev. Z optimiranjem poslovnih procesov in optimiranjem logistike rezultati naše raziskovalne skupine neposredno posegajo na področje izboljšanja vodenja in upravljanja ter na dvig kakovosti življenja posameznikov, ki sodelujejo v teh delovnih procesih. Z zavedanjem o pomenu optimiranja spodbujamo tudi varčno upravljanje z okoljem, trajnostni razvoj in s tem razvoj civilne družbe. S študjiem fundamentalnih lastnosti omrežij in njihovim izkoriščanjem pri optimizaciji sodelujemo pri optimalnem razvoju informacijsko-komunikacijske infrastrukture, s projektom z Elektroinstitutom Milan Vidmar pa smo posegli tudi na področje razvoja elektroenergetske infrastrukture.
Najpomembnejši znanstveni rezultati
Zaključno poročilo,
celotno poročilo na dLib.si
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Zaključno poročilo,
celotno poročilo na dLib.si