Etats critiques dans le modèle du tas de sable
Compléments

Robert Cori

25 Février 1998

Ce texte complète la description du sujet qui figure dans le polycopié de présentation des projets. Il donne en particulier des indications détaillées pour le calcul de l'identité et de la structure du groupe des états effectifs introduit dans le texte de présentation. On utilise, dans la mesure ou cela ne complique pas la description, la version généralisée des tas de sable pour des réseaux quelconques, le cas particulier des grilles sera considéré comme un exemple.

1  Graphes à puits

Un graphe à puits G = (X,0,E) est donné par un ensemble fini X={0, 1,2, ... , n} de sommets, (le sommet 0 est appelé puits) et un ensemble fini d'arêtes E. A chaque arête e est associée une paire {i,j} de sommets, appelés les extrémités de l'arête. Deux sommets i,j extrémités d'une arête e Î E sont dits voisins, l'ensemble des voisins d'un sommet i est noté V(i), le nombre d'arêtes dont le sommet i est extrémité est noté di; noter que l'on n'a pas toujours di = |V(i)|, car il peut y avoir plusieurs arêtes ayant mêmes extrémités. Pour tout couple de sommets i,j on note E(i,j) le nombre d'arêtes ayant pour extrémités {i,j}. On vérifie facilement que E(i,j) =E(j,i), que j est voisin de i si E(i,j) >0 et que di = åi=0n E(i,j).




Dans le cas de la grille ( p,q), l'ensemble des sommets est constitué du puits 0, et les cellules 1, 2, ... ,n=pq. Pour chaque sommet i autre que le puits on a di=4 ainsi les cellules qui ne sont pas sur le bord sont reliées à leurs 4 voisines, les cellules sur les 4 coins sont reliées au puits par deux arêtes différentes et par une are6te à chacune de leurs 2 voisines, les autres cellules du bord sont reliées au puits par une arête de même qu'à leurs trois voisines. Ainsi on a d0 = 2(p+q).




Une configuration c est une application de X dans l'ensemble des entiers naturels, celle-ci peut être représentée par une suite d'entiers c = c0, c1, ..., cn. Dans la suite on fera référence à ci comme la valeur du sommet i. L'éboulement du sommet i >0 est défini par un opérateur Di qui à c tel que ci ³ di fait correspondre c' satisfaisant c'i = ci -di, et cj=c'j + E(i,j) pour j ¹ i. Noter que le puits ne peut pas s'ébouler. Une configuration telle que " i >0 on ait ci < di est dite stable.

Une succession d'éboulements est appelée avalanche. On peut démontrer les résultats suivants :
  1. Pour toute configuration c, le nombre d'éboulements consécutifs possibles à partir de c est fini.
  2. Toutes les configurations stables que l'on peut atteindre par une avalanche à partir de c sont identiques (ainsi l'ordre dans lequel sont effectués les éboulements est indifférent).

Pour une configuration c, on note r(c) la configuration stable atteinte à partir de c par une avalanche. On s'intéresse plus particulièrement aux configurations que l'on appellera effectives, ce sont les configurations stables atteintes à partir d'une configuration c dans laquelle on a ci ³ di -1 pour tout i >0.

2  Groupe des configurations effectives, configurations remarquables

Pour deux configurations a et b on note c=a+b la configuration donnée par ci = ai +bi. Dans la suite on considère l'opération d'addition des configurations notée Å qui à deux configurations a et b associe la configuration stable r(a+b). Plusieurs configurations particulières jouent un rôle dans ce qui va suivre, il s'agit de la configuration d telle que di = di -1 pour tout i ³ 0, de la configuration 1 dont toutes le valeurs des sommets sont égales à 1 et de la configuration b telle que pour tout i, bi = E(i,0), (bi est le nombre d'arêtes qui joignent i au puits). Enfin pour une configuration c on note c la configuration telle que ci = di-1 -ci, ainsi c + c =c Å c= d.


On peut montrer les résultats suivants
  1. Pour tout couple de configurations effectives a et b, il existe une configuration effective u telle que
    a Å u = b
    Cette configuration est donnée par
    u= b Å
    d Å a
  2. La loi Å muni l'ensemble des configurations effectives d'une structure de groupe abélien fini.

  3. L'identité de ce groupe est la configuration e donnée par e = d Å d Å d

  4. Pour une configuration effective c l'opposée - c est donnée par  :
    - c = d Å
    d Å c
    		Å
    d Å d


  5. Une configuration stable c est effective si et seulement si c Å b = c, de plus dans le calcul de c Å b chaque sommet (sauf le puits) s'éboule exactement une fois.

3  Structure du groupe des états effectifs

