Théorème de Kirchhoff

Dans le domaine de la théorie des graphes, le théorème de Kirchhoff, aussi appelé matrix-tree theorem, nommé d'après le physicien Gustav Kirchhoff, est un théorème donnant le nombre exact d'arbres couvrants pour un graphe non orienté quelconque. C'est une généralisation de la formule de Cayley qui donne ce résultat pour les graphes complets non orientés.

Énoncé

Le théorème de Kirchhoff s'appuie sur la notion de matrice laplacienne, définie elle-même comme la différence entre la matrice des degrés et la matrice d'adjacence du graphe. Formellement, pour un graphe ${\displaystyle G=(V,E)}$ où ${\displaystyle V=\{v_{1},\cdots ,v_{n}\}}$, la matrice laplacienne est définie par :

${\displaystyle (L)_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{si }}i=j\\-1&{\mbox{si }}i\neq j{\mbox{ et }}(v_{i},v_{j})\in E\\0&{\mbox{sinon}}\end{matrix}}\right.}$

Le théorème de Kirchhoff s'énonce ainsi :

Théorème — Le nombre d'arbres couvrants du graphe ${\displaystyle G}$ est égal, au signe près, à la valeur de n'importe quel cofacteur de ${\displaystyle L}$.

Exemple

Ce graphe possède 11 arbres couvrants

Calcul de la matrice laplacienne

On calcule d'abord la matrice laplacienne de ce graphe :

• Le sommet 1 est de degré 2 et il est relié aux sommets 2 et 5 : la première colonne vaut (2, -1, 0, 0, -1, 0).
• Le sommet 2 est de degré 3 et il est relié aux sommets 1, 3 et 5 : la deuxième colonne vaut (-1, 3, -1, 0, -1, 0).
• Le sommet 3 est de degré 2 et il est relié aux sommets 2 et 4 : la troisième colonne vaut (0, -1, 2, -1, 0, 0).
• Le sommet 4 est de degré 3 et il est relié aux sommets 3, 5 et 6 : la quatrième colonne vaut (0, 0, -1, 3, -1, -1).
• Le sommet 5 est de degré 3 et il est relié aux sommets 1, 2 et 4 : la cinquième colonne vaut (-1, -1, 0, -1, 3, 0).
• Le sommet 6 est de degré 1 et il est relié au sommet 4 : la sixième colonne vaut (0, 0, 0, -1, 0, 1).

Cela donne la matrice laplacienne :

${\displaystyle L={\begin{pmatrix}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{pmatrix}}}$

Calcul d'un des cofacteurs

On supprime ensuite n'importe quelle ligne et n'importe quelle colonne de la matrice. Si l'on supprime par exemple la troisième colonne et la deuxième ligne :

${\displaystyle L^{*}={\begin{pmatrix}2&-1&0&-1&0\\0&-1&-1&0&0\\0&0&3&-1&-1\\-1&-1&-1&3&0\\0&0&-1&0&1\\\end{pmatrix}}}$

Le cofacteur est ${\displaystyle \det(L^{*})=-11}$. D'après le théorème de Kirchhoff, il y a 11 arbres couvrants.

Vérification

Le graphe possède en effet 11 arbres couvrants, ce que l'on peut effectivement constater dans la figure suivante :

Les 11 arbres couvrant le graphe de départ

Cas des graphes non connexes

Si le graphe de départ n'est pas connexe, alors la matrice laplacienne sera diagonale par bloc. En supprimant une ligne et une colonne, il y aura au moins une composante connexe pour laquelle aucune colonne n'aura été supprimée. La somme des colonnes de cette composante est alors nulle, donc tout cofacteur est nul. On retrouve bien le fait que seuls les graphes connexes ont des arbres couvrants.

Démonstration

Étape 1

