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.^[1][2] 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:

${\displaystyle 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,^[3] hurokélekkel, többszörös élekkel rendelkező gráfokon is. A játék Norman Biggs-féle változata,^[1] 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),^[4] ami még hosszú útgráfokon volt értelmezve.^[5] Az 1989-es,^[6] 1991-es^[7] 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^[3] 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 (wd) önszervező kritikusságát; 1999-es cikkében^[1] „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:^[3] 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.^[6]
• Ha minden csúcs legalább egyszer lő, akkor a játék végtelen^[8]
• Ha a zsetonok száma kisebb az élek számánál, a játék mindig véges.^[7]
• 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.^[7]
• 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.^[7]
• 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.^[3]
• 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).^[8]
• Az irányított verzióban egy véges játék exponenciálisan sok lépés hosszúságú is lehet.^[9]

További információk

• MIT Course 18.312: Algebraic Combinatorics
• Weisz Ágoston: A koronglövő játék. Szakdolgozat, ELTE TTK Bsc, 2014^{[halott link]}
• 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.) ^{[halott link]}

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.

Jegyzetek

1. 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.) ^{[halott link]}
2. wikidot: Chip-firing references. (Hozzáférés: 2014. május 19.)
3. 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 PDF
4. Criel Merino: The Chip Firing Game and Matroid Complexes, in: Discrete Mathematics and Theoretical Computer Science Proceedings AA (DM-CCG), 2001, 245–256
5. J. Spencer. Balancing vectors in the max norm., in: Combinatorica, 6:55–66, 1986 doi:10.1007/BF02579409
6. Spencer, J., Anderson, R. J., Lovász, L., Shor, P., Tardos, E., & Winograd, S. (1989). Disks, balls and walls: Analysis of a combinatorial game. American Mathematical Monthly, 96, 481-493. doi:10.2307/2323970
7. 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
8. G. Tardos, Polynomial bound for a chip firing game on graphs, SIAM J. Discrete Math. 1 (1988), 397–398. doi:10.1137/0401039
9. K. Eriksson, No polynomial bound for the chip-firing game on directed graphs, Proc. Amer. Math. Soc. 112 (1991), 1203–1205. doi:10.2307/2048674 PDF^{[halott link]}