On présente ici un résultat important de la théorie des graphes pourtant méconnus des étudiants. Le but de cet exercice est de démontrer le théorème de Kirchhoff, aussi appelé matrix tree theorem. Ce théorème donne une formule pour compter le nombre d’arbres couvrants d’un graphe.
Cet exercice nécessite une bon maîtrise mathématique de la notion de matrice et de déterminant.
Exercice
Soit $G = (S,A)$ un graphe non orienté, avec $n = |S|$ et $m=|A|$. On associe chaque sommet de $S$ à un élément de l’ensemble $\{1,\,\ldots,\,n\}$ et on pose $A = \{a_1,\, \ldots,\, a_m\}$. Enfin, on note $\tau(G)$ le nombre d’arbres couvrants de $G$.
Soit $M$ matrice de $\mathcal{M}_{n}(\mathbb{R})$ et $i,j \leq n$. On note $M_{i,j}$ la valeur de $M$ à la coordonnée $i,j$. On définit $M[i]$ comme la matrice $M$ où on a supprimé la $i$-ème ligne de $M$ et $M[i,j]$ comme la matrice $M$ où on a supprimé la $i$-ème ligne et $j$-ème colonne de $M$.
On considère maintenant $L \in \mathcal{M}_{n}(\mathbb{R})$ la matrice Laplacienne de $G$. Pour rappel, elle est définie ainsi. Pour $i,j \leq n$ :
\[L_{i,j} = \begin{cases} \text{ degré de } i & \text{ si } i = j \\ -1 & \text{ si } (i,j) \in A \\ 0 & \text{ sinon } \end{cases}\]
On pose $B$ la matrice de $\mathcal{M}_{n,m}(\mathbb{R})$ définie pour $x \leq m$, et $(i,j) = a_x$ avec $i \lt j$, par $B_{i,x} = 1$, $B_{j,x} = -1$, et toutes les autres coordonnées sont égales à $0$.
$1.$ Prouver que $L = BB^{T}$.
$2.$ Prouver que pour tout $i$, $L[i,i] = B[i]B[i]^{T}$.
Soit $U$ un ensemble d’arêtes de $A$. On définit $B_U$ comme la matrice $B$ dont on ne garde la colonne $i$ que si $a_i \in U$.
$3.$ Montrer que tout ensemble de $n-1$ arêtes de $G$ forme un arbre couvrant si et seulement si il ne possède pas de cycles.
$4.$ Soit $U \subset A$ de taille $n-1$ tel que $U$ ne forme pas un arbre couvrant. Pour tout $i \leq n$, calculer $\det(B_U[i])$.
$5.$ Soit $U \subset A$ de taille $n-1$ tel que $U$ forme un arbre couvrant. Montrer que pour tout $i$, $\det\left(B_U[i]\right) = \pm 1$.
Donnons la formule de Binet-Cauchy. Soit $C$ et $D$ des matrices de $\mathcal{M}_{n,m}(\mathbb{R})$ et $\mathcal{M}_{m,n}(\mathbb{R})$. Pour tout ensemble $U \subset \{1,\,\ldots,\,m\}$ de $n$ éléments, on note $C_U$ la sous-matrice de $C$ dont on n’a gardé que les colonnes de $U$ et $D_U$ la sous-matrice de $D$ dont on n’a gardé que les lignes de $U$. On a alors l’égalité suivante :
\[\det(CD) = \sum\limits_{U \subset \{1,\,\ldots,\,m\} \atop |U| = n} \det(C_U)\det(D_U)\]
$6.$ En déduire que pour tout $i \leq n$ on a $\det(L[i,i]) = \tau(G)$.
Correction
$1.$ Pour tout $i$, on note $A_i$ l’ensemble des arêtes de $G$ contenant $i$. Soit $M = BB^{T}$. On a :
\begin{align*}
M_{i,i} & = \sum\limits_{x \in A} B_{i,x}B^{T}_{x,i} \\
& = \sum\limits_{x \in A_i} B_{i,x}B^{T}_{x,i} \\
& = \sum\limits_{x \in A} 1 \\
M_{i,i} & = |A_i|
\end{align*}
Ainsi, $M_{i,i}$ est bien égal au degré de $i$ et donc à $L_{i,i}.
Pour $i \neq j$, s’il n’existe pas d’arête $(i,j)$ on a pour toute arête $a \in A$, soit $B_{i,x} = 0$, soit $B_{j,x} = 0$. De ce fait, $M_{i,j} = 0 = L_{i,j}$.
Enfin, si $(i,j) \in A$, on a $B_{i,(i,j)}B_{j,(i,j)} = -1$ et pour tout $a$ de $A$ différent de $(i,j)$, $B_{i,a}B_{j,a} = 0$. Donc $M_{i,j} = -1 = L_{i,j}$.
En conclusion on a donc bien prouvé l’égalité suivante :
\[\boxed{L = BB^{T}}\]
$2.$ Si on considère que les lignes sont indicées par les sommets, on peut écrire : pour tout $j,k$ différents de $i$ on a $L[i,i]_{j,k} = L_{j,k}$. De plus $\displaystyle L_{j,k} = \sum\limits_{x \in A} B_{j,x}B^{T}_{x,k}$. Or pour tout $x$, $B_{j,x} = B[i]_{j,x}$. On a donc bien :
\[\boxed{L[i,i] = B[i]B[i]^{T}}\]
$3.$ Tout d’abord, on rappelle qu’un arbre est un graphe connexe sans cycle. Il ne reste donc qu’à prouver qu’un sous ensemble d’arêtes sans cycle de taille $n-1$ est connexe.
Commençons par préciser que tout arbre couvrant de $G$ a exactement $n-1$ arêtes. Pour s’en convaincre, il suffit d’enraciner l’arbre dans un de ses sommets. Chaque autre sommet possède alors exactement un parent et chaque arête définit une relation parent-enfant. Donc, il y a autant d’arêtes que de parents. De ce fait, il y a exactement $n-1$ arêtes.
Ainsi, si un sous-ensemble sans cycle de $n-1$ arêtes n’est pas connexe, on peut le prolonger en un arbre couvrant de taille strictement supérieure à $n-1$, ce qui n’est pas possible.
De ce fait, tout ensemble de $n-1$ arêtes de $G$ forme un arbre couvrant si et seulement si il ne possède pas de cycles.
$4.$ Si $U$ ne forme pas d’arbre couvrant, par la question précédente, on en déduit que $U$ possède un cycle. Soit $C$ les arêtes traversées dans le cycle de taille minimale de $U$. On s’intéresse à la matrice $B_C[i]$. Pour toute arête $x=(i,j) \in C$ avec $i \lt j$, on pose $\lambda_x$ qui vaut $1$ si notre cycle va de $i$ à $j$ et $-1$ si on parcourt l’arête dans l’autre sens. On note que pour tout $i$ on a :
\[\boxed{\sum\limits_{x \in C}\lambda_xB_{i,x} = 0}\]
En effet, si $i$ est un sommet apparaissant dans notre cycle, il apparaît dans exactement deux arêtes, pour assurer que $C$ soit bien un cycle minimal. Soit $x$ l’arête qui emmène à $i$ et $y$ celle qui en part. On a alors $B_{i,x} = -1$ et $B_{i,y} = 1$. Donc $B_{i,x} + B_{i,y} = 0$. De plus, si $i$ n’apparaît pas dans notre cycle, alors pour tout $x \in C$, $B_{i,x} = 0$.
Ainsi, les colonnes de $B_C$ sont linéairement dépendantes, donc les colonnes de $B_C[i]$ et de $B_U[i]$ aussi. De ce fait, $\displaystyle \boxed{\det(B_U[i]) = 0}$.
$5.$ Pour prouver ce résultat, on procède par récurrence sur $n \geq 2$, le nombre de sommets dans $G$. On pose donc $\mathcal{P}(n) = $ « Pour tout graphe $G$ à $n$ sommets et pour tout sous-ensemble $U$ d’arêtes de $G$ formant un arbre couvrant, on a pour tout sommet $i$, $\det(B_U[i]) = \pm 1$ ».
Pour le cas $n = 2$, on note que $B_U$ est une matrice à une colonne et deux lignes ayant pour termes $\pm 1$. De ce fait, $B_U[i]$ est une matrice de dimension $1$ de valeur $\pm 1$.
On suppose donc que $\mathcal{P}(n)$ est vrai pour $n \geq 2$. Montrons que $\mathcal{P}(n+1)$ est vrai. Soit $G$ un graphe à $n+1$ sommets et $U$ un ensemble de $n$ arêtes de $G$ formant un arbre couvrant. Soit $i$ un sommet de $G$. On considère $B_U[i]$. Soit $a \in S$ une arête de $U$ touchant $i$. Cette arête existe par définition d’arbre couvrant. Dans la colonne de $B_U[i]$ associé à $a$, on a donc un seul élément, ligne $j$, non nul et qui vaut $\pm 1$. On développe alors suivant cette colonne. On a alors :
\[\boxed{\det(B_U[i]) = \pm \det(B_U[i][j,a])}\]
Maintenant, on considère le graphe $G’=(S’,A’)$ dans lequel on a contracté l’arête $a$. C’est à dire, on supprime le sommet $j$ et pour toute arête $(j,k)$, on ajoute l’arête $(i,k)$. On note que le sous graphe $(S’,U’)$ qui correspond à la contraction de l’arête $a$ dans le graphe $(S,U)$, est également un arbre couvrant. De ce fait, on peut appliquer notre hypothèse de récurrence sur $G’$ pour obtenir $\det(B_U[i][j,a]) = \pm 1$. On a donc montré :
\[\boxed{\det(B_U[i]) = \pm 1}\]
$6.$ Soit $i$ un sommet de $G$. On a prouvé que $L[i,i] = B[i]B[i]^{T}$.
Appliquons la formule de Binet-Cauchy sur $\det(B[i]B[i]^{T})$. On note, $T$ l’ensemble des sous-ensembles de taille $n-1$ de $A$ formant un arbre couvrant, et $\bar{T}$ ceux de taille $n-1$ qui contiennent un cycle. On obtient alors :
\begin{align*}
\det(L[i,i]) & = \det(B[i]B[i]^{T}) \\
& = \sum\limits_{\substack{U \subset \{1,\,\ldots,\,m\} \\ |U| = n-1}} \det(B_U[i])\det(B_U[i]^{T}) \\
& = \sum\limits_{\substack{U \subset \{1,\,\ldots,\,m\} \\ |U| = n-1}} \det(B_U[i])^{2} \\
& = \sum\limits_{U \in T} \det(B_U[i])^{2} + \sum\limits_{U \in \bar{T}} \det(B_U[i])^{2} \\
\det(L[i,i]) & = \sum\limits_{U \in T} 1 + \sum\limits_{U \in \bar{T}} 0
\end{align*}
Cela nous permet donc de conclure :
\[\boxed{\det(L[i,i]) = \tau(G)}\]
