Nalaganje ...
Projekti / Programi vir: ARIS

RAZISKOVANJE NOTRANJE STRUKTURE STOLPNIH GRAFOV

Raziskovalna dejavnost

Koda Veda Področje Podpodročje
1.01.05  Naravoslovje  Matematika  Teorija grafov 

Koda Veda Področje
P001  Naravoslovno-matematične vede  Matematika 

Koda Veda Področje
1.01  Naravoslovne vede  Matematika 
Ključne besede
diskretna matematika; teorija grafov; teoretično računalništvo; problem Hanojskega stolpa; stolpni grafi; grafi Sierpińskega; celoštevilska zaporedja
Vrednotenje (pravilnik)
vir: COBISS
Raziskovalci (18)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacijŠtev. publikacij
1.  35352  dr. Jernej Azarija  Matematika  Raziskovalec  2016  25 
2.  17005  dr. Boštjan Brešar  Matematika  Raziskovalec  2016 - 2018  403 
3.  25993  dr. Sergio Cabello Justo  Matematika  Raziskovalec  2016 - 2018  218 
4.  32028  dr. Tanja Dravec  Matematika  Raziskovalec  2016 - 2017  143 
5.  35875  Marjeta Grahek    Tehnični sodelavec  2017 - 2018 
6.  36905  dr. Andreas Hinz  Matematika  Raziskovalec  2016 - 2018  66 
7.  05949  dr. Sandi Klavžar  Matematika  Vodja  2016 - 2018  1.173 
8.  33510  dr. Jelena Klisara  Matematika  Raziskovalec  2016  16 
9.  22648  dr. Tadeja Kraner Šumenjak  Matematika  Raziskovalec  2017 - 2018  118 
10.  31670  dr. Borut Lužar  Računalniško intenzivne metode in aplikacije  Raziskovalec  2016 - 2018  181 
11.  37403  dr. Tilen Marc  Matematika  Raziskovalec  2018  46 
12.  08727  dr. Uroš Milutinović  Matematika  Raziskovalec  2016 - 2018  348 
13.  01931  dr. Bojan Mohar  Matematika  Raziskovalec  2016 - 2018  1.002 
14.  16013  dr. Ciril Petr  Matematika  Raziskovalec  2016 - 2018  68 
15.  22649  dr. Janez Povh  Računalniško intenzivne metode in aplikacije  Raziskovalec  2016  341 
16.  11666  dr. Aleksander Vesel  Računalniško intenzivne metode in aplikacije  Raziskovalec  2016 - 2018  338 
17.  33306  dr. Sara Sabrina Zemljič  Matematika  Raziskovalec  2016 - 2018  19 
18.  03430  dr. Janez Žerovnik  Matematika  Raziskovalec  2017 - 2018  805 
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  19.643 
2.  2784  Fakulteta za informacijske študije v Novem mestu  Novo mesto  3375650  5.977 
Povzetek
Glavni cilj projekta je poglobiti razumevanje Hanojskih grafov, Sierpińskijevih grafov in razredov grafov, ki so njim sorodni. Specifična področja, ki jih nameravamo raziskovati, so naslednja. 1. Metrične lastnosti stolpnih grafov; 2. Algoritmi in računalniški eksperimenti nad stolpnimi grafi; 3. Strukturne lastnosti stolpnih grafov; 4. Raziskovanje stolpnih grafov, ki jo relevantni v (neuro-)psihologiji in drugje; 5. Klasifikacija grafov Sierpińskijevega tipa; in 6. Druga izdaja knjige ''The Tower of Hanoi—Myths and Maths''.   Jedro naših raziskav bo potekalo na klasični matematični način, torej kot izrek-dokaz. Vendar pa se bomo zaradi delikatne strukture Hanojskih grafov osredotočali tudi na numerično evidenco, da bi pridobili morebitne dokazljive rezultate. Glavni cilj naših računalniških eksperimentov bo izračun razdalj in metričnih invariant v Hanojskih grafih. Računalniške eksperimente bomo uporabili tudi za Hanojski stolp na zvezdi in za različne strukturne lastnosti Hanojskih grafov in grafov Sierpińskijevega tipa, kot je recimo pakirno kromatično število Sierpińskijevega grafa.   Naćrtujemo tudi raziskovanje invariant in drugih problemov na Sierpińskijevih grafih in razredih grafov, ki so njim sorodni, vključujoč tiste, katere je v bolj splošnem okviru predlagal Hasunuma in so znotraj raziskovalne skupnosti aktualni. Na ta način bomo poglobili razumevanje teh razredov grafov ter jih obenem odprli drugim raziskovalcem. Problemi, ki jih nameravamo raziskovatii, vključujejo kompleksnost (število vpetih dreves), število prirejanj, pakirno kromatično število, in igra dominacije.   Pri Hanojskih grafih je situacija precej bolj zahtevna. Na primer, ne obstajajo netrivialne 1-popolne kode v Hanojskih grafih in obstaja mnogih grafovskih invariant, ki so bile določene za Sierpińskijeve grafe, vendar so do sedaj neznane za Hanojske grafe, kot sta recimo dominacijsko število in neodvisno število. Naš načrt je napasti te invariante in pridobiti dobre zgornje in spodnje meje za njih, saj se zdi, da je točne vrednosti zelo težko dobiti.   V središču testiranja kognitivnih sposobnosti s strani (nevro-)psihologov je igra Londonskega stolpa. Večina grafovskih invariant je v Londonskih grafih neznanih (na primer, že izračun števila povezav vodi do zapletenih vprašanj iz teorije števil), zato je naš primarni cilj določitev točnih ali dobrih približnih vrednosti grafovskih invariant tistih Londonskih grafov, kateri so zanimivi (nevro-)psihologom.   Stolpni grafi so uporabni marsikje. Pred nekaj meseci je bila objavljena kemična samo-konstrukcija ''Sierpińskijevih trikotnikov''. Naš cilj v povezavi s to aplikacijo je razumevanje take samo-konstrukcije in pogledati kako bi lahko uporabili naše razumevanje grafov Sierpińskijevega tipa za nove vpoglede v to kemijsko aplikacijo.   Grafi, katerih grafične upodobitve so aproksimacije znamenitega Sierpińskijevega trikotnika, so bili intenzivno raziskovani zadnjih 25 let in sicer na mnogih različnih znanstvenih področjih. Zato ni presenetljivo, da so bila uporabljena različna poimenovanja za isti objekt in ista imena za različne objekte. Naš cilj je vpeljati nekaj reda v ta živalski vrt grafov Sierpińskijevega tipa in povzeti lastnosti najbolj pomembnih razredov.   Načrtujemo tudi drugo izdajo knjige ''The Tower of Hanoi—Myths and Maths''. Vsebovala bo številne dopolnitve, poleg tega pa tudi več uvodnega materiala iz diskretne matematike in matematike v splošnem, zato da bo bolj primerna za učno uporabo. Drugo izdajo knjige je med drugim sprožil napredek na problemu, ki je bil odprt več kot stoletje. Ta napredek, ki je delo Thierry Bousch-a iz Pariza, bo osrednje področje našega projekta. Z avtorjem smo v kontaktu in ga želimo vključiti v naša lastna prizadevanja.
Pomen za razvoj znanosti
Projekt spada med temeljne raziskave s področja matematike in povezanih področij kot je to računalništvo. 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 problemi področja, hkrati pa imajo aplikacije v drugih znanostih, na primer v psihologiji in kemiji.    Problemi, ki jih nameravamo raziskovati, so po eni strani še nerešeni, po drugi strani pa so glede na veliko aktualnost grafov Sierpińskijevega tipa (vključno s Hanojskimi grafi) zelo relevantni. Pričakujemo, da bomo s področja vsebine predlaganega projekta objavili več znanstvenih člankov v osrednjih revijah s področja diskretne matematike in svoje rezultate predstavili na relevantnih mednarodnih konferencah. Delo na projektu bo tudi odlična osnova za pripravo druge izdaje Springerjeve monografije The Tower of Hanoi—Myths and Maths iz leta 2013. Da je druga izdaja potrebna utemeljujemo z izjemno hitrim razvojem področja in z ducatom zelo pozitivnih recenzij prve izdaje knjige. Nadalje, računalniški eksperimenti velikega obsega lahko služijo kot model za bodoče algoritme in izračunljivostne metode.
Pomen za razvoj Slovenije
Predlagani projekt je temeljne narave, zato je težko izmeriti njegov neposredni pomen za gospodarstvo in družbo. Po drugi strani pa je projekt zasnovan tako, da omogoča vključevanje mladih raziskovalcev in študentov v projektne aktivnosti ter tako omogoča dolgoročno ohranjanje kvalitetnega raziskovalnega dela s področja matematike. To ima neposreden pozitiven vpliv na kvaliteto univerzitetnih programov matematike in drugih znanosti. Kot direktni pomen projekta lahko smatramo tudi dejstvo, da podpira nadaljevanje raziskovalnih stikov slovenskih znanstvenikov z najbolj aktualnimi znanstvenimi dogajanji.
Najpomembnejši znanstveni rezultati Vmesno poročilo, zaključno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati Vmesno poročilo, zaključno poročilo
Zgodovina ogledov
Priljubljeno