Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 Oznaka poročila: ARRS_ZV_RPROG_ZP_2008/575 ZAKLJUČNO POROČILO O REZULTATIH RAZISKOVALNEGA PROGRAMA V OBDOBJU 2004-2008 A. PODATKI O RAZISKOVALNEM PROGRAMU 1. Osnovni podatki o raziskovalnem programu Šifra programa P1-0297 Naslov programa Teorija grafov Vodja programa 1931 Bojan Mohar Obseg raziskovalnih ur 18.700 Cenovni razred B Trajanje programa 01.2004 - 12.2008 Izvajalke programa (raziskovalne organizacije in/ali koncesionarji) 101 Inštitut za matematiko, fiziko in mehaniko B. REZULTATI IN DOSEŽKI RAZISKOVALNEGA PROGRAMA 2. Poročilo o realizaciji programa raziskovalnega programa1 V programu smo si za cilj zadali raziskave na naslednjih področjih: topološka teorija grafov, grafi na ploskvah, vložitve; barvanja grafov, povsod neničelni pretoki, snarki; strukturna teorija grafov, grafovski minorji; grafovski produkti, njihove invariante in sorodne problemi; medianski grafi s poudarkom na problemu prepoznavanja; kemijska teorija grafov in izračunavanje različnih topoloških invariant; razvoj hitrih algoritmov za prepoznavanje pomembnih razredov grafov; problemi v zvezi s posplošitvami klasičnega problema hanojskih stolpov. V obdobju 2004 - april 2008 smo na vseh zastavljenih področjih dosegli pomemben napredek in objavili 209 člankov. Na kratko seveda ni možno opisati vseh dosežkov, zato opišimo samo najpomembješe in najbolj značilne. S področja topološke teorije grafov in grafov na ploskvah smo dosegli številne globoke rezultate, navedimo dva članka, ki sodita med najpomembnejše dosežke skupine s tega področja. Članek (S. Cabello, B. Mohar, Finding shortest non-separating and non-contractible cycles for topologically embedded graphs, Discrete & Computational Geometry 37 (2007) 213-235), je naredil fundamentalen prispevek k algoritmičnim pristopom k razdaljam v vloženih grafih in je v kratkem času že nabral 8 čistih citatov. V članku (Z. Dvorak, R. Škrekovski, A theorem about a contractible and light edge, SIAM Journal on Discrete Mathematics 20 (2006) 55-61) pa je dokazano, da vsak 3-povezan ravninski graf, ki ni K_4, vsebuje povezavo, ki je hkrati skrčljiva in lahka. Posledica izreka je, da lahko vsak 3-politop konstruiramo iz tetraedra z zaporednim razcepljanjem vozlišč stopnje največ 11. Rezultat tega članka tako hkrati posploši Kotzigovega rezultata iz leta 1955 (A. Kotzig, Math. Slovaca 5 (1955) 111-113), ki pravi, da vsak ravninski 3-povezan graf vsebuje povezavo, tako da je vsota stopenj njenih krajišč kvečjemu 13 (taka povezavi pravimo, da je lahka) in Tutteov izrek iz leta 1961 (W. T. Tutte, Indag. Math. 23 (1961) 441-455), ki trdi, da vsak 3-povezan graf, ki ni K_4, vsebuje skrčljivo povezavo. Ta rezultat je zanimiv tudi z vidika optimizacije in geometrije. Pri raziskavah v zvezi z minorji grafov smo dokončali članek (T.Bohme, K-I. Kawarabayashi, J. Program P1-0297 Stran 1 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 Maharry, B. Mohar, Linear connectivity forces large complete bipartite minors, J. Combin. Theory Ser. B 99 (2009) 557–582) o linearni aproksimaciji Hadwigerjeve domneve za velike grafe. Članek je že dosegel visoko odmevnost. V nadaljevanju dela na tem področju smo odprli nekatere nove probleme in našli prve delne rezultate, ki veliko obetajo. Zelo veliko dela je bilo opravljenega na področju barvanj grafov, še posebej v povezavi s topološko teorijo. Zelo intenzivno smo delali na področju poligonalnih ploskev, kjer smo uspeli rešiti Higuchijevo domnevo. Razlikovalno število grafa je pomembna grafovska invarianta s področja barvanja grafov, ki je bila intenzivno raziskovana v zadnjih letih. V dveh člankih, ki sta bila oba objavljena v vrhunskih revijah s področja algebre in teorije grafov (J. Algebra in J. Graph Theory), je bil narejen preboj na tem področju. Med drugim je bila dokazana splošna zgornja meja Brooksovega tipa za to invarianto ter določeno razlikovalno število za vse kartezične potence grafov. S slednjim je bila med drugim razrešena domneva, ki jo je postavil M. Albertson. S področja barvanja grafov moramo posebej omeniti delo (Ken-Ichi Kawarabayashi, B. Mohar, Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs), ki je bilo predstavljeno na prestižni konferenci ACM Symposium on Theory of Computing (Proc. 38th Ann. ACM Symp. on Theory of Computing, Seattle, Washington, USA, May 21-23, 2006, ACM Press, 2006, pp. 401-416). Na tem srečanju izberejo le okrog 80 prispevkov iz teoretičnega računalništva, ki predstavljajo vrhunec raziskovalnih dosežkov na tem področju v tekočem letu. Naš najnovejši rezultat iz teorije algoritmov je linearni algoritem za izomorfizem poliedrskih grafov omejenega roda, ki predstavlja prvo pomembno posplošitev 35 let starega algoritma Hopcrofta in Wanga za ravninske grafe. Ker je izomorfizem grafov eden od fundamentalnih problemov, katerih algoritmična zahtevnost je še široko odprta, in ker prinaša enega od redkih prebojev na tem področju, je bil ta rezultat sprejet na prestižni konferenci STOC'08. Na področju povsod neničelnih pretokov in snarkov smo objavili dva pomembna članka. V prispevku (P. Potočnik, M. Škoviera, R. Skrekovski, Nowhere-zero 3-flows in abelian Cayley graphs, Discrete Mathematics 297 (2005) 119-127) je natančno določeno, kateri Cayleyevi grafi abelovih grup dopuščajo povsod neničelne 3-pretoke. V posebnem vsi taki grafi stopnje vsak 4 dopuščajo povsod neničelne 3-pretoke. Leta 1969 je B. Grunbaum postavil domnevo, da lahko povezave vsake triangulacija orientabilne ploskve pobarvamo s tremi barvami tako, da je vsako lice incidentno z vsemi tremi barvami. Ta atraktivna domneva je posplošitev izreka štirih barv in še vedno ostaja odprta. V članku (B. Mohar, A. Vodopivec, On polyhedral embeddings of cubic graphs, Combin. Probab. Comp. 15 (2006) 877-893) je pokazano, da različne družine snarkov, it is shown that various families of snarkov, kubičnih grafov brez mostov s kromatičnim indeksom štiri, nimajo poliedrske vložitve v orientabilne ploskve, s čimer je podana nova podpora Grunbaumovi domnevi. V članku je tudi dokazano, da domneva velja za vse kubične grafe z manj kot 30 vozlišči. Na področju medianskih in sorodnih razredov grafov ter splošneje metrične teorije grafov, smo največ pozornosti povečali delnim kockam, ki so osrednji razred teorije in med drugim vključujejo medianske grafe. Dokazali smo, da lahko vsak spoj dveh grafov dobimo kot križni graf delne kocke, ki ni kartezični produkt dveh netrivialnih delnih kock. Po drugi strani je spoj dveh grafov križni graf medianskega grafa natanko tedaj, ko je le-ta kartezični produkt dveh medianskih grafov, katerih križna grafa sta prvotna grafa. Delne kocke smo obravnavali tudi s pomočjo vložitev v ravnino, ki jih je nakazal dual baricentrične subdivizije polnega grafa na štirih točkah. S pomočjo tega smo na nov način lahko karakterizirali Platonske grafe. Našli smo tudi nekaj novih primerov regularnih osnovnih delnih kock. V vseh nam znanih primerih so regularne delne kocke tudi kritične za odvzemanje povezav. Po povezavah kritične delne kocke smo zato raziskovali natančneje. Pokazali smo tudi, da so povezani, dvodelni, zunanje ravninski grafi delne kocke in našli vložitev takšnega grafa v hiperkocko. V daljšem članku smo razvili tudi teorijo plemen delnih kock in z njeno pomočjo našli veliko primerov kubičnih delnih kock in s tem naredili precejšen preboj na tem področju. Drevesa so poseben razred medianski grafov. Ringel-Kotzigova domneva o t.i. gracilnih označitvah dreves sodi med najbolj znane in raziskovane probleme moderne kombinatorike. Domneva trdi, da v vsakem drevesu lahko točke označimo z različnimi oznakami naravnih števil od 1 do n tako, da so oznake na povezavah, ki jih dobimo kot absolutno vrednost razlike oznak na njenih krajiščih, paroma različne. Analogen označitveni problem smo obravnavali na splošnejšem razredu grafov, na delnih kockah, kjer zahtevamo enakost porojenih oznak na Program P1-0297 Stran 2 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 povezavah iz istega Theta-razreda in za poljubni povezavi iz različnih Theta razredov različni porojeni oznaki. Domnevo smo dokazali za sode cikle, Fibonaccijeve kocke in nekaj drugih razredov delnih kock. Pokazali smo tudi, da kartezični produkt delnih kock ohranja njuno Theta-gracilnost. Iz obravnave medianskih grafov izdvojimo članek (B. Brešar, S. Klavžar, R. Škrekovski, Roots of cube polynomials of median graphs, J. Graph Theory 52 (2006) 37-50), ki predstavlja nadaljevanje naše obravnave polinoma kock na medianskih grafih. V tem prispevku ugotovimo, da iz ničel polinoma kock lahko razberemo mnogo lastnosti medianskih grafov. Med glavne rezultate sodita karakterizacija grafov acikličnih kubnih kompleksov znotraj medianskih grafov ter karakterizacija kartezičnih produktov dreves. V kemijski teoriji grafov smo izpeljali vrsto lastnosti za družino invariant Wienerjevega tipa in karakterizirali resonančne grafe katakondenziranih heksagonalnih grafov. Poiskali smo preprosto metodo binarnega kodiranje 1-faktorjev katakondenziranih benzenoidnih grafov, ki temelji na Randićevem številu šestkotnikov. Obravnavali smo neskončno družino invariant Wienerjevega tipa in povezavo med povprečno razdaljo grafa ter izometrično kanonično reprezentacijo grafa. Članek (S. Klavžar, On the canonical metric representation, average distance, and partial Hamming graphs, European J. Combin. 27 (2006) 68-73) predstavlja kulminacijo desetletnega dela na področju metrične teorije grafov in Wienerjevega indeksa, saj glavni rezultat pokriva (in razširja) jedro celotne teorije. Na področju grafovskih invariant smo za zgornje dominantno število kartezičnega in direktnega produkta grafov v obeh primerih pokazali neenakost Vizingovega tipa, to je, zgornje dominatno število produkta dveh grafov ni manjše od produkta zgornjih dominantnih števil obeh faktorjev. Za parno-dominatno število kartezičnega produkta grafov smo pokazali podobne spodnje meje kot so znane za dominantno število kartezičnega produkta. Po drugi strani smo pokazali, da se parno dominatno število direktnega produkta obnaša povsem drugače, saj je produkt parnih-dominantnih števil dveh grafov zgornja meja za parno dominatno število njunega direktnega produkta. Podoben rezultat smo pokazali tudi za dominantno število direktnega produkta, namreč, da je le-to navzgor omejeno s trikratnikom produkta dominantnih števil obeh faktorjev. Izpeljali smo meje za optimalno L(2,1) označitev krepkih produktov ciklov ter določili optimalne L(2,1) označitve nekaterih družin krepkih produktov ciklov. V skoraj 40 strani dolgem članku (P. Bella, D. Kral, B. Mohar, K. Quitterova, Labeling planar graphs with a condition at distance two, European J. Combin. 28 (2007) 2201-2239) je dokazana slavna delta-kvadrat domneva za L(2,1)-označitve za vse ravninske grafe z maksimalno stopnjo različno od 3. To predstavlja enega najmočnejših rezultatov, ki podpirajo domnevo. Na področju grafovskih produktov smo nadaljevali z raziskavami invariant, še posebej v povezavi z znamenito Vizingovo domnevo o dominantnem številu kartezičnega produkta grafov. Rezultat teh raziskav je članek (B. Brešar, M. A. Henning, S. Klavžar, On integer domination in graphs and Vizing-like problems, Taiwanese Journal of Mathematics 10 (2006) 1317-1328), v katerem smo študirali razširitev omenjenega problema na celoštevilsko dominantno število. Uspelo nam je posplošiti rezultat, ki sta ga leta 2000 dokazala Clark in Suen za običajno dominantno število produkta dveh grafov. Na področju grafovskih algoritmov smo razvili skoraj linearen algoritem za poseben razred skoraj-medianskih grafov in linearen algoritem za kartezično faktorizacijo. Slednji algoritem je vrhunec raziskav, ki so se začele leta 1985, ko je bil predstavljen prvi polinomski algoritem za ta problem. Izpeljan je bil tudi algoritem za učinkovito prepoznavanje resonančnih grafov katakondenziranih heksagonalnih grafov. Razvili pa smo tudi hiter algoritem za prepoznavanje Fibonacciejvih kock (A. Taranenko, A. Vesel, Fast recognition of Fibonacci cubes, Algorithmica 49 (2007) 81-93). Na področju teorije Hanojskih stolpov smo teorijo na različne načine prepletli z drugimi področji matematike. V daljšem članku (A.M. Hinz, S. Klavžar, U. Milutinović, D. Parisse, C. Petr, Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence, European J. Combin. 26 (2005) 693-708) smo to teorijo povezali z metrično teorijo grafov, v članku (S. Klavžar, B. Mohar, Crossing numbers of Sierpinski-like graphs, J. Graph Theory 50 (2005) 186-198) s topološko teorijo grafov in v članku (S. Klavžar, U. Milutinović, C. Petr, Hanoi graphs and some classical numbers, Expo. Math. 23 (2005) 371-378) s klasično kombinatoriko. Nazadnje smo v članku (S. Klavžar, U. Milutinović, C. Petr, Stern polynomials 39 (2007) 86-95), ki smo ga objavili v prestižni reviji Advances in Applied Mathematics, vpeljali nov razred polinomov, ki se na naraven način pojavi znotraj teorije. Program P1-0297 Stran 3 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 3. Ocena stopnje realizacije zastavljenih raziskovalnih ciljev2 Cilji programa so bili v celoti realizirani. 4. Utemeljitev morebitnih sprememb programa raziskovalnega programa3 5. Najpomembnejši znanstveni rezultati programske skupine4 Znanstveni rezultat 1. Naslov SLO Teme iz teorije grafov : grafi in njihov kartezični produkt ANG Topics in graph theory : graphs and their Cartesian product Opis SLO V letu 2008 smo pri uglednem založniku matematičnih knjig A K Peters izdali znanstveno monografijo, ki pokriva teme iz sodebne teorije grafov. Rdeča nit, ki med seboj povezuje izbrane teme, je kartezični produkt grafov. ANG In 2008 we have published a scientific monograph with a respectable published of mathematical book A K Peters. The book covers topics from modern graph theory, where the topics are interconnected via the Cartesian product operation. Objavljeno v IMRICH, Wilfried, KLAVŽAR, Sandi, RALL, Douglas F.. Topics in graph theory : graphs and their Cartesian product. Wellesley: A K Peters, cop. 2008. XIV, 205 str., graf. prikazi. ISBN 978-1-56881-429-2. Tipologija 2.01 Znanstvena monografija COBISS.SI-ID 223132416 2. Naslov SLO Analogija Descartes-Eulerjeve formule za neskončne grafe in Higuchijeva domneva ANG An analogue of the Descartes-Euler formula for infinite graphs and Higuchi's conjecture Opis SLO V članku je dobljena posplošitev Descartesovega izreka na poljubne, tudi nekompaktne poliedrske ploskve. Če so vsi poligoni, ki sestavljajo ploskev, pravilni mnogokotniki, pridemo do pojma kombinatorične ukrivljenosti. Dokazano je, da je v primeru povsem pozitivne kombinatorične ukrivljenosti prostor kompakten in ima z izjemo štirih neskončnih družin kvečjemu 3444 vozlišč. Ta rezultat ima za posledico tudi potrditev domneve, ki jo je pred nekaj leti postavil Higuchi. ANG For a polzhedral surface S obtained from a (possibly infinite) collection of polygons, we prove that under a certain condition, S is homeomorphic to a compact 2-manifold with t points removed. In the special case when every polygon is regular and the Gaussian curvature is positive at each vertex, we apply our main theorem to deduce that R is compact and is homeomorphic to either the sphere or to the projective plane. With exception of four infinite families, |V| < 3445. This resolves a recent conjecture of Higuchi. Objavljeno v DEVOS, Matt, MOHAR, Bojan. An analogue of the Descartes-Euler formula for infinite graphs and Higuchi's conjecture. Trans. Am. Math. Soc, 2007, vol. 359, no. 7, str. 3287-3300. JCR IF: 0.824, SE (42/207), mathematics Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 14334809 3. Naslov SLO Barvno-pretočna dualnost vloženih grafov ANG Coloring-flow duality of embedded graphs Opis SLO V letu 2005 je v prestižni reviji Transactions of the American Mathematical Society naš daljši članek, v katerem je objavljen pomemben nov rezultat o skoraj dualnosti med krožnimi pretoki in krožnimi barvanji grafov na ploskvah. S tem je dosežen vrh raziskav mnogih avtorjev in so razjasnjeni in posplošeni mnogi rezultati, ki so bili doslej dobljeni z drugačnimi metodami. In 2005 we published a paper in a prestige journal Transactions of the American Mathematical Society. The paper brings important new results Program P1-0297 Stran 4 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 ANG about an almost duality between circular flows and circular colorings of graphs on surfaces. This presents culmination of the research of many authors and clarifies and generalizes many results previously obtained by other methods. Objavljeno v DEVOS, Matt, GODDYN, Luis, MOHAR, Bojan, VERTIGAN, Dirk, ZHU, Xuding. Coloring-flow duality of embedded graphs. Trans. Am. Math. Soc, 2005, vol. 357, no. 10, str. 3993-4016. JCR IF: 0.827, SE (32/181), mathematics Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 13781081 4. Naslov SLO Krožni kromatični indeks grafov velikega obsega ANG The circular chromatic index of graphs of high girth Opis SLO Krožno kromatično število in krožni kromatični indeks predstavljata eno najpomembnejših raziskovalnih področij aktualne teorije barvanja grafov. V tem članku je dokazan fundamentalen izrek, ki trdi, da za vsak epsilon > 0 in za vsako naravno število delta > 0 obstaja število g, za katero velja, da je za vsak graf G z maksimalno stopnjo delta in najkrajšim ciklom dolžine vsaj g, krožni kromatični indeks grafa G kvečjemu delta + epsilon. ANG Circular chromatic number and circular chromatic index present one of the most important research areas in the contemporary theory of graph colorings. In this paper a fundamental theorem is proved asserting that for each epsilon > 0 and each integer delta > 0, there exists a number g such that for any graph G of maximum degree delta and girth at least g, the circular chromatic index of G is at most delta + epsilon. Objavljeno v KAISER, Tomáš, KRÁL', Daniel, ŠKREKOVSKI, Riste, ZHU, Xuding. The circular chromatic index of graphs of high girth. J. comb. theory, Ser. B, 2007, vol. 97, no. 1, str. 1-13. JCR IF: 1.017, SE (25/207), mathematics Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 14187353 5. Naslov SLO Razlikovalne označitve delovanja grup na vektorskih prostorih in grafih ANG Distinguishing labellings of group action on vector spaces and graphs Opis SLO Razlikovalno število grafa je pomembna grafovska invarianta, ki je bila intenzivno raziskovana v zadnjih letih. V skupini smo objavili več člankov na to temo in to v vrhunskih revijah J. Algebra, J. Graph Theory in European J. Combin. Eksplicitno omenjeni članek je v kratkem času po viru MatcSciNet zbral že 9 citatov, kar je za metamatično raziskovalno okolje zelo veliko. ANG The distinguishing number of a graph is an important graph invariant which was intensively studied in last years. We have published several papers on the topic in top journals J. Algebra, J. Graph Theory and European J. Combin. The explicitly mentioned paper has in the short period after its publication collected 9 citation according to the database MatcSciNet, which is a very big number for mathematical research. Objavljeno v KLAVŽAR, Sandi, WONG, Tsai-Lien, ZHU, Xuding. Distinguishing labellings of group action on vector spaces and graphs. J. algebra, 2006, vol. 303, iss. 2, str. 626-641. JCR IF: 0.568, SE (77/186), mathematics Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 14075225 6. Najpomembnejši družbeno-ekonomsko relevantni rezultati programske skupine5 Družbeno-ekonomsko relevantni rezultat Naslov SLO Zoisovo nagrado za vrhunske znanstvene in razvojne dosežke na področju matematike ANG Zois award for highest scientific achievements in the field of mathematics Opis SLO Sandi Klavžar je prejel Zoisovo nagrado za leto 2007 za vrhunske znanstvene in razvojne dosežke na področju matematike. ANG Sandi Klavžar received Zois award for 2007 for highest scientific achievements in the field of mathematics. Šifra E.01 Domače nagrade Program P1-0297 Stran 5 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 Objavljeno v BRATKO, Ivan, KLAVŽAR, Sandi. Zoisovi nagrajenci : TV Pika, oddaja Sadovi znanja, 21. 12. 2007. Ljubljana, 2007. Tipologija 2.19 Radijska ali televizijska oddaja COBISS.SI-ID 14628697 2. Naslov SLO ANG Organiziranje znanstvenih srečanj Organization of scientific meetings Opis SLO ANG S. Klavžar in B. Mohar sta bila soorganizatorja 21st LL-Seminar on Graph Theory, 2004, Avstrija, in 6th Slovenian Conference on Graph Theory, Bled, 2007. S. Klavžar je bil soorganizator 22nd LL-Seminar, Leipzig, 2005 in Workshop on the Tower of Hanoi, Maribor, 2005, minisimpozij na SIAM Conference on Discrete Mathematics, Kanada, 2006. B. Mohar je organiziral Topological Graph Theory and Crossing Numbers, Kanada, 2006, "CanaDAM 2007", Kanada; "Workshop on the Cycle Double Cover Conjecture", UBC, 2007; "Infinite Graphs", BIRS, 2007; Graph Minors, Banff, 2008. We have organized many internatinal scientific meetings: 21st LL-Seminar on Graph Theory, 2004, Avstrija; 6th Slovenian International Conference on Graph Theory, Bled, 2007; 22nd LL-Seminar on Graph Theory, Leipzig, 2005; Workshop on the Tower of Hanoi, 2005; a mini symposium at the Siam Conference on Discrete Mathematics, Canada, 2006; Topological Graph Theory and Crossing Numbers, Banff, 2006, CanaDAM 2007, Canada 2007; Workshop on the Cycle Double Cover Conjecture, UBC, 2007; Infinite Graphs, BIRS, 2007; "Graph Minors", Banff, 2008. Šifra B.01 Organizator znanstvenega srečanja Objavljeno v spletne strani konferenc, zborniki povzetkov konferenc Tipologija 1.24 Bibliografija, kazalo ipd. COBISS.SI-ID 14110297 3. Naslov SLO ANG Vabljena predavanja Invited lectures Opis SLO ANG V letih od 2004-2008 je bil Bojan Mohar vabljeni plenarni predavatelj na 22 mednarodnih konferencah. Sandi Klavžar je bil vabljeni plenarni predavatelj na petih konferencah. From 2004 to 2008 Bojan Mohar was an invited plenary speaker on 22 international conferences, and Sandi Klavžar was an invited plenary speaker at five conferences. Šifra B.04 Vabljeno predavanje Objavljeno v spletne strani konferenc, zborniki povzetkov konferenc Tipologija 1.24 Bibliografija, kazalo ipd. COBISS.SI-ID 14763609 4. Naslov SLO ANG Uredniško delo Editorial work Opis SLO ANG Bojan Mohar urednik ali član uredniških odborov pri revijah Journal of Graph Theory, Discrete Mathematics, Journal of Combinatorial Theory Series B, Linear and Multilinear Algebra, MATCH Communications in Mathematical and in Computer Chemistry, Ars Mathematica Contemporanea. Sandi Klavžar je član uredniških odborov revij European Journal of Combinatorics, MATCH Communications in Mathematical and in Computer Chemistry, Discussiones Mathematicae Graph Theory, Asian-European Journal of Mathematics, Ars Mathematica Contemporanea. Bojan Mohar editor or member of editorial boards in Journal of Graph Theory, Discrete Mathematics, Journal of Combinatorial Theory Series B, Linear and Multilinear Algebra, MATCH Communications in Mathematical and Computer Chemistry, Ars Mathematica Contemporanea. Sandi Klavžar is a member of editorial boards of European Journal of Combinatorics, MATCH Communications in Mathematical and Computer Chemistry, Discussiones Mathematicae Graph Theory, Asian-European Journal of Mathematics, Ars Mathematica Contemporanea. Šifra C.04 Uredništvo mednarodne revije Program P1-0297 Stran 6 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 Objavljeno v spletne strani revij, na platnicah revij Tipologija 1.24 Bibliografija, kazalo ipd. COBISS.SI-ID 25427968 5. Naslov SLO Mentorstvo pri disertacijah ANG Ph.D. Supervisions Opis SLO Člani skupine so bili v obdobju med 2004 in 2008 mentorji pri naslednjih podoktorskih projektih in doktorskih disertacijah: Sergio Justo Cabello, Marie Curie Postdoctoral Fellowship, 5. okvirni program EU (2004-2006); PETR, Ciril, 2004; PETERIN, Iztok, 2005; POVH, Janez, 2006; BOKAL, Drago, 2006; VODOPIVEC, Andrej, 2007; ŠPACAPAN, Simon, 2007; KOVŠE, Matjaž, 2008; JEREBIC, Janja, 2008. ANG Between 2004 and 2008 we have supervised the following postdoc projects and Ph.D.'s: Sergio Justo Cabello, Marie Curie Postdoctoral Fellowship, Fifth Framework EU (2004-2006); PETR, Ciril, 2004; PETERIN, Iztok, 2005; POVH, Janez, 2006; BOKAL, Drago, 2006; VODOPIVEC, Andrej, 2007; ŠPACAPAN, Simon, 2007; KOVŠE, Matjaž, 2008; JEREBIC, Janja, 2008. Šifra D. 10 Pedagoško delo Objavljeno v disertacijah Tipologija 2.08 Doktorska disertacija COBISS.SI-ID 13020761 7. Pomen raziskovalnih rezultatov programske skupine6 7.1. Pomen za razvoj znanosti7 SLO 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). Program P1-0297 Stran 7 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 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. ANG_____________________________________________________________________________________________________________ The project belongs to basic research from the area of mathematics. Problems that we will work on are internationally important, which can in particular be justified with our bibliography from the last period as well as with the (citation) impact of our results. The problems are central in the area of graph theory. We expect that the newly obtained results will be published in established international journals and we will present them at international scientific conferences. For the next period we expect that we will be invited to deliver several invited plenary talks which will further emphasize the importance of ourresearch achievements. In this way we will further increase the role of the Slovenian graph theory school. The results are mainly theoretical with potential to be applicable in information technologies. Our previous contacts with industry include Hermes Softlab and Iskratel. The research programme is oriented such that it enables to integrate the most promising young researchers. In this way it enables a long-term continuation of the quality research in mathematics which has in turn a positive influence on the quality of the university programs in mathematics. Since mathematics is used in many other areas, the quality of research in mathematics has an indirect but imporatant influence on the development of other disciplines as well. Inside mathematics the programme mostly developes graph theory and keeps and strenthens its world level. There is a strong international cooperation through bilateral projects and many research visits. In the last years we had the following international projects: 1. Cooperation with ALCOM (Pierre Rosenstiehl, France). 2. Cooperation with Hungarian Academy of Sciences. 3. Cooperation within European network DIMANET for discrete mathematics. 4. SLO-USA projects on graph minors (Neil Robertson, John Maharry, Ohio State University, USA). 5. Several bilateral projects with Austria (University of Leoben). 6. Several PROTEUS projects with IMAG, Grenoble, France (Sylvain Gravier and Michel Mollard). 7. SLO-DE project with the Technical University Ilmenau, Germany (Thomas Bohme and Michael Stiebitz). Every four years we organize an important international conference in graph theory (Slovenian Graph Theory Conference) with 100-200 participants from all over the world. 7.2. Pomen za razvoj Slovenije5 SLO____________________________________________________________________________________________________________ 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. ANG Program P1-0297 Stran 8 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 Reserach of this program group is basic but the methods can be applied to optimization, network designs, control of production processes. Our expertise has led to a cooperation with the Slovenian industry from the technological development, mostly in the information and telecommunication technology. In the last period we have successfully cooperated in the projects Models and algorithms for employee scheduling (project ordered by HIT d.d., Nova Gorica), Algorithms for developing a model of working process (project ordered by ICIT, d.o.o., Šempeter pri Gorici), Optimal distribution among fuel stations (project ordered be Ultra d.o.o., Zagorje ob Savi), The application of the Q factor (SAIDI and SAIFI) in the methodology of determining distribution charges for power transmission and distribution grid (the project is done in collaboration with the institute Milan Vidmar), Graphs and telecommunication networks (IMFM and ISKRATEL, telekomunikacijski sistemi, d.o.o.), Graph minors, graphs on surfaces and networks (IMFM and Hermes Softlab Programska Oprema). 8. Zaključena mentorstva članov programske skupine pri vzgoji kadrov9 Vrsta izobraževanja Število mentorstev Od tega mladih raziskovalcev - magisteriji 11 - doktorati 8 3 - specializacije Skupaj: 19 3 9. Zaposlitev vzgojenih kadrov po usposabljanju Organizacija zaposlitve Število doktorjev Število magistrov Število specializantov - univerze in javni raziskovalni zavodi 7 7 - gospodarstvo 1 - javna uprava 4 - drugo Skupaj: 8 11 0 10. Opravljeno uredniško delo, delo na informacijskih bazah, zbirkah in korpusih v obdobju10 Ime oz. naslov publikacije, podatkovne informacijske baze, korpusa, zbirke z virom (ID, spletna stran) Število * 1. Math. Reviews http://www.ams.org/mathscinet/ 46 2. Journal of Graph Theory http://www3.interscience.wiley.com/journal/35334/home 163 3. Discrete Mathematics http://www.sciencedirect.com/science/journal/0012365X 30 4. Linear and Multilinear Algebra http://www.informa world. com/smpp/title~content=t713644116 10 5. Zentralblatt MATH http://www.zblmath.fiz-karlsruhe.de/MATH/home 7 6. 7. 8. Program P1-0297 Stran 9 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 9. 10. *Število urejenih prispevkov (člankov) /število sodelavcev na zbirki oz. bazi /povečanje obsega oz. število vnosov v zbirko oz. bazo v obdobju 11. Vključenost raziskovalcev iz podjetij in gostovanje raziskovalcev, podoktorandov ter študentov iz tujine, daljše od enega meseca Sodelovanje v programski skupini Število - raziskovalci-razvijalci iz podjetij 1 - uveljavljeni raziskovalci iz tujine 3 - podoktorandi iz tujine 2 - študenti, doktorandi iz tujine 1 Skupaj: 7 12. Vključevanje v raziskovalne programe Evropske unije in v druge mednarodne raziskovalne in razvojne programe ter drugo mednarodno sodelovanje v obravnavanem obdobju11_______________________________________________________________________________ BI-PL/04-05-007: Grafovske invariante in produkti grafov (vodja Sandi Klavžar) BI-FR/04-002: Grafi in kode (vodja Sandi Klavžar) BI-US 04-05/36: Minorji grafov in grafi na ploskvah (vodja Bojan Mohar) BI-SK/05-07-001: Neizogibne konfiguracije v vloženih grafih (vodja Bojan Mohar) BI-US/06-07-004: Grafi kartezičnih produktov in grafovske invariante (vodja Sandi Klavžar) BI-IN/06-07-002: Metrična teorija grafov in aplikacije (vodja Sandi Klavžar) BI-CZ/06-07-015: Barvanja grafov in njihova uporaba pri dodeljevanju frekvenc (vodja Riste Škrekovski) BI-HU/06-07-004: Semidefinitno programiranje z uporabo (vodja Martin Juvan) BI-AT/07-08-011: Kartezični produkti grafov in razlikovalno število (vodja Sandi Klavžar) BI-FR/08-09-Proteus-002: Grayeve kode, sorodni razredi grafov in delne kocke (vodja Sandi Klavžar) Drago Bokal je bil 9 mesecev na Simon Fraser University, Kanada. Andrej Vodopivec je bil 9 mesecev na Simon Fraser University, Kanada. Drago Bokal je bil 3 mesece na Universität Paderborn, Nemčija. Andrej Vodopivec je bil 2 meseca na Universität Paderborn, Nemčija. Drago Bokal je imel enoletni podoktorski projekt na University of Waterloo, Kanada. Riste Škrekovski je preživel 3 mesece na Karlovi univerzi v Pragi. Gašper Fijavž je bil več mesecev v Nemčiji s podporo Humboldtove štipendije. Simon Špacapan je bil 6 mesecev na Simon Fraser University, Kanada. 13. Vključenost v projekte za uporabnike, ki potekajo izven financiranja ARRS12 Modeli in algoritmi za razporejanje zaposlenih projekt za naročnika HIT d.d., Nova Gorica. Projekt obravnava problem razporejanja zaposlenih z metodami lokalne optimizacije. Podatki problema sestojijo iz množice zaposlenih in množice delovnih zahtev - izmen. Vsaki delovni zahtevi je treba zadostiti - zagotoviti zadostno število delavcev z ustreznimi znanji. Cilj je poiskati razpored delavcev v izmene, ki je za zaposlene in delodajalce čim ugodnejši. Razvit je model za problem razporejanja zaposlenih ter namenski algoritmi za reševanje tega problema. Le-ti vključujejo lokalno vzpenjanje, iskanje brez vračanja in simulirano ohlajanje. Predlagane so hevristike, ki naj bi izboljšale učinkovitost optimizacijskega postopka, in metode, ki pomagajo pri razvoju samega algoritma. Algoritmi so implementriani kot ActiveX modul, ki omogoča neposredno izmenjavo podatkov z gostiteljsko aplikacijo ter shranjevanje in branje podatkov iz XML datotek. Izvajanje algoritmov je mogoče prilagoditi posamezni naročnikovi stranki s pomočjo namenske krmilne skripte. Modularna zasnova komponente omogoča preprosto dopolnjevanje z novimi namenskimi omejitvami oz. prilagajanje obstoječih omejitev v problemu. Algoritmi za izdelavo modela delovnega procesa projekt za naročnika ICIT, d.o.o., Šempeter pri Gorici Program P1-0297 Stran 10 od Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 Pri projektu obravnavamo problem izdelave delovnega procesa. Podatke problema sestavljata skupina agentov, ki v delovnem procesu delujejo, in množica delovnih nalog, ki jih je potrebno v sklopu delovnega procesa opraviti. Delovne naloge so lahko opisane ali posamično ali pa kot družina istovrstnih delovnih nalog, ki jih je potrebno opravljati z zadostno frekvenco. Cilj je poiskati model delovnega procesa, ki opravi vse predpisane delovne naloge in čimbolj ustreza vnaprej predpisanim kriterijem. Vsako od delovnih nalog, ki morda še ni časovno determinirana, je potrebno umestiti v čas, poleg tega pa je potrebno zaporedja časovno združljivih delovnih nalog sestaviti v izmene sodelujočih agentov. Problem izdelave delovnega procesa formaliziramo in izdelamo algoritme za reševanje problema. Razviti algoritmi so implementriani v ActiveX komponenti, ki omogoča neposredno izmenjavo podatkov z gostiteljsko aplikacijo oz. shranjevanje ter branje podatkov iz XML datotek. Algoritmi so implementirani tako, da omogočajo prilagajanje izvajanja posamezni naročnikovi stranki s pomočjo namenske krmilne skripte. Optimalni razvoz po bencinskih servisih projekt za naročnika Ultra d.o.o., Zagorje ob Savi. Izdelan je matematični model optimiranja stroškov poslovanja bencinskega servisa. Izhodiščem, ki predstavijo način poslovanja ter strukturo stroškov, sledi formalna predstavitev entitet, ki v problemu nastopajo, njihovih atributov ter pogojev, ki morajo veljati. Predstavljene so formule za izračun stroškov ter izračunana optimalna doba dobave za primer enakomerne porabe na bencinskem servisu. Sledi predlog algoritma za izračun načrta dobav ter več metod določanja optimalne dobavne dobe v primeru neenakomerne dobave. V zvezi s predlaganimi izboljšavami najdenih rešitev z lokalno optimizacijo je podana definicija okolice dane rešitve. Razviti algoritmi so implementirani kot samostojen program, ki z gostiteljsko aplikacijo podatke izmenjuje s pomočjo namenskega narečja XML jezika. Uporaba faktorja Q (SAIDI in SAIFI) v metodologiji določanja omrežnine za prenosno in distribucijsko omrežje. Projekt v sodelovanju z Elektroinštitutom Milan Vidmar za potrebe slovenskih elektrodistribucijskih podjetij. Kakovost električne energije je v novejšem času zelo pomemben dejavnik, ki postaja merilo za učinkovitost in uspešnost poslovanja distribucijskih podjetij. Področje kakovosti napajanja odjemalcev z EE delimo na kakovost storitev, stalnost dobave in kakovost napetosti. Tu je obdelano področje stalnosti dobave pri čemer je izhodišče bilo pregled stanja na tem področju doma in v svetu. Kot merilo za spremljanje stalnosti dobave sta izbrana dva kazalca zanesljivosti in sicer SAIFI in SAIDI, katerih uporaba pri vrednotenju omrežnine v distribucijskem EE sistemu je tudi obdelana. Predlagane so tri metode: metoda razredov kakovosti, metoda zvezne funkcije in metoda kosoma linearne funkcije. Z uporabo v praksi bodo preverjene prednosti in slabosti posameznih metod glede na stanje v slovenskem DEES. Tako bodo opredeljeni realnejši pogoji za izbiro najprimernejše metode. Upoštevane so vrednosti posameznih investicij in njihovi učinki na izboljšanje kazalcev zanesljivosti. Pri opredeljevanju ukrepov je izbrana pot v nasprotni smeri, ker je najprej opredeljeno potrebno izboljšanje kazalcev zanesljivosti na nivoju izvoda in so šele na tej podlagi opredeljeni ukrepi na nivoju izvodov potrebni za doseganje zastavljenega cilja. Člani projektne skupine za algoritme na grafih in kombinatorično optimizacijo so razvili več matematičnih modelov za vrednotenje kakovosti glede na vrednost faktorjev SAIDI in SAIFI ter izdelali primerjalno študijo izdelanih modelov. Člani programa so bili vključeni tudi v naslednja raziskovalna aplikativna projekta: - Grafi in telekomunikacijska omrežja (L1-5168-0101-05, IMFM in ISKRATEL, telekomunikacijski sistemi, d.o.o.) - Grafovski minorji, grafi na ploskvah in omrežja (L1-5014-0101-04, IMFM in Hermes Softlab Programska Oprema) 14. Dolgoročna sodelovanja z uporabniki, sodelovanje v povezavah gospodarskih in drugih organizacij (grozdi, mreže, platforme), sodelovanje članov programske skupine v pomembnih gospodarskih in državnih telesih (upravni odbori, svetovalna telesa, fundacije, itd.)________________________________________________________________________________________ Sodelovanje s podjetjem ICIT, inovativni center igralniških tehnologij d.o.o., na področju razvoja in implementacije optimizacijskih modelov in algoritmov za razporejanje zaposlenih, ter optimizacijskih algoritmov izdelave modela delovnega procesa. Sodelovanje se je pričelo leta 2004 in še vedno traja v obliki razvojno-vzdrževalne pogodbe za implementirane algoritme. 15. Skrb za povezavo znanja s slovenskim prostorom in za slovensko znanstveno Program P1-0297 Stran 11 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 terminologijo (Cobiss tip 1.04, 1.06, 1.07, 1.08, 1.09, 1.17, 1.18, 2.02, 2.03, 2.04, 2.05, 2.06)13 Naslov Nekaj primerov dvojnega štetja Opis Strokovni članek obravnava kombinatorični princip dvojnega štetja ter navaja več primerov uporabe na različnih področjih matematike. Objavljeno v KLAVŽAR, Sandi. Nekaj primerov dvojnega štetja. Obz. mat. fiz., 2008, letn. 55, št. 4, str. 121-128. COBISS.SI-ID 14984537 16. Skrb za popularizacijo znanstvenega področja (Cobiss tip 1.05, 1.21, 1.22, 2.17, 2.19, 3.10, 3.11, 3.12)14 Naslov Zoisovi nagrajenci Opis Intervju s Zoisovima nagrajencema na TV Pika v odddaji Sadovi znanja. Objavljeno v BRATKO, Ivan, KLAVŽAR, Sandi. Zoisovi nagrajenci : TV Pika, oddaja Sadovi znanja, 21. 12. 2007. Ljubljana, 2007. http://www.pika.tv/? showid = 02bb133575714e6e876dff46f118933f. COBISS.SI-ID 14628697 17. Vpetost vsebine programa v dodiplomske in podiplomske študijske programe na univerzah in samostojnih visokošolskih organizacijah v letih 2004 – 2008 1. Naslov predmeta Kombinatorična optimizacija, Diskretna matematika 1; Diskretna matematika 2; Računalništvo 1; Računalništvo 2; Računalništvo 3 Vrsta študijskega programa matematika (UNI) Naziv univerze/ fakultete UL FMF 2. Naslov predmeta Diskretna matematika; Računalništvo 1; Računalništvo 2; Optimizacija Vrsta študijskega programa matematika (VSŠ) Naziv univerze/ fakultete UL FMF 3. Naslov predmeta Diskretne strukture 1; Diskretne strukture 2; Kombinatorika; Optimizacijske metode; Računska geometrija; Alternativni modeli računanja Vrsta študijskega programa interdisciplinarni študij računalništva in matematike (UNI) Naziv univerze/ fakultete UL FMF+FRI 4. Naslov predmeta Probability in Computer Science; Izbrana poglavja iz diskretne matematike (več tem); Matematične igre Vrsta študijskega programa matematika, podiplomski študij Naziv univerze/ fakultete UL FMF Naslov predmeta Diskretne strukture; Kombinatorika Program P1-0297 Stran 12 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 5. Vrsta študijskega programa računalništvo in informatika (UNI) Naziv univerze/ fakultete UL FRI 6. Naslov predmeta Kombinatorika; Osnove algoritmov; Osnove podatkovnih struktur; Aktualno računalništo; Uporabna matematika Vrsta študijskega programa matematika Naziv univerze/ fakultete UM FNM 7. Naslov predmeta Diskretna matematika; Teorija algoritmov; Teorija grafov Vrsta študijskega programa matematika, podiplomski študij Naziv univerze/ fakultete UM FNM 18. Označite potencialne vplive oziroma učinke vaših rezultatov na navedena področja: Vpliv Ni vpliva Majhen vpliv Srednji vpliv Velik vpliv G.01 Razvoj visoko-šolskega izobraževanja G.01.01. Razvoj dodiplomskega izobraževanja r r a r G.01.02. Razvoj podiplomskega izobraževanja r r r (S G.01.03. Drugo: r r r r G.02 Gospodarski razvoj G.02.01 Razširitev ponudbe novih izdelkov/storitev na trgu a c r r G.02.02. Širitev obstoječih trgov (S r r r G.02.03. Znižanje stroškov proizvodnje a r r r G.02.04. Zmanjšanje porabe materialov in energije (S r r r G.02.05. Razširitev področja dejavnosti a r r r G.02.06. Večja konkurenčna sposobnost (S r r r G.02.07. Večji delež izvoza a r r r G.02.08. Povečanje dobička (S r r r G.02.09. Nova delovna mesta a r r r G.02.10. Dvig izobrazbene strukture zaposlenih r (S r r G.02.11. Nov investicijski zagon a r r r G.02.12. Drugo: r r r r G.03 Tehnološki razvoj G.03.01. Tehnološka razširitev/posodobitev dejavnosti a r r r Program P1-0297 Stran 13 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 G.03.02. dejavnosti 1» \ \ \ G.03.03. Uvajanje novih tehnologij (S r r r G.03.04. Drugo: C r r r G.04 Družbeni razvoj G.04.01 Dvig kvalitete življenja C r r r G.04.02. Izboljšanje vodenja in upravljanja a r r r G.04.03. Izboljšanje delovanja administracije in javne uprave a r r r G.04.04. Razvoj socialnih dejavnosti (S r r r G.04.05. Razvoj civilne družbe a r r r G.04.06. Drugo: r r r r G.05. Ohranjanje in razvoj nacionalne naravne in kulturne dediščine in identitete a r r r G.06. Varovanje okolja in trajnostni razvoj (S r r r G.07 Razvoj družbene infrastrukture G.07.01. Informacijsko-komunikacijska infrastruktura r r (S r G.07.02. Prometna infrastruktura a r r r G.07.03. Energetska infrastruktura a r r r G.07.04. Drugo: r r r r G.08. Varovanje zdravja in razvoj zdravstvenega varstva a r r r G.09. Drugo: r r r r Komentar^ C. IZJAVE Podpisani izjavljam/o, da: • so vsi podatki, ki jih navajamo v poročilu, resnični in točni • se strinjamo z obdelavo podatkov v skladu z zakonodajo o varstvu osebnih podatkov za potrebe ocenjevanja, za objavo 5., 6. in 7. točke na spletni strani http://sicris.izum.si/ ter obdelavo teh podatkov za evidence ARRS • so vsi podatki v obrazcu v elektronski obliki identični podatkom v obrazcu v pisni obliki Podpisi: vodja raziskovalnega programa zastopniki oz. pooblaščene osebe raziskovalnih organizacij in/ali koncesionarjev Bojan Mohar in/ali Inštitut za matematiko, fiziko in mehaniko Program P1-0297 Stran 14 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 Kraj in datum: Ljubljana 15.4.2009 Oznaka poročila: ARRS_ZV_RPROG_ZP_2008/575 1 Napišite kratko vsebinsko poročilo, kjer boste predstavili raziskovalno hipotezo in opis raziskovanja. Navedite ključne ugotovitve, znanstvena spoznanja ter rezultate in učinke raziskovalnega programa. Največ 21.000 znakov vključno s presledki (približno tri in pol strani, velikosti pisave 11). Nazaj 2 Največ 3000 znakov vključno s presledki (približno pol strani, velikosti pisave 11). Nazaj 3 Samo v primeru bistvenih odstopanj in sprememb od predvidenega programa raziskovalnega programa, kot je bil zapisan v predlogu raziskovalnega programa. Največ 3.000 znakov vključno s presledki (približno pol strani, velikosti pisave 11). Nazaj 4 Navedite največ pet najpomembnejših znanstvenih rezultatov programske skupine, ki so nastali v času trajanja programa v okviru raziskovalnega programa, ki je predmet poročanja. Za vsak rezultat navedite naslov v slovenskem in angleškem jeziku (največ 150 znakov vključno s presledki), rezultat opišite (največ 600 znakov vključno s presledki) v slovenskem in angleškem jeziku, navedite, kje je objavljen (največ 500 znakov vključno s presledki), izberite ustrezno šifro tipa objave po Tipologiji dokumentov/del za vodenje bibliografij v sistemu COBISS ter napišite ustrezno COBISS.SI-ID številko bibliografske enote. Navedeni rezultati bodo objavljeni na spletni strani http://sicris.izum.si/. PRIMER (v slovenskem jeziku): Naslov: Regulacija delovanja beta-2 integrinskih receptorjev s katepsinom X; Opis: Cisteinske proteaze imajo pomembno vlogo pri nastanku in napredovanju raka. Zadnje študije kažejo njihovo povezanost s procesi celičnega signaliziranja in imunskega odziva. V tem znanstvenem članku smo prvi dokazali… (največ 600 znakov vključno s presledki) Objavljeno v: OBERMAJER, N., PREMZL, A., ZAVAŠNIK-BERGANT, T., TURK, B., KOS, J.. Carboxypeptidase cathepsin X mediates ß2 - integrin dependent adhesion of differentiated U-937 cells. Exp. Cell Res., 2006, 312, 2515-2527, JCR IF (2005): 4.148 Tipopologija: 1.01 - Izvirni znanstveni članek COBISS.SI-ID: 1920113 Nazaj 5 Navedite največ pet najpomembnejših družbeno-ekonomsko relevantnih rezultatov programske skupine, ki so nastali v času trajanja programa v okviru raziskovalnega programa, ki je predmet poročanja. Za vsak rezultat navedite naslov v slovenskem in angleškem jeziku (največ 150 znakov vključno s presledki), rezultat opišite (največ 600 znakov vključno s presledki) v slovenskem in angleškem jeziku, izberite ustrezen rezultat, ki je v Šifrantu raziskovalnih rezultatov in učinkov (Glej: http://www.arrs.gov.si/sl/gradivo/sifranti/sif-razisk-rezult.asp), navedite, kje je rezultat objavljen (največ 500 znakov vključno s presledki), izberite ustrezno šifro tipa objave po Tipologiji dokumentov/del za vodenje bibliografij v sistemu COBISS ter napišite ustrezno COBISS.SI-ID številko bibliografske enote. Navedeni rezultati bodo objavljeni na spletni strani http://sicris.izum.si/. Nazaj 6 Pomen raziskovalnih rezultatov za razvoj znanosti in za razvoj Slovenije bo objavljen na spletni strani: http://sicris.izum.si Nazaj 7 Največ 4.000 znakov vključno s presledki Nazaj 8 Največ 4.000 znakov vključno s presledki Nazaj 9 Za raziskovalce, ki niso habilitirani, so pa bili mentorji mladim raziskovalcem, se vpiše ustrezen podatek samo v stolpec MR Nazaj 10 Vpisuje se uredništvo revije, monografije ali zbornika v skladu s Pravilnikom o kazalcih in merilih znanstvene in Program P1-0297 Stran 15 od 16 Zaključno poročilo o rezultatih raziskovalnega programa v obdobju 2004-2008 strokovne uspešnosti (Uradni list RS, št. 39/2006,106/2006 in 39/2007), kar sodi tako kot mentorstvo pod sekundarno avtorstvo, in delo (na zlasti nacionalno pomembnim korpusu ali zbirki) v skladu z 3. in 9. členom istega pravilnika. Največ 1000 znakov (ime) oziroma 150 znakov (število) vključno s presledki. Nazaj 11 Navedite oziroma naštejte konkretne projekte. Največ 12.000 znakov vključno s presledki. Nazaj 12 Navedite konkretne projekte, kot na primer: industrijski projekti, projekti za druge naročnike, državno upravo, občine ipd. in ne sodijo v okvir financiranja pogodb ARRS. Največ 9.000 znakov vključno s presledki. Nazaj 13 Navedite objavo oziroma prevod (soobjavo) članov programske skupine strokovnega prispevka v slovenskem jeziku, ki se nanaša na povezavo znanja s slovenskim prostorom in za slovensko znanstveno terminologijo (Cobiss tip 1.04, 1.06, 1.07, 1.08, 1.09, 1.17, 1.18, 2.02, 2.03, 2.04, 2.05, 2.06). Napišite naslov (največ 150 znakov vključno s presledki), kratek opis (največ 600 znakov vključno s presledki), navedite, kje je objavljen/a (največ 500 znakov vključno s presledki) ter napišite ustrezno COBISS.SI-ID številko bibliografske enote. Nazaj 14 Navedite objavo oziroma prevod (soobjavo) članov programske skupine, povezano s popularizacijo znanosti (Cobiss tip 1.05, 1.21, 1.22, 2.17, 2.19, 3.10, 3.11, 3.12). Napišite naslov (največ 150 znakov vključno s presledki), kratek opis (največ 600 znakov vključno s presledki), navedite, kje je objavljen/a (največ 500 znakov vključno s presledki), ter napišite ustrezno COBISS.SI-ID številko bibliografske enote. Nazaj 15 Komentar se nanaša na 18. točko in ni obvezen. Največ 3.000 znakov vključno s presledki. Nazaj Obrazec: ARRS-ZV-RPROG-ZP/2008 v1.00a Program P1-0297 Stran 16 od 16