On démontre que le nombre de configurations effectives est égal au déterminant de la matrice M de taille n × n obtenue de la façon suivante : les lignes et les colonnes sont indicées par les sommets autres que le puits, le coefficient Mi,i sur la diagonale est égal à di et le coefficient Mi,j est égal à -E(i,j) pour i ¹ j. Le calcul de ce déterminant ne présente pas de difficulté théorique majeure, toutefois les calculs intermédiaires font intervenir des entiers de taille élevée ce qui donne lieu à des débordements de capacité même pour des matrices de taille très petite, il faut donc soit utiliser une bibliothèque de calculs de grands nombres, soit la construire vous même. Cette bibliothèque doit contenir les additions soustractions, multiplications et divisions entières avec reste.




Pour calculer la structure du groupe des états récursifs, on doit effectuer une transformation de la matrice M pour la mettre sous la forme dite de Smith, on démontre en effet que pour toute matrice M à coeffcicients entiers il existe une matrice diagonale A et deux matrices U et V de déterminant égal à 1 et telles que :
M = U A V
de plus les éléments a1, a2, ... , an de la diagonale de A sont tels que ai divise ai+1 pour 1 £ i < n. On montre que l'ordre des groupes cycliques de la décomposition du groupe des états effectifs sont exactement les coefficients de la forme normale de Smith de M.




L'algorithme de mise sous forme normale de Smith est décrit ci-dessous, il utilise la procédure :
Euclide(a,b)

qui à partir de deux entiers a et b donne pour résultat les trois nombres d,u,v tels que (sign(a) désigne -1 si a est négatif et 1 sinon). Au cours de l'algorithme de mise sous forme de Smith, la matrice M est modifiée jusqu'à avoir la forme voulue. On note C_i la i-ème colonne de M et L_i sa i-ème ligne. 
R := Determinant(M);

Pour i := 1 jusqu'a n faire
    debut

    repeter 
        debut
        modif := faux;
        Pour j := i + 1 jusqu'a n faire
            Si (M[i,j) <> 0) Alors
              debut
              (d,u,v) := Euclide (M[i,i],M[i,j]);
              (C_i, C_j) := (u C_i + v C_j, (M[i,i]/d)C_j - (M[i,j]/d)C_i)) (mod R)
              fin;
        Pour j := i + 1 jusqu'a n faire
            Si (M[j,i) <> 0) Alors
              debut
              modif := vrai;
              (d,u,v) := Euclide (M[i,i],M[j,i]);
              (L_i, L_j) := (u L_i + v L_j, (M[i,i]/d)L_j - (M[i,j]/d)L_i)) (mod R)
              fin;
        Si not(modif) et s'il existe un couple p,q tel que 
           (p >i, q> i ) et M[p,q] non divisible par m[i,i] alors
               debut 
               modif := vrai;
               L_i:= L_i + L_p;
               fin;
     jusqu'a modif = faux;

     a[i,i] = pgcd(a[i,i], R);
     R := R/a[i,i];
     fin

4  Calcul de l'arbre recouvrant associé à un état effectif

On peut associer à tout état effectif d'un graphe à puits G= (X,E) un arbre recouvrant en utilisant une construction décrite plus loin (pour la notion d'arbre recouvrant on pourra se reporter au polycopié du tronc commun page 187). La programmation de cet algorithme n'est pas obligatoire, elle peut être considérée comme un complément interessant pour tous, et un substitution possible au calcul de la structure du groupe pour ceux qui n'ont pu résoudre les problèmes de la manipulation des grands entiers.




Etant donné un état effectif c on a vu que dans le calcul de c + b chaque sommet de G s'éboule exactement une fois. Ceci permt de construire une suite de configurations c(i) pour i = 0, ..., p et une partition de l'ensemble des sommets
X = X0 È X1 È ... È Xp

On pose d'abord X0 = {0} et c(0)= c + b, puis X1 = {i| ci(0) ³ di} et c(1) = DX1(c(0))




où la notation DY désigne la composition des Dj pour tous les j appartenant à Y.

Plus généralement on note
Xk = {i| ci(k-1) ³ di } c(k) = DXk(c(k-1))

Pour terminer la construction de l'arbre recouvrant proprement dite on classe les arêtes dont une des extremités est le sommet i du graphe dans une liste d'adjacence; ensuite pour chaque sommet i appartenant à Xk, k >0 on restreint sa liste d'adjacence aux arêtes qui le relient à un sommet qui appartienent à Xk-1 et on retient dans l'arbre la (ci(k-1) -di+1)-eme arête qui figure dans cette liste.

L'ensemble des n arêtes retenues forment l'arbre cherché.
Ce document a été traduit de LATEX par HEVEA.