Preskoči na vsebino Preskoči na navigacijo

Inštitut za matematiko, fiziko in mehaniko

Language:
RSS:
Navigacija

Although he may not always recognize his bondage, modern man lives under a tyranny of numbers.

Nicholas Eberstadt
Nahajate se tu: Domov Raziskave in projekti Raziskovalni projekti J1-7110 - Raziskovanje notranje strukture stolpnih grafov
Akcije dokumenta

J1-7110 - Raziskovanje notranje strukture stolpnih grafov

Vodja projekta: prof. dr. Sandi Klavžar.

Temeljni znanstveno-raziskovalni projekt.

Vodja projekta: prof. dr. Sandi Klavžar

Naslov projekta: Raziskovanje notranje strukture stolpnih grafov

Šifra projekta: J1-7110

Veda: Naravoslovno matematične vede

Trajanje projekta: 01. 01. 2016 - 31. 12. 2018.

Cenovna kategorija: C

Letni obseg projekta: 0,82 FTE

Sodelujoča organizacija: 2784 - Fakulteta za informacijske študije Novo mesto

Projekt sofinancira: Javna agencija Republike Slovenije za raziskovalno dejavnost.

Vsebinski opis projekta:

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.

Sestava projektne skupine: povezava na SICRIS

Bibliografske reference: povezava na SICRIS