ENS Informatique Fondamentale (Maths Info) MP 2009Sujet et corrigé

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 G est formé d'un ensemble fini X de sommets, qu'on prendra, sauf mention explicte du contraire, égal à X_n = {1, …, n}, et d'un ensemble E 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 G_0 = (X, E) avec X = {1, 2, 3, 4, 5} et E = {{1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {3, 5}} est représenté à la figure 1 , ainsi que le graphe cycle C_6 et le graphe roue W_5.

L'arête {i, j} est dite incidente aux sommets i et j et dans ce cas les sommets i et j sont dits adjacents. Le degré d_i du i ème sommet est le nombre d'arêtes qui lui sont incidentes. La matrice d'incidence d'un graphe G = (X, E) à n sommets et m arêtes est la matrice L_G = (ℓ_(i, j)) de taille n × m avec

où on a ordonné les arêtes arbitrairement, par exemple en écrivant chaque arête (i, j) avec i < j et en utilisant l'ordre lexicographique: (i, j) < (k, ℓ) si i < k ou si (i = k et j < ℓ).

La matrice d'adjacence complétée ou matrice Laplacienne du graphe G est la matrice symétrique Δ_G = (e_(i, j)) de taille n × n avec

Pour le graphe G_0 de la figure 1 on a

Question 1.1. Montrer que pour tout G, Δ_G = L_G^t L_G où ^t L_G désigne la matrice transposée de L_G.

Question 1.2. Montrer que si un réel λ et un vecteur colonne v ≠ 0 satisfont Δ_G v = λv alors λ = ‖^t L_G v‖^2/‖v‖^2 et en déduire λ = ∑_({i, j} ∈ E)(v_i − v_j)^2/∑_i v_i^2 où v = (v_i)_(i = 1)^n. Commentez le fait que les valeurs propres de Δ_G soient réelles positives.

Un chemin de longueur k du sommet x au sommet y du graphe G est une suite u_0, u_1, …, u_k de sommets avec u_0 = x, u_k = y et telle que {u_(i − 1), u_i} ∈ E pour tout i = 1, …, k. S'il existe un chemin de x à y dans G on dit que x et y sont connectés dans G. La relation être connectés est
une relation d'équivalence sur les sommets de G et on appelle composantes connexes de G ses classes d'équivalences. Le graphe G est connexe s'il n'a qu'une composante connexe, autrement dit s'il existe un chemin entre toute paire de sommets de G.
Question 1.3. Montrer que si le graphe G est connexe alors ker(Δ_G) = {v|Δ_G v = 0} est le sous-espace vectoriel engendré par e = ^t(1, …, 1). En déduire dans ce cas que le rang de Δ_G est n − 1. Plus généralement donner une formule qui lie le rang de Δ_G au nombre de composantes connexes de G.

On va montrer que les résultats précédents restent vrais si on remplace L_G par L_(G, k) la matrice n × (m + 1) dont les lignes i ≠ k sont les lignes de L_G augmentée d'un 0 en colonne m + 1 et la ligne k est une ligne de zéro terminée par un 1 en colonne m + 1, et Δ_G par Δ_(G, k) la matrice n × n formée à partir de Δ_G en remplaçant la k ème ligne et la kème colonne par les kème ligne et k ème colonne d'une matrice identité n × n.

Question 1.4. Donner une relation analogue à celle de la question 1 entre L_(G, k) et Δ_(G, k), et une relation analogue à celle de la question 2 entre une valeur propre λ de Δ_(G, k) et un éventuel vecteur propre v non nul. En déduire que si le graphe G est connexe alors Δ_(G, k) est de rang n.

On note x_1, …, x_n les n vecteurs de la base canonique de l'espace vectoriel ℝ^n : x_i a toutes ses coordonnées nulles sauf la i ème égale à 1 . On pose Δ_i = d_i x_i + ∑_(j ≠ i)e_(i, j)x_j, le vecteur dont les coordonnées dans la base canonique sont données par la i ème ligne de Δ_G.
Question 1.5. Déduire des résultats précédents que la famille {Δ_1, …, Δ_n}∖{Δ_k} ∪ {x_k} est une famille libre de vecteurs de ℝ^n, quel que soit k.

La question suivante est indépendantes des précédentes et termine cette partie préliminaire.
Question 1.6. Soit A une matrice carrée n × n inversible et a un vecteur, tout deux à coefficients entiers. Notons v l'unique solution du système d'équations linéaires Av = a. Montrer que le vecteur v s'écrit sous la forme (v_1^′/δ + v_1^(′′), …, v_n^′/δ + v_n^(′′)) avec les v_i^′, les v_i^(′′) et δ entiers et 0 ≤ v_i^′ < δ pour tout i.

