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é modifier

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 $G=(V,E)$ où $V=\{v_{1},\cdots ,v_{n}\}$ , la matrice laplacienne est définie par :

$(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 $G$ est égal, au signe près, à la valeur de n'importe quel cofacteur de $L$ .

Exemple modifier

Ce graphe possède 11 arbres couvrants

Calcul de la matrice laplacienne modifier

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 :

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 modifier

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 :

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 $\det(L^{*})=-11$ . D'après le théorème de Kirchhoff, il y a 11 arbres couvrants.

Vérification modifier

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 modifier

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 modifier

Étape 1 modifier

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

$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 $M^{*}=MM^{t}$ : il correspond au produit scalaire de deux lignes de $M$ .

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

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

Étape 2 modifier

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

Le sous-graphe correspondant à $B$ contient donc $n$ nœuds et $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 $B$ sera nulle, et donc le déterminant de $B$ sera nul lui aussi.

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

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

Étape 3 modifier

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

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

où ${\mathcal {H}}$ représente les sous-matrices $(n-1)\times (n-1)$ de $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 modifier

La formule de Cayley modifier

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 $K_{n}$ possède $n^{n-2}$ arbres couvrants.

Démonstration

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

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 $n-1\times n-1$ de la forme :

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 $L_{n-1\times n-1}^{*}$ , on soustrait à chaque colonne $C_{i}$ de celui-ci la première colonne $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 :

\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 $L_{1}$ toutes les autres lignes $L_{i}$ . On sait en effet que le déterminant est invariant par somme de lignes. On obtient :

\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 $n-2$ fois le nombre $n$ , on obtient le résultat $t(K_{n})=n^{n-2}$ .

Génération aléatoire et algorithmique modifier

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 modifier

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 modifier

↑ ^{a et b} (en) Shayan Oveis Gharan, « Recent Advances in Approximation Algorithms : Random Spanning Trees », sur Université de Washington, 2015.

Voir aussi modifier

Bibliographie modifier

(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 modifier

Portail des mathématiques

[washington-1] {a et b} (en) Shayan Oveis Gharan, « Recent Advances in Approximation Algorithms : Random Spanning Trees », sur Université de Washington, 2015.

[1]