Zsetonlövő játék

A matematika, azon belül a gráfelmélet területén az 1980-as években megjelent chip firing-játék, koronglövő játék vagy zsetonlövő játék a strukturális kombinatorika fontos vizsgálati témája.

A játék stabil és visszatérő konfigurációinak halmaza Abel-csoportként jellemezhető. Ráadásul a csoport rendje megegyezik a gráf fa-számával (tree number), azaz a gráf éleit lefedő fák minimális számával. A játék vizsgálata során gyakran a gráf Laplace-mátrixával kell számításokat végezni.

A játék leírása

Példagráf

Egy legális lövéssorozat

A chip firing-játék tetszőleges G = (V, E) (alapesetben: véges, egyszerű, összefüggő, irányítatlan) gráfon játszott egyszemélyes játék. Kezdetben a gráf minden csúcsán van néhány zseton. Egy lépés abból áll, hogy a játékos kiválasztja a gráf valamely v ∈ V csúcsát, melyen a csúcs deg(v) fokszámánál nem kisebb számú zseton van (tehát „fel van töltve”, vagy „szabad”), és azokból egyet-egyet átad a csúcs szomszédainak („a csúcs lő”).

A játék egy lépése során tetszőleges szabad csúcs lőhet. A játék véget ér, ha már nincsen szabad csúcs a gráfban, ekkor ezt a korongkiosztást vagy konfigurációt végső konfigurációnak nevezzük. Azt mondjuk, hogy a v₁, v₂, ..., v_k lövéssorozat legális, ha az i-edik lépésben a v_i csúcs szabad volt. A lövések számát a játék hosszának nevezzük, ez nem feltétlen véges. Diffúz egy konfiguráció, ha ismétlődően előállhat.

Minden v_i csúcshoz tehát egy nemnegatív S(v_i). Legyen s a játék zsetonkonfigurációja. Egy lépés során kiválasztunk egy v_j csúcsot, melyre igaz, hogy S(v) ≥ deg (v). A csúcs tüzelése során elveszít fokszámának megfelelő számú zsetont, a szomszédos csúcsok pedig 1-1 zsetont nyernek. Ha v(v, w) a v_j-t w-vel összekötő élek száma, x(v) értéke pedig, hogy v hány alkalommal tüzelt egy lépéssorozat alatt.

Ekkor s tüzelése után az új konfigurációt, s'-t a következő képlet adja:

$s'(v)=s(v)-x(v)\deg(v)+\sum x(v)v(v,w)$

Variációk

A játék értelmezhető irányított gráfokon, hurokélekkel, többszörös élekkel rendelkező gráfokon is. A játék Norman Biggs-féle változata, a „dollar game” esetében az egyik, q-val jelölt csúcs, a nyelő (avagy bank) negatív értékeket is fölvehet, de csak akkor tüzelhet, ha más csúcs nem képes tüzelni (ilyenkor a bank „pénzt önt a gazdaságba”, amíg az nem képes újra funkcionálni).

Története

A játék kezdetleges formája legalább 1983-ig nyúlik vissza, amikor Joel Spencer prezentálta „kiegyensúlyozó” játékát (balancing game), ami még hosszú útgráfokon volt értelmezve. Az 1989-es, 1991-es cikkekben Lovász László, Peter Shor, Joel Spencer, Tardos Éva, Shmuel Winograd már az általános gráfokon értelmezett, chip firing game-nek nevezett játék dinamikáját vizsgálták részletesen. Az 1992-es Björner–Lovász-tanulmány irányított gráfokon vizsgálja a játékot. Norman Biggs felfedezett egy a játékkal kapcsolatba hozható folyamatot, az Abel-féle homokdombok önszervező kritikusságát; 1999-es cikkében „dollar game”-nek nevez egy olyan játékvariációt, ahol az egyik, q-val jelölt csúcs, a nyelő (avagy bank) negatív értékeket is fölvehet, de csak akkor tüzelhet, ha más csúcs nem képes tüzelni. A játék így feltétlenül végtelen hosszúságú.

Eredmények

A chip firing game vizsgálata során természetesen felmerülő kérdések közé tartoznak: a játék milyen esetekben véges, mikor végtelen? Ha véges, hány körön át tarthat? Ha végtelen, hány kör után válik ismétlődővé? Lényeges-e, hogy milyen lépéseket hajtunk végre? Hogyan határozható meg, hogy a zsetonok egyik konfigurációjából el lehet-e jutni egy másik konfigurációba?

• A játék végessége a gráftól, illetve a zsetonok elhelyezésétől és számától függ, viszont attól nem, hogy a játékos milyen sorrendben lő a csúcsokkal. Ráadásul, adott összefüggő gráfban az érvényes lépéssorozatok vagy végtelen sokáig folytatódnak, vagy ugyanannyi lépés után, ugyanazzal a végső konfigurációval záródnak, továbbá adott csúcs bármely legális lépéssorozat során ugyanannyiszor tüzel.
• Ha minden csúcs legalább egyszer lő, akkor a játék végtelen
• Ha a zsetonok száma kisebb az élek számánál, a játék mindig véges.
• Ha a zsetonok száma nagyobb, mint az élek számának kétszerese mínusz a csúcsok száma, a játék mindig végtelen.
• Ha a zsetonok száma nagyobb az élek számánál, de nem nagyobb az élek számának kétszerese mínusz a csúcsok számánál, a játék a kezdeti konfigurációtól függően végtelen is lehet.
• Erősen összefüggő irányított gráf esetében, ha a zsetonok száma kisebb az éldiszjunkt irányított körök számánál, akkor a játék véges.
• Az irányítatlan verzióban ha egy játék véges, akkor legfeljebb polinom számú lépés után véget ér (Tardos Gábor).
• Az irányított verzióban egy véges játék exponenciálisan sok lépés hosszúságú is lehet.

További információk

• MIT Course 18.312: Algebraic Combinatorics
• Weisz Ágoston: A koronglövő játék. Szakdolgozat, ELTE TTK Bsc, 2014
• A. Björner, L. Lovász, P. W. Shor: Chip-firing games on graphs. European Journal of Combinatorics archive, Volume 12 Issue 4, July 1991, Pages 283-291 doi:10.1016/S0195-6698(13)80111-4 PDF
• A. Björner, L. Lovász: Chip-Firing Games on Directed Graphs. Journal of Algebraic Combinatorics, December 1992, Volume 1, Issue 4, pp 305–328 doi:10.1023/A:1022467132614
• Chip firing survey on Egerváry Research Group
• Games built on chip-firing (2010) Archiválva 2017. július 11-i dátummal a Wayback Machine-ben
• Biggs, Norman L. (1997. június 25.). „Chip-Firing and the Critical Group of a Graph”. Journal of Algebraic Combinatorics, 25–45. o. (Hozzáférés: 2014. május 10.)  

Fordítás

• Ez a szócikk részben vagy egészben a Norman L. Biggs című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.