Obdobje poteka: 1.1.2016 – 31.12.2018
Financer: ARRS
Sodeluje: Laboratorij za kompleksne sisteme in podatkovne znanosti

Raziskovanje notranje strukture stolpnih grafov (J1-7110 )

Obdobje poteka: 1.1.2016 – 31.12.2018
Financer: ARRS
Sodeluje: Laboratorij za kompleksne sisteme in podatkovne znanosti

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. Vodja projekta na FIŠ: doc. dr. Borut Lužar