Domination game on paths and cycles

angleški

2017

letnik 13, številka 1

cikli   dominacijska igra   igralno dominacijsko število   poti

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Dominacijska igra je igra za dva igralca, Dominatorja in Zavlačevalko, ki se odvija na enostavnem grafu. Igralca izmenično izbirata vozlišča, tako da v vsaki potezi izbereta vozlišče, ki v svoji zaprti okoli vsebuje vsaj eno še nedominirano vozlišče (tj. vozlišče, ki še ni bilo izbrano in ni sosednjo nobenemu izbranemu). Igra se konča, ko so vsa vozlišča dominirana in zato ni na voljo več nobene poteze. Dominator želi igro zaključiti čim hitreje, medtem ko Zavlačevalka želi ravno nasprotno, tj. končati igro v čim več potezah. Z ?$\gamma_g$? oziroma ?$\gamma_g'$? označujemo skupno število potez v igri, v kateri prvo potezo naredi Dominator oziroma Zavlačevalka in oba igralca igrata po svojih optimalnih strategijah. Avtorji Kinnersley et al. so v rokopisu iz leta 2012 izračunali vrednosti obeh invariant za poti in cikle, vendar rezultatov niso nikoli objavili. V tem članku dokažemo isti rezultat na povsem drugačen način. Še več, naš pristop nam poleg vrednosti invariant eksplicitno opiše tudi optimalni strategiji obeh igralcev.

29.05.2020