Soit ${\displaystyle D}$ une orientation quelconque de ${\displaystyle G}$, et ${\displaystyle M}$ la matrice d'incidence associée: si ${\displaystyle G}$ a ${\displaystyle n}$ nœuds et ${\displaystyle m}$ arêtes, alors ${\displaystyle M}$ est une matrice à ${\displaystyle n}$ lignes et ${\displaystyle m}$ colonnes dont le terme général est défini par:

${\displaystyle m_{i,j}:=\left\{{\begin{matrix}1&{\mbox{si }}v_{i}{\mbox{ est la queue de }}e_{j}\\-1&{\mbox{si }}v_{i}{\mbox{ est la tête de }}e_{j}\\0&{\mbox{si }}v_{i}\notin e_{j}\end{matrix}}\right.}$

Calculons le terme général de ${\displaystyle M^{*}=MM^{t}}$: il correspond au produit scalaire de deux lignes de ${\displaystyle M}$.

1. Si ${\displaystyle i\neq j}$, alors ${\displaystyle m_{i,j}^{*}=\sum _{k=1}^{n}m_{i,k}m_{j,k}=-1}$ si une arête ${\displaystyle e_{k}}$ relie ${\displaystyle v_{i}}$ à ${\displaystyle v_{j}}$, indépendamment de la direction, et ${\displaystyle m_{i,j}^{*}=0}$ sinon.
2. Si ${\displaystyle i=j}$, alors ${\displaystyle m_{i,j}^{*}=m_{i,i}^{*}=\sum _{k=1}^{n}m_{i,k}^{2}}$ compte ${\displaystyle 1^{2}}$ pour des arêtes sortant de ${\displaystyle v_{i}}$ et ${\displaystyle (-1)^{2}}$ pour des arêtes arrivant à ${\displaystyle v_{i}}$, donc ${\displaystyle m_{i,i}^{*}=deg(v_{i})}$.

Finalement, on a : ${\displaystyle L=MM^{t}}$ .

Étape 2

On ne considère que les graphes connexes, ce qui assure ${\displaystyle m\geq n-1}$. On considère alors ${\displaystyle B}$ une sous-matrice carrée ${\displaystyle (n-1)\times (n-1)}$ de ${\displaystyle M}$.

Le sous-graphe correspondant à ${\displaystyle B}$ contient donc ${\displaystyle n}$ nœuds et ${\displaystyle n-1}$ arêtes, donc soit c'est un arbre couvrant, soit il contient un cycle. S'il contient un cycle, alors la somme des colonnes correspondantes dans ${\displaystyle B}$ sera nulle, et donc le déterminant de ${\displaystyle B}$ sera nul lui aussi.

S'il ne contient pas de cycle, c'est un arbre couvrant ${\displaystyle T}$, qui contient au moins deux feuilles. ${\displaystyle B}$ a donc au moins une ligne correspondant à une feuille, donc une ligne contenant ${\displaystyle n-2}$ termes nuls et un terme égal à ${\displaystyle 1}$ ou ${\displaystyle -1}$. En développant le déterminant de ${\displaystyle B}$ par rapport à cette ligne, on obtient donc une relation de récurrence sur le nombre de nœuds ${\displaystyle n}$ du graphe. Si le graphe a un seul nœud, ${\displaystyle B}$ est la matrice vide de déterminant ${\displaystyle 1}$ par convention, donc quelle que soit la valeur de ${\displaystyle n}$, si ${\displaystyle B}$ représente un arbre couvrant ${\displaystyle T}$, ${\displaystyle \det(B)=\pm 1}$.

En résumé, soit le sous-graphe contient un cycle et dans ce cas ${\displaystyle \det(B)=0}$, soit le sous-graphe représente un arbre couvrant et dans ce cas ${\displaystyle \det(B)=\pm 1}$.

Étape 3

Soit ${\displaystyle M^{*}}$ obtenue en supprimant une ligne quelconque de ${\displaystyle M}$. Le déterminant de ${\displaystyle M^{*}(M^{*})^{t}}$ est donc un cofacteur de ${\displaystyle L}$, au signe près. Par la formule de Binet-Cauchy, on obtient :

${\displaystyle {\mbox{Cofacteur}}(L)=\sum _{B\in {\mathcal {H}}}(\det(B))^{2}}$

où ${\displaystyle {\mathcal {H}}}$ représente les sous-matrices ${\displaystyle (n-1)\times (n-1)}$ de ${\displaystyle M^{*}}$. D'après l'étape 2, les termes de la somme valent 1 pour chaque arbre couvrant, et 0 sinon, ce qui termine la démonstration.

Applications

La formule de Cayley

Le théorème de Kirchhoff permet de donner une démonstration rapide de la formule de Cayley. Cette dernière indique que le graphe complet ${\displaystyle K_{n}}$ possède ${\displaystyle n^{n-2}}$ arbres couvrants.

Démonstration

La matrice laplacienne d'un graphe complet à n sommets est une matrice ${\displaystyle n\times n}$ de la forme :

${\displaystyle L_{n\times n}={\begin{pmatrix}n-1&-1&-1\\-1&\ddots &-1\\-1&-1&n-1\\\end{pmatrix}}}$

On peut par exemple supprimer la première ligne et la première colonne, on obtient donc une matrice ${\displaystyle n-1\times n-1}$ de la forme :

${\displaystyle L_{n-1\times n-1}^{*}={\begin{pmatrix}n-1&-1&-1\\-1&\ddots &-1\\-1&-1&n-1\\\end{pmatrix}}}$

Pour faciliter le calcul du déterminant de ${\displaystyle L_{n-1\times n-1}^{*}}$, on soustrait à chaque colonne ${\displaystyle C_{i}}$ de celui-ci la première colonne ${\displaystyle C_{1}}$.à partir de la deuxième colonne. On sait en effet que le déterminant est invariant par différence de colonnes. On obtient :

${\displaystyle \det(L_{n-1\times n-1}^{*})={\begin{vmatrix}n-1&-n&-n&\cdots &-n&-n\\-1&n&0&\cdots &0&0\\-1&0&n&\cdots &0&0\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\-1&0&0&\cdots &n&0\\-1&0&0&\cdots &0&n\\\end{vmatrix}}}$

On ajoute ensuite à la première ligne ${\displaystyle L_{1}}$ toutes les autres lignes ${\displaystyle L_{i}}$. On sait en effet que le déterminant est invariant par somme de lignes. On obtient :

${\displaystyle \det(L_{n-1\times n-1}^{*})={\begin{vmatrix}1&0&0&\cdots &0&0\\-1&n&0&\cdots &0&0\\-1&0&n&\cdots &0&0\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\-1&0&0&\cdots &n&0\\-1&0&0&\cdots &0&n\\\end{vmatrix}}}$

Ainsi, en développant par rapport à la première ligne, et en constatant que la diagonale contient ${\displaystyle n-2}$ fois le nombre ${\displaystyle n}$, on obtient le résultat ${\displaystyle t(K_{n})=n^{n-2}}$.

Génération aléatoire et algorithmique

Le théorème de Kirchoff est utilisé pour générer des arbres couvrants de façon probabiliste. Certains algorithmes probabilistes utilisent ensuite ces arbres^[1].

Histoire

Le théorème de Kirchoff est l'une des premières applications de la matrice laplacienne d'un graphe^[1]. Cet objet est maintenant très utilisé, notamment en théorie spectrale des graphes.

Notes et références

1. (en) Shayan Oveis Gharan, « Recent Advances in Approximation Algorithms : Random Spanning Trees », sur Université de Washington, 2015.

Voir aussi

Bibliographie

(en) John M. Harris, Jeffry L. Hirst et Michael J. Mossinghoff, Combinatorics and Graph Theory, New York, Springer, coll. « Undergraduate Texts in Mathematics », 19 septembre 2008, 2^e éd., 381 p. (ISBN 978-0-387-79711-3, lire en ligne), p. 47-50

Articles connexes

• Théorie des graphes
• Arbre couvrant
• Cofacteur