Théorème de Kirchhoff

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 quelconque. C'est une généralisation de la formule de Cayley qui donnait ce résultat pour les graphes complets.

Théorème de Kirchhoff[modifier | modifier le code]

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.

Concrètement, pour un graphe G=(V,E)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 t(G) d'arbres couvrants du graphe G est égal, au signe près, à la valeur de n'importe quel cofacteur de L.

Un exemple[modifier | modifier le code]

Ce graphe possède 11 arbres couvrants

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 de Laplace :

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 :

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}

D'après le théorème de Kirchhoff, ~~t(G)=|\det(L^*)|=|-11|=11. Le graphe possède 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 | modifier le code]

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 | modifier le code]

Étape 1[modifier | modifier le code]

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=j, alors m^*_{i,j} compte 1^2 pour des arêtes sortant de v_i et (-1)^2 pour des arêtes arrivant à v_i, donc m^*_{i,j}=deg(v_i). Si i\neq j, alors m^*_{i,j}=-1 si une arête relie v_i à v_j, indépendamment de la direction, et 0 sinon.

On a donc: L=MM^t

Étape 2[modifier | modifier le code]

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œuds, B est 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, et sinon, \det(B) = 0.

Étape 3[modifier | modifier le code]

On obtient M^* 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

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

Application : démontrer la formule de Cayley[modifier | modifier le code]

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.

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

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) John M. Harris, Jeffry L. Hirst, Michael J. Mossinghoff, Combinatorics and Graph Theory (Undergraduate Texts in Mathematics) . Springer; 2nd edition (September 19, 2008).