On considère dans tout le reste du sujet un graphe connexe G = (X_n, E) de matrice Laplacienne Δ_G = (e_(i, j)) de taille n × n, telle que définie à la partie précédente. En particulier pour i ≠ j, e_(i, j) = − 1 si {i, j} ∈ E et 0 sinon, et d_i = e_(i, i) est le degré du sommet i.

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

Question 2.1. Montrer que ⟨g_1, …, g_k⟩ est formé de tous les éléments de K qui s'écrivent ∑_(i = 1)^k a_i g_i avec a_i ∈ ℤ.

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 ℝ^n peut-être vu comme un groupe pour la loi usuelle d'addition des vecteurs, et le sous-ensemble ℤ^n des vecteurs à coordonnées entières en est le sous-groupe ⟨x_1, …, x_n⟩ engendré par les vecteurs de la base canonique. Ce sous-groupe ℤ^n est bien différent du sous-espace vectoriel engendré par les mêmes vecteurs x_1, …, x_n (qui est ℝ^n tout entier).

On note Δ(G, k) le sous-groupe de ℤ^n engendré par le vecteur x_k et les Δ_i pour i = 1, …, n, définis comme à la partie précédente par Δ_i = d_i x_i + ∑_(j ≠ i)e_(i, j)x_j.
Question 2.2. Montrer que Δ(G, k) est engendré par x_k et n'importe quel sous-ensemble de n − 1 des Δ_i.

Deux éléments x et y d'un groupe abélien K sont dits équivalents relativement au sous-groupe H si x − y ∈ H.
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é K/H et appelé le quotient de K par H. La classe d'équivalence de x relativement à H est notée x_(/H), ou plus simplement x¯ lorsque H est clair. Dans chaque classe d'équivalence de K relativement à H 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 K/H d'une structure de groupe abélien.

On définit le groupe critique C(G, k) du graphe G enraciné en k comme le quotient ℤ^n/Δ(G, k).
Question 2.5. Montrer que C(G, k) est un groupe de cardinal fini.
Deux groupes K, K^′ sont isomorphes (on écrit K ∼ K^′ ) s'il existe un isomorphisme de groupe entre K et K^′, c'est-à-dire une bijection φ de K sur K^′ telle que φ(x + y) = φ(x) + φ(y).
Question 2.6. Montrer que si φ est un isomorphisme de groupe entre K et K^′, et H est un sous-groupe de K alors K/H ∼ K^′/φ(H).

Question 2.7. Montrer que C(G, k) ∼ C(G, ℓ) pour tout k, ℓ. Indication : on pourra considérer les Δ_i^′ = Δ_i − e_(i, k)x_ℓ pour tout i, les vecteurs y_i = x_i − x_k pour i ≠ k et y_k = − x_ℓ, et l'application φ(x_i) = y_i pour tout i.

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

On considère toujours un graphe connexe G = (X_n, E) de matrice Laplacienne Δ_G 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 ℤ^n, la ième coordonnée s'interprétant comme le nombre de grains au sommet i, le nème sommet représentant le puits. Une configuration u = (u_i)_(1 ≤ i ≤ n) est positive si u_i ≥ 0 pour tout i = 1, …, n − 1 : 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 u et v on écrit u → v s'il existe un i ≤ n − 1 tel que v = u − Δ_i (où Δ_i est défini comme dans la partie précédente), et on dit que v est obtenu à partir de u par éboulement du sommet i. On note → ^∗ la clôture transitive de la relation →:u → ^∗ v si et seulement si il existe des configurations u^0, …, u^p telles que u^0 = u, u^p = v et u^i → u^(i + 1) pour tout 0 ≤ i ≤ p. Remarquons encore une fois qu'on éboule jamais le puits.
Question 3.1. Montrer que si u → ^∗ v alors u et v ont la même image dans le groupe C(G, n).
On note S_k l'ensemble des sommets à distance k du sommet n dans le graphe G : S_0 = {n}, S_1 contient les voisins du sommet n, S_2 les voisins de ces voisins qui ne sont pas déjà dans S_0 ∪ S_1, etc. On pose ℓ = max(i|S_i ≠ ∅) et pour k ≤ ℓ, μ_k(u) = ∑_(i ∈ S_k)u_i le nombre de grains à distance k du puits dans la configuration u. Le vecteur μ(u) = (μ_0(u), …, μ_ℓ(u)) est appelé potentiel de la configuration u. Une configuration positive u est dite stable si aucun sommet ne peut s'ébouler : u_i ≤ d_i pour tout i ≤ n − 1.
Question 3.2. Montrer que (a) pour toute configuration positive u il existe une configuration stable v telle que u → ^∗ v 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 u est dite récurrente si elle est stable et s'il existe une configuration positive v ≠ 0 telle que u + v → ^∗ u. Soit δ la configuration avec δ_i = d_i pour tous les sommets, on remarque que si u est stable alors δ − u est positive.
Question 3.3. Montrer les points suivants:
(a). Si u → ^∗ u^′ et v → ^∗ v^′ alors u + v → ^∗ u^′ + v^′.
(b). Pour toute configuration positive v ≠ 0 il existe un entier k et une configuration w (non nécessairement stable) telle que kv → ^∗ w et w_i > 0 pour tout 1 ≤ i ≤ n − 1.
(c). Une configuration stable u est récurrente si et seulement s'il existe une configuration positive u^′ telle que u^′ + δ → ^∗ u.
Pour toute paire ( u, v ) de configurations positives on note u ⊕ v l'unique configuration stable telle que u + v → ^∗ u ⊕ v. Enfin pour toute paire de configurations (non nécessairement positives) on écrit u ⟹ v s'il existe un sommet i ≤ n − 1 tel que v = u − Δ_i et ⟹ ^∗ la clôture transitive de cette relation.
Question 3.4. Montrer que si u et v sont deux configurations telles que u − v ∈ ⟨Δ_1, …, Δ_n⟩ alors il existe une configuration w telle que w ⟹ ^∗ u et w ⟹ ^∗ v.

