Temeljni znanstveno-raziskovalni projekt

Naslov projekta: Splošna lega in vidnost v teoriji grafov
 
Šifra projekta: J1-70045
 
Veda: Naravoslovno matematične vede

Trajanje projekta: 01. 03. 2026 - 28. 02. 2029.
 
Cenovna kategorija: B
 
Letni obseg projekta: 1,89 FTE
 
Sodelujoča organizacija: 1554 - Univerza v Ljubljani, Fakulteta za matematiko in fiziko

Projekt sofinancira: Javna agencija Republike Slovenije za znanstvnoraziskovalno in inovacijsko dejavnost.
 
Vsebinski opis projekta: Problem vidnosti v grafih lahko zasledimo že pri Dudeneyju, ki je leta 1917 postavil t.i. no-three-in-line uganko, ki je še danes odprta. Problem, kako na kvadratno mrežo postaviti čim več točk, da nobena od treh točk ne bo ležala na isti premici, se naravno razširi na grafe tako, da nas zanimajo čim večje množice vozlišč, tako da najkrajše poti med dvema poljubnima vozliščema iz množice ne vsebujejo dodatnega vozlišča iz nje. Takšne množice imenujemo množice vozlišč v splošni legi. Drugi glavni koncept, ki nas zanima in je dualni koncept množicam vozlišč v splošni legi, izvira iz računalništva. Di Stefano je leta 2022 zasnoval model vidnosti v teoriji grafov tako, da je vprašal po največji možni množici vozlišč, tako da se roboti, ki se nahajajo v teh vozliščih, vidijo med seboj po najkrajših poteh. V tem projektu nameravamo raziskati ta dva koncepta, rešiti odprte probleme in utreti poti za nadaljnje raziskave teh množic.

Problemi in teme o množicah vozlišč v splošni legi, ki jih nameravamo raziskati, so naslednji. Prvič, raznolikost konceptov splošne lege. Ta tema vključuje štiri-elementno raznolikost, spodnje množice v splošni legi in množice v deljeni splošni legi. Drugič, strukturni vidiki množic v splošni legi. Ta tema vključuje polinom splošne lege, vpliv lokalnih grafovskih operacij na raznolikost splošne lege in raznolikost množic v splošni legi na produktih grafov. Tretjič, igralni pristop k množicam vozlišč v splošni legi. Načrtovan je tudi pregledni članek o množicah v splošni legi.

Problemi in teme o množicah vzajemne vidnosti na grafih, ki jih bomo raziskati, so naslednji. Prvič, raznolikost konceptov vzajemne vidnosti. Ta tema vključuje štiri-elementno raznolikost vzajemne vidnosti, lokalno vzajemno vidnost in deljeno lokalno vidnost. Drugič, strukturni vidiki množic vzajemne vidnosti. Ta tema vključuje polinom vzajemne vidnosti, povezave med vzajemno vidnostjo in dominacijo in graf vidnosti. Tretjič, igralno teoretični pristop k množicam vzajemne vidnosti. Načrtovan je tudi pregledni članek o množicah vzajemne vidnosti. 

Sestava projektne skupine: povezava na SICRIS
 
Bibliografske reference: povezava na SICRIS