Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.
Članica UL: Fakulteta za matematiko in fiziko
Šifra projekta: Z1-50003
Naziv projekta: Igra policajev in roparja na grafih in geodetskih prostorih
Obdobje: 1. 10. 2023 - 30. 9. 2025
Letni obseg: 1 FTE, cenovna kategorija: B
Vodja: Vesna Iršič
Veda: Naravoslovje
Sodelujoče RO, sestava projektne skupine in bibliografske reference
Vsebinski opis projekta:
Grafi se uporabljajo za modeliranje problemov z različnih področji, na primer v računalništvu, kemiji in družboslovnih vedah. Zanimivo je, da mnoge realne probleme najlažje modeliramo kot igre na grafih. Raziskovanje širjenja novega virusa med ljudmi, omejevanje požara v naravi, iskanje izgubljene osebe v jamskem sistemu ali lovljenje roparja v mestu lahko opišemo s pomočjo igre policaja in roparja na grafu (ali ene od njenih različic). Ker v nekaterih primerih omejitev na grafe pomeni precejšnjo poenostavitev, je zanimivo raziskovati enako igro tudi na geodetskih prostorih.
Igra policajev in roparja je že desetletja ena od osrednjih tem teorije grafov. Poleg mnogih uporab v vsakdanjem življenju je igra tesno povezana z nekaterimi lastnostmi grafov. Igro na grafu igrata dva igralca, ki se premikata po vozliščih grafa. Prvi igralec predstavlja policaje, drugi igralec pa roparja. Policaji poskušajo ujeti roparja, ki se želi temu izogniti. Najmanjše število policajev, ki je potrebno, da policaji ujamejo roparja na danem grafu, je policijsko število grafa. Najpomembnejše domneve s področja določajo zgornje meje za policijsko število grafa v povezavi z njegovo velikostjo ali rodom. Vpeljane in študirane so bile že tudi številne različice igre. Ena izmed novejših različic igro namesto na grafu obravnava na splošnem geodetskem prostoru. Kljub podobnostim z drugimi diferencialnimi igrami ta različica ohranja diskretno naravo in kaže podobnosti z igro na grafih.
Cilj projekta je raziskovanje igre policajev in roparja na grafih in na geodetskih prostorih. Študirane bodo zgornje meje za policijsko število geodetskega prostora v odvisnosti od lastnosti prostora, s posebnim poudarkom na ploskvah, simplicialnih kompleksih in metričnih grafih. V povezavi z igro na grafih bo pozornost posvečena odprtim domnevam, vključno z domnevama Meyniela in Schröderja, tako za originalno različico igre kot za nekatere njene že uveljavljene različice. Iskali bomo izboljšave v smeri odprtih domnev ter raziskali morebitne povezave med domnevami.
