Durée : 4 heures

Les calculatrices ne sont pas autorisées.

Le sujet porte sur l'étude de structures combinatoires et algébriques associées aux graphes. La première partie traite de quelques propriétés de la matrice Laplacienne. La seconde partie étudie une structure algébrique naturellement associée à un graphe, son groupe critique. La troisième partie porte sur l'étude d'un système de réécriture sur le graphe qui conduit à une représentation combinatoire du groupe critique. La quatrième et dernière partie est consacrée à des questions de complexité du calcul dans cette représentation.

Le sujet progresse au fil des parties et il est conseillé de les aborder dans l'ordre. Par contre il est bien entendu permis d'utiliser les résultats des questions précédentes sans y avoir répondu.

Un graphe est formé d'un ensemble fini de sommets, qu'on prendra, sauf mention explicte du contraire, égal à , et d'un ensemble de paires non ordonnées de sommets appelées les arêtes. On représente graphiquement un graphe en associant les sommets à des points distincts du plan et en traçant des arcs joignants les paires de sommets qui forment des arêtes. Le graphe avec et est représenté à la figure 1 , ainsi que le graphe cycle et le graphe roue .

L'arête est dite incidente aux sommets et et dans ce cas les sommets et sont dits adjacents. Le degré du ème sommet est le nombre d'arêtes qui lui sont incidentes. La matrice d'incidence d'un graphe à sommets et arêtes est la matrice de taille avec

où on a ordonné les arêtes arbitrairement, par exemple en écrivant chaque arête avec et en utilisant l'ordre lexicographique: si ou si et .

La matrice d'adjacence complétée ou matrice Laplacienne du graphe est la matrice symétrique de taille avec

Pour le graphe de la figure 1 on a

Question 1.1. Montrer que pour tout où désigne la matrice transposée de .

Question 1.2. Montrer que si un réel et un vecteur colonne satisfont alors et en déduire où . Commentez le fait que les valeurs propres de soient réelles positives.

Un chemin de longueur du sommet au sommet du graphe est une suite de sommets avec et telle que pour tout . S'il existe un chemin de à dans on dit que et sont connectés dans . La relation être connectés est
une relation d'équivalence sur les sommets de et on appelle composantes connexes de ses classes d'équivalences. Le graphe est connexe s'il n'a qu'une composante connexe, autrement dit s'il existe un chemin entre toute paire de sommets de .
Question 1.3. Montrer que si le graphe est connexe alors est le sous-espace vectoriel engendré par . En déduire dans ce cas que le rang de est . Plus généralement donner une formule qui lie le rang de au nombre de composantes connexes de .

On va montrer que les résultats précédents restent vrais si on remplace par la matrice dont les lignes sont les lignes de augmentée d'un 0 en colonne et la ligne est une ligne de zéro terminée par un 1 en colonne , et par la matrice formée à partir de en remplaçant la ème ligne et la kème colonne par les kème ligne et ème colonne d'une matrice identité .

Question 1.4. Donner une relation analogue à celle de la question 1 entre et , et une relation analogue à celle de la question 2 entre une valeur propre de et un éventuel vecteur propre non nul. En déduire que si le graphe est connexe alors est de rang .

On note les vecteurs de la base canonique de l'espace vectoriel a toutes ses coordonnées nulles sauf la ème égale à 1 . On pose , le vecteur dont les coordonnées dans la base canonique sont données par la ème ligne de .
Question 1.5. Déduire des résultats précédents que la famille est une famille libre de vecteurs de , quel que soit .

La question suivante est indépendantes des précédentes et termine cette partie préliminaire.
Question 1.6. Soit une matrice carrée inversible et un vecteur, tout deux à coefficients entiers. Notons l'unique solution du système d'équations linéaires . Montrer que le vecteur s'écrit sous la forme avec les , les et entiers et pour tout .

On considère dans tout le reste du sujet un graphe connexe de matrice Laplacienne de taille , telle que définie à la partie précédente. En particulier pour si et 0 sinon, et est le degré du sommet .

Un groupe abélien est un ensemble muni d'une loi interne, notée +, associative, commutative, admettant un élément neutre et telle que chaque élément de ait un inverse. Un sous-groupe de est un sous-ensemble de stable pour la loi interne + et qui forme luimême un groupe. Étant donnés des éléments de , le sous-groupe de engendré par les , noté , est le plus petit sous-groupe de les contenant.

Question 2.1. Montrer que est formé de tous les éléments de qui s'écrivent avec .

