Chip-pálení hra - Chip-firing game - Wikipedia

Příklad grafu

Možná sekvence střelby se stavovými proměnnými s(proti) červeně a vrchol vystřelený žlutě.

The hra na pálení žetonů je hráč jednoho hráče hra na graf který byl vynalezen kolem roku 1983 a od té doby se stal důležitou součástí studia strukturní kombinatorika.

Definice

Nechť konečný graf G být připojeno a bezmocný, s vrcholy PROTI = {1, 2, . . . , n}. Nechte deg (proti) být stupeň vrcholu a e (v, w) počet hran mezi vrcholy proti a w. Konfigurace nebo stav hry je definován přiřazením každého vrcholu nezáporného celého čísla s(proti), což představuje počet žetonů na tomto vrcholu. Tah začíná výběrem vrcholu w který má alespoň tolik čipů jako jeho stupeň: s(w) ≥ stupeň (w). Vrchol w je vystřelil, přesunutí jednoho čipu z w podél každého dopadajícího okraje do sousedního vrcholu, čímž se vytvoří nová konfigurace ${ displaystyle s '}$ definován:

${ displaystyle s '(w) = s (w) - deg (w)}$

a pro v ≠ w,

${ displaystyle s '(v) = s (v) + e (v, w).}$

Stav, ve kterém již není možné střílet, je a stabilní stav. Počínaje počáteční konfigurací pokračuje hra s následujícími výsledky.

Pokud je počet žetonů menší než počet hran, hra je vždy konečná a dosahuje stabilního stavu.
Pokud má každý vrchol méně žetonů než jeho stupeň, hra je konečná.

Pokud je počet žetonů alespoň počet hran, může být hra pro vhodně zvolenou počáteční konfiguraci nekonečná a nikdy nedosáhne stabilního stavu.
Pokud je počet žetonů více než dvojnásobek počtu hran minus počet vrcholů, hra je vždy nekonečná.

Biggsova varianta

Ve variantě střelby z čipů úzce související s sandpile model, také známý jako dolar hra, jeden speciální vrchol q je označen jako banka, a může se zadlužit, přičemž získá zápornou celočíselnou hodnotu s(q) <0. Pokud může střílet jakýkoli jiný vrchol, banka nemůže střílet, pouze shromažďuje žetony. Nakonec, q nashromáždí tolik čipů, že žádný jiný vrchol nemůže vystřelit: pouze v takovém stavu, vrchol q může střílet žetony na sousední vrcholy, aby „nastartoval ekonomiku“.

Sada stavů, které jsou stabilní (tj. Pouze pro které q může střílet) a opakující se pro tuto hru může být dána struktura abelianská skupina který je izomorfní s přímým produktem ${ displaystyle mathbb {Z}}$ a skupina pískovců (označované také jako Jacobian group or critical group). Pořadí posledně jmenovaného je strom číslo grafu.^[1]^[2]

Viz také

Reference

^ Biggs, Norman L. (25. června 1997). „Chip-Firing a kritická skupina grafu“ (PDF). Journal of Algebraic Combinatorics: 25–45. Citováno 10. května 2014.
^ wikidot. „Odkazy na pálení třísek“. Citováno 19. května 2014.

A. Björner, L. Lovász, P. W. Shor: Chip-firing games on graphs. Archiv European Journal of Combinatorics, svazek 12, vydání 4, červenec 1991, strany 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, prosinec 1992, svazek 1, číslo 4, str. 305–328 doi:10.1023 / A: 1022467132614

externí odkazy

[1] Biggs, Norman L. (25. června 1997). „Chip-Firing a kritická skupina grafu“ (PDF). Journal of Algebraic Combinatorics: 25–45. Citováno 10. května 2014.

[2] wikidot. „Odkazy na pálení třísek“. Citováno 19. května 2014.

[1]

[2]