Théorème de Kirchhoff

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}}}$

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.

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

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}}$ .

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}$.

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.

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}}$.

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].

(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

• Théorie des graphes
• Arbre couvrant
• Cofacteur