On sera attentif à ne pas confondre la notion de sous-groupe engendré par des éléments d'un groupe abélien avec la notion d'espace vectoriel réel engendré par des vecteurs d'un espace vectoriel : dans le premier cas on forme des sommes et différences de vecteurs, qui se réécrivent comme combinaisons linéaires mais à coefficients entiers, alors que le second cas on forme toutes les combinaisons linéaires à coefficients réels.

Par exemple, l'ensemble peut-être vu comme un groupe pour la loi usuelle d'addition des vecteurs, et le sous-ensemble des vecteurs à coordonnées entières en est le sous-groupe engendré par les vecteurs de la base canonique. Ce sous-groupe est bien différent du sous-espace vectoriel engendré par les mêmes vecteurs (qui est tout entier).

On note le sous-groupe de engendré par le vecteur et les pour , définis comme à la partie précédente par .
Question 2.2. Montrer que est engendré par et n'importe quel sous-ensemble de des .

Deux éléments et d'un groupe abélien sont dits équivalents relativement au sous-groupe si .
Question 2.3. Montrer que la relation d'équivalence relativement à un sous-groupe est bien une relation d'équivalence.

L'ensemble des classes d'équivalences pour la relation d'équivalence relativement à un sousgroupe est noté et appelé le quotient de par . La classe d'équivalence de relativement à est notée , ou plus simplement lorsque est clair. Dans chaque classe d'équivalence de relativement à on choisit arbitrairement un élément qu'on appelle le représentant de la classe et on définit la somme de deux classes d'équivalence comme la classe d'équivalence de la somme de leurs représentants.
Question 2.4. Montrer que l'opération de somme décrite ci-dessus munit d'une structure de groupe abélien.

On définit le groupe critique du graphe enraciné en comme le quotient .
Question 2.5. Montrer que est un groupe de cardinal fini.
Deux groupes sont isomorphes (on écrit ) s'il existe un isomorphisme de groupe entre et , c'est-à-dire une bijection de sur telle que .
Question 2.6. Montrer que si est un isomorphisme de groupe entre et , et est un sous-groupe de alors .

Question 2.7. Montrer que pour tout . Indication : on pourra considérer les pour tout , les vecteurs pour et , et l'application pour tout .

Le groupe critique du graphe étant, à isomorphisme près, indépendant de la racine on le note .

On considère toujours un graphe connexe de matrice Laplacienne comme à la partie précédente. On va maintenant étudier un système de réécriture qu'il est commode d'interpréter comme un modèle de tas de sable : des grains de sable sont répartis sur les sommets d'un graphe et se déplacent le long des arêtes selon des règles d'éboulements. L'un des sommets du graphe est appelé le puits, les grains qui y tombent s'y accumulent.

Formellement on définit une configuration du graphe comme un élément de , la ième coordonnée s'interprétant comme le nombre de grains au sommet , le nème sommet représentant le puits. Une configuration est positive si pour tout : le nombre de grains de sable doit être positif en chaque sommet, sauf peut-être dans le puits.

L'éboulement d'un sommet consiste à lui retirer un grain par arête incidente et à distribuer ces grains aux voisins. Plus précisément, étant données deux configurations positives et on écrit s'il existe un tel que (où est défini comme dans la partie précédente), et on dit que est obtenu à partir de par éboulement du sommet . On note la clôture transitive de la relation si et seulement si il existe des configurations telles que et pour tout . Remarquons encore une fois qu'on éboule jamais le puits.
Question 3.1. Montrer que si alors et ont la même image dans le groupe .
On note l'ensemble des sommets à distance du sommet dans le graphe , contient les voisins du sommet les voisins de ces voisins qui ne sont pas déjà dans , etc. On pose et pour le nombre de grains à distance du puits dans la configuration . Le vecteur est appelé potentiel de la configuration . Une configuration positive est dite stable si aucun sommet ne peut s'ébouler : pour tout .
Question 3.2. Montrer que (a) pour toute configuration positive il existe une configuration stable telle que et que (b) cette configuration est unique. Indication : pour (a) on pourra s'appuyer sur la notion de potentiel introduite plus haut.

On appelle avalanche une suite d'éboulements qui se termine par une configuration stable. Une configuration est dite récurrente si elle est stable et s'il existe une configuration positive telle que . Soit la configuration avec pour tous les sommets, on remarque que si est stable alors est positive.
Question 3.3. Montrer les points suivants:
(a). Si et alors .
(b). Pour toute configuration positive il existe un entier et une configuration (non nécessairement stable) telle que et pour tout .
(c). Une configuration stable est récurrente si et seulement s'il existe une configuration positive telle que .
Pour toute paire ( ) de configurations positives on note l'unique configuration stable telle que . Enfin pour toute paire de configurations (non nécessairement positives) on écrit s'il existe un sommet tel que et la clôture transitive de cette relation.
Question 3.4. Montrer que si et sont deux configurations telles que alors il existe une configuration telle que et .

