X. Si, est pas connexe, alors X se décompose en un ensemble de composantes connexes C k . Pour chaque C k le monôme dominant de T (C k ) divise celui de T (X) car d i (C k ) = d i (X) pour tout i ? C k

. Sinon-x-n-'est-pas-connexe, Donc une de ses composantes que l'on notera C ne contient pas le puits n. Alors le monôme dominant de T (X ? C) divise celui de T (X) car pour tout i ? X, l'inclusion X ? C ? X entra??neentra??ne que d i (X ? C) ? d i (X)

M. [. Bak and . Creutz, Fractals and self-organized criticality, Fractals in Science, pp.27-47, 1995.
DOI : 10.1007/978-3-642-77953-4_2

L. [. Björner and . Lovász, Chip-firing on directed graphs, Journal of Algebraic Combinatorics, vol.1, issue.4, pp.305-328, 1992.
DOI : 10.1023/A:1022467132614

A. Bjorner, L. Lovasz, and P. Schor, Chip-firing Games on Graphs, European Journal of Combinatorics, vol.12, issue.4, pp.283-291, 1991.
DOI : 10.1016/S0195-6698(13)80111-4

P. Bak, C. Tang, and K. Wiesenfeld, noise, Physical Review Letters, vol.59, issue.4, pp.381-384, 1987.
DOI : 10.1103/PhysRevLett.59.381

P. Bak, C. Tang, and K. Wiesenfeld, Self-organized criticality, Physical Review A, vol.38, issue.1, pp.364-374, 1988.
DOI : 10.1103/PhysRevA.38.364

P. [. Chen and . Bak, Self-organized criticality in a crack-propagation model of earthquakes, Physical Review A, vol.43, issue.2, pp.625-630, 1991.
DOI : 10.1103/PhysRevA.43.625

D. Cox, J. Little, O. Shea, and D. , Ideals, varieties, and algorithms : An introduction to computational algebraic geometry and commutative algebra, 1991.

H. Cohen, A course in computational algebraic number theory, 1993.
DOI : 10.1007/978-3-662-02945-9

[. Cori and D. Rossin, On the Sandpile Group of Dual Graphs, European Journal of Combinatorics, vol.21, issue.4, pp.447-459, 2000.
DOI : 10.1006/eujc.1999.0366
URL : https://hal.archives-ouvertes.fr/hal-00016380

]. R. Crsed, D. Cori, B. Rossin, and . Salvy, Polynomial ideals for sandpiles and their gröbner bases, TCS

D. Dhar, Self-organized critical state of sandpile automaton models, Physical Review Letters, vol.64, issue.14, pp.1613-1616, 1990.
DOI : 10.1103/PhysRevLett.64.1613

S. [. Dhar and . Manna, Inverse avalanches in the Abelian sandpile model, Physical Review E, vol.49, issue.4, pp.2684-2687, 1994.
DOI : 10.1103/PhysRevE.49.2684

P. [. Dhar, S. Ruelle, D. Sen, and . Verma, Algebraic aspects of Abelian sandpile models, Journal of Physics A: Mathematical and General, vol.28, issue.4, pp.805-831, 1995.
DOI : 10.1088/0305-4470/28/4/009

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in Graphs, 1998.
DOI : 10.1201/b16132-65

K. [. Hafner and . Mccurley, Asymptotically Fast Triangularization of Matrices over Rings, SIAM Journal on Computing, vol.20, issue.6, pp.1068-1083, 1991.
DOI : 10.1137/0220067

O. Marguin, Application de méthodes algébriquesalgébriquesà l'´ etude algorithmique d'automates cellulaires etàetà l'analyse par ondelettes, 1997.

D. [. Majumdar and . Dhar, Height correlations in the Abelian sandpile model, Journal of Physics A: Mathematical and General, vol.24, issue.7, pp.357-362, 1991.
DOI : 10.1088/0305-4470/24/7/008

. W. Mm82-]-e, A. Mayr, and . Meyer, The complexity of the word problem for commutative semigroups and polynomial ideals, Adv. Math, vol.46, pp.305-329, 1982.

. Cris, M. Moore, and . Nilsson, The computationnal complexity of sandpiles, Journal of Statistical Physics, vol.96, pp.205-224, 1999.

A. Storjohann and G. Labahn, Asymptotically fast computation of Hermite normal forms of integer matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation , ISSAC '96, pp.96-96
DOI : 10.1145/236869.237083

A. Storjohann and T. Mulders, Fast Algorithms for Linear Algebra Modulo N, ESA 98, pp.139-150, 1998.
DOI : 10.1007/3-540-68530-8_12

]. Ste99, . Ian, and . Stewart, Defend the roman empire !, Scientific American, pp.136-138, 1999.

. Arne and . Storjohann, A fast + practical + deterministic algorithm for triangularizing integer matrices, 1996.

. Arne and . Storjohann, Near optimal algorithms for computing smith normal forms of integer matrices, p.96, 1996.

. Arne and . Storjohann, Computing hermite and smith normal forms of triangular integer matrices, Linear Algebra and its applications, vol.282, pp.25-45, 1998.

R. M. Wilson and J. H. Van-lindt, A course in combinatorics, pp.449-460, 1992.

L. Y. , L. , S. Steven, and S. , Algorithm for square roots of graphs, SIAM J. Discrete Math, vol.8, issue.1, pp.99-118, 1995.