Chip Firing Games
Parfois utilisés en économie, physique ou informatique, les "Chip Firing Games" sont des modèles discrets dynamiques où la donnée de départ est un graphe (orienté ou non orienté) avec des jetons posés sur chacun des sommets. La dynamique de ces modèles consiste à déplacer les jetons en suivant la règle suivante. Quand un sommet a au moins autant de jetons que d'arêtes/arcs sortant du sommet, il peut alors décider de "tirer" (fire) : pour chaque arête/arc sortant, un jeton part et va rejoindre le sommet à l'autre extrémité.Une configuration du modèle est tout simplement la distribution des jetons entre les différents sommets. Dans la version classique, dite séquentielle, de la dynamique, il n'y a pas de tirs simultanés. A priori à partir d'une même configuration initiale, différentes trajectoires des configurations peuvent être obtenues, en fonction de la suite des sommets choisis pour tirer (un configuration peut parfois admettre plusieurs tirs possibles).
L'objectif est ici de faire une présentation générale des "Chip Firing Games" et à sélectionner des résultats qui vous semblent importants. Pour vous guider dans cette sélection, voici quelques questions les concernant :
- Existe-t-il des "Chip Firing Games" admettant des trajectoires infinies (suite infinie de configurations où à chaque instant il existe toujours un sommet qui peut tirer) ? ou les trajectoires sont-elles toujours finies ?
- A partir d'une même configuration initiale, il existe souvent plusieurs trajectoires. Si ces trajectoires sont finies, terminent-elles sur la même configuration finale (où aucun sommet ne peut plus tirer) ? Si ces trajectoires sont finies, peuvent-elles avoir des durées différentes avant d'atteindre leur(s) configuration(s) finale(s) ?
- Lorsqu'il y a convergence en temps fini vers des configurations finales, existe-t-il des bornes sur le nombre d'étapes nécessaires pour converger ?
- Est-il facile (algorithmiquement) de prévoir le comportement d'un "Chip Firing Game" à partir de sa configuration initiale ?
- Est-ce que les résultats diffèrent beaucoup selon qu'on se place avec des graphes orientés ou bien des graphes non orientés ?
Quelques références (pas exhaustif).
- Chip-firing games on graphs, article de A. Björner, L. Lovasz, P. Shor, European Journal of Combinatorics, vol. 12, n. 4, pages 283-291 (1991). Un article de référence pour la version non orientée.
- Chip-firing games on graphs, article de A. Björner, L. Lovasz, Journal of Algebraic Combinatorics, vol. 1, pages 305-328 (1992).. Un article de référence pour la version orientée.
- Polynomial Bound for a Chip Firing Game on Graphs, article de G. Tardos, SIAM J. Discrete Math, vol. 1, n. 3, pages 397-398 (1988). Bornes sur les temps de convergence (cas non orienté). Je peux vous fournir une version papier.
- No polynomial bound for the chip firing game on directed graphs, article de K. Erikson, Proc. Amer. Math. Soc. 112, pages 1203-1205 (1991). Bornes sur les temps de convergence (cas orienté). Je peux vous fournir une version papier.
Retour à la page des sujets.