Projekti / Programi
RAZISKOVANJE NOTRANJE STRUKTURE STOLPNIH GRAFOV
| 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 |
diskretna matematika; teorija grafov; teoretično računalništvo; problem Hanojskega stolpa; stolpni grafi; grafi Sierpińskega; celoštevilska zaporedja
Raziskovalci (18)
Organizacije (2)
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