Soit ε = 2δ − (δ ⊕ δ) 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 u est récurrente si et seulement si u + ε → ^∗ u.
Question 3.7. Montrer que pour toute configuration u il existe une unique configuration récurrente v telle que u − v ∈ ⟨Δ_1, Δ_2, …, Δ_n⟩.

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

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 G sur lequel on étudie le tas de sable a n sommets et m arêtes. On désigne comme précédement par S_i l'ensemble des sommets à distance i du puits, on pose ℓ = max(i|S_i ≠ ∅) et on note μ_i(u) le nombre de grains à distance i du puits dans la configuration u. On pose de plus S_(> i) = ⋃_(j > i)S_j (l'ensemble des sommets à distance au moins i + 1 du puits) et μ_(≥ i)(u) = ∑_(j ≥ i)μ_j(u) (le nombre de grains à distance au moins i du puits).
Question 4.1. Montrer que le nombre total de grains hors du puits dans une configuration stable est majoré par 2m.

Question 4.2. Montrer que deux séquences d'éboulements qui conduisent d'une configuration u à une configuration stable v font ébouler le même nombre de fois le sommet i pour tout i : 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 u ayant p grains hors du puits et on l'éboule dans l'ordre suivant:

Montrer que le nombre d'éboulements effectués à l'étape i est au plus μ_(≥ i) ⋅ |S_(> i)| et en déduire une borne sur la complexité d'une avalanche partant de u en fonction de ℓ, n et p (autrement dit majorer le nombre d'éboulements de u → ^∗ v avec v stable).

Question 4.4. Appliquer votre borne pour majorer en fonction de ℓ, n et m la complexité du test u + ε → ^∗ u pour déterminer si une configuration stable est récurrente? Même question pour le calcul de u ⊕ v pour u et v récurrentes?

Le test u + ε → ^∗ u fait intervenir la configuration ε qui contient au moins 2m 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 β = − Δ_n la configuration obtenue par éboulement du puits : β_i = 1 pour tous les voisins du puits et β_n = − d_n.
Question 4.5. Montrer qu'une configuration est recurrente si et seulement si u + β → ^∗ u. Montrer de plus que si u est récurrent, dans une séquence d'éboulements de u + β à u, 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 u + β → ^∗ u 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 u et effectue les opérations suivantes:
− u^((0)) = u + β; R_(− 1) = {n}; i:=0

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

Un sous-graphe d'un graphe G = (X, E) est un graphe G = (X, E^′) avec E^′ ⊂ E. Un chemin u_0, …, u_k de longueur k est un cycle si u_0 = u_k et k ≥ 2. Un cycle est simple si pour tout 0 ≤ i < j ≤ k − 1, u_i ≠ u_j. 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 G = (X, E) est un sous-graphe T = (X, A) de G qui est un arbre.

Question 4.7. Montrer que l'algorithme thermique appliqué à une configuration récurrente construit un ensemble d'arêtes A tel que ( X, A ) 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 ( X, A ) 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.