Soit où est la configuration définie précédement.
Question 3.5. Montrer que la configuration est positive et que .
Question 3.6. Montrer qu'une configuration est récurrente si et seulement si .
Question 3.7. Montrer que pour toute configuration il existe une unique configuration récurrente telle que .

Question 3.8. Montrer que l'opération munit l'ensemble des configurations récurrentes de d'une structure de groupe et que le groupe ainsi obtenu est isomorphe à .

Nous avons donc construit une représentation du groupe critique d'un graphe en terme d'éboulements.

On suppose dans cette partie que le graphe connexe sur lequel on étudie le tas de sable a sommets et arêtes. On désigne comme précédement par l'ensemble des sommets à distance du puits, on pose et on note le nombre de grains à distance du puits dans la configuration . On pose de plus (l'ensemble des sommets à distance au moins du puits) et (le nombre de grains à distance au moins du puits).
Question 4.1. Montrer que le nombre total de grains hors du puits dans une configuration stable est majoré par .

Question 4.2. Montrer que deux séquences d'éboulements qui conduisent d'une configuration à une configuration stable font ébouler le même nombre de fois le sommet pour tout : autrement dit, deux séquences d'éboulements complètes ne diffèrent que par l'ordre des éboulements.

Il est donc possible de parler du nombre de sommets éboulés pour passer d'une configuration positive à la configuration stable associée. Remarquons pour simuler efficacement un éboulement sur ordinateur il faudrait, entre autres choses, gérer dynamiquement l'ensemble des sommets éboulables, pour ne pas perdre de temps à les chercher. On se concentre ici sur la complexité intrinsèque du modèle en prenant comme définition de complexité d'une avalanche le nombre d'éboulements qui la compose.

Question 4.3. On considère une configuration ayant grains hors du puits et on l'éboule dans l'ordre suivant:

Montrer que le nombre d'éboulements effectués à l'étape est au plus et en déduire une borne sur la complexité d'une avalanche partant de en fonction de et (autrement dit majorer le nombre d'éboulements de avec stable).

Question 4.4. Appliquer votre borne pour majorer en fonction de et la complexité du test pour déterminer si une configuration stable est récurrente? Même question pour le calcul de pour et récurrentes?

Le test fait intervenir la configuration qui contient au moins grains et qu'il faut avoir calculé au préalable à partir de sa définition. On donne maintenant une caractérisation un peu plus «efficace» des configurations récurrentes. Soit la configuration obtenue par éboulement du puits : pour tous les voisins du puits et .
Question 4.5. Montrer qu'une configuration est recurrente si et seulement si . Montrer de plus que si est récurrent, dans une séquence d'éboulements de à , chaque sommet s'éboule exactement une fois. En déduire un test de recurrence de complexité linéaire.

Nous allons maintenant voir que le test permet d'associer les configurations récurrentes à d'autres structures naturelles sur le graphe.

L'algorithme suivant, appelé algorithme thermique, prend en entrée une configuration stable et effectue les opérations suivantes:

Question 4.6. Montrer que l'algorithme thermique termine et que si la configuration de départ est récurrente les forment une partition des sommets de et les sont des ensembles d'arêtes bien formées (pas de renvoyé par select).

Un sous-graphe d'un graphe est un graphe avec . Un chemin de longueur est un cycle si et . Un cycle est simple si pour tout . Un graphe est une forêt s'il ne contient pas de cycle simple, c'est un arbre s'il est de plus connexe. Un arbre couvrant d'un graphe est un sous-graphe de qui est un arbre.

Question 4.7. Montrer que l'algorithme thermique appliqué à une configuration récurrente construit un ensemble d'arêtes tel que ( ) soit un arbre couvrant du graphe.

Question 4.8. Montrer que deux configurations récurrentes différentes donnent par l'algorithme thermique deux arbres couvrants distincts.

Question 4.9. Montrer réciproquement qu'à tout arbre couvrant ( ) est associée une configuration récurrente qui le redonne par l'algorithme thermique.

Question 4.10. Déduire des questions précédentes que le nombre de configurations récurrentes d'un graphe est égal au nombre de ses arbres couvrants.