Exercice
La formule de Cayley affirme que pour $n \gt 1$, le nombre $C_n$ d’arbres qu’on peut construire sur $n$ sommets est $n^{n-2}$.
Le matrix tree theorem ou théorème de Kirchhoff, déjà présenté en exercice, nous permet de calculer directement cette valeur.
$1)$ Prouver la formule de Cayley à l’aide du Matrix Tree Theorem.
Une autre preuve, due à Jim Pitman, consiste en une preuve par double dénombrement.
On cherche à dénombre de deux façons différentes le nombre $D_n$ de façon d’ajouter consécutivement $n-1$ arêtes orientées au graphe nul à $n$ sommets : le graphe $G_n$ à $n$ sommets sans arêtes.
On commence par un dénombrement à partir d’arbres orientés.
$2)$ À partir d’un arbre non orienté sur $n$ sommets, expliquer comment obtenir un arbre orienté.
$3)$ En déduire une méthode en partant d’un arbre non orienté pour trouver plusieurs manières d’ajouter $n-1$ arêtes orientées à $G_n$.
$4)$ Montrer qu’utiliser cette méthode à partir de tous les arbres non orientés permet d’obtenir chaque construction possible une et une seule fois.
$5)$ Exprimer $D_n$ en fonction de $C_n$ et $n$.
On effectue maintenant un comptage directe.
$6)$ Combien compte-t-on de composante connexes après avoir ajouté $k \lt n$ arêtes à $G_n$ ?
$7)$ Après avoir ajouté $k \lt n-1 $ arêtes à $G_n$, combien de possibilité reste-t-il pour placer la prochaine ?
$8)$ En déduire une expression de $D_n$ ne dépendant que de $n$.
$9)$ Calculer $C_n$.
Correction
$1.$ Le nombre d’arbres non-orientés pouvant être construits sur $n$ sommets correspond au nombre d’arbre couvrant du graphe complet à $n$ sommets. Soit $L$ la matrice de dimension $n-1 \times n-1$ avec des $n-1$ sur la diagonale, et des $-1$ partout ailleurs. On a donc par le théorème de Kirchhoff :
\[C_n = \det\left(L\right)\]
\[C_n = \begin{vmatrix} n-1 & -1 & -1 & \cdots & -1 \\ -1 & n-1 & -1 & \cdots & -1 \\ \vdots & -1 & -1 & n-1 & \dots & -1\\ \vdots & \ddots & \ddots & \vdots \\ -1 & -1 & -1 & \cdots & n-1\end{vmatrix}\]
On soustrait à chaque colonne autre que la première la première colonne :
\[C_n = \begin{vmatrix} n-1 & -n & -n & \cdots & -n \\ -1 & n & 0 & \cdots & 0\\ -1 & 0 & n & \ldots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ -1 & 0 & 0 & \cdots & n\end{vmatrix}\]
On ajoute maintenant à la première ligne les $n-2$ suivantes.
\[C_n = \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 \\ -1 & n & 0 & \cdots & 0\\ -1 & 0 & n & \ldots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ -1 & 0 & 0 & \cdots & n\end{vmatrix}\]
En développant par rapport à la première ligne, on obtient bien :
\[C_n = n^{n-2}\]
$2.$ Un arbre composé d’arêtes orientées est un arbre enraciné. Ainsi, en partant d’un arbre non orienté, choisir un de ses sommets comme racine suffit à définir un arbre orienté.
$3.$ En partant d’un arbre non-orienté, on commence par l’enraciner, puis on choisit l’ordre d’insertion des arêtes. Cela nous donne une façon de construire un arbre orienté à partir de $G_n$ en ajoutant successivement les arêtes.
$4.$ On commence par noter qu’à partir d’un même arbre, toutes les constructions obtenues sont distinctes. De plus, si on supprime l’orientation des arêtes de l’arbre obtenu, on retrouve l’arbre de départ. De ce fait, toutes nos constructions sont distinctes. Enfin, si on considère une construction, on note qu’on peut l’obtenir à partir de l’arbre final auquel on a supprimé l’orientation. Ainsi, nous obtenons bien toutes les constructions une et une seule fois.
$5.$ Pour chaque arbre, on dispose de $n$ choix possible pour la racine. De plus, il existe $(n-1)!$ ordre différents pour la sélection des arêtes. Autrement dit $\displaystyle D_n = C_n n!$.
$6.$ On note que $G_n$ comporte $n$ composantes connexes distincts, tous composés d’un unique sommet. À la fin de la construction, il nous reste plus qu’un arbre. De plus, ajouter une arête diminue au plus le nombre de composantes de $1$. Or, on ajoute $n-1$ arêtes. Il en résulte qu’après avoir ajouté $k \lt n$ arêtes, il reste $n-k$ composantes connexes.
$7.$ On rappel qu’un arbre enraciné, est un graphe acyclique tel que tous les sommets sauf un ont un degré entrant de $1$. Lors de notre construction, on doit donc conserver le caractère acyclique et que chaque sommet ait au plus $1$ parents.
Ainsi, après avoir placé $k \lt n-1$ arêtes dans $G$, on dispose de $n-k$ composante connexe. Chacune de ces composante connexes possède un unique élément sans arête entrante. En effet, tous les sommets ont degré entrant au plus $1$ et pour assurer la connexité, la composante est constitué d’au moins autant d’arête que le nombre de sommets moins un.
De ce fait, pour ajouter une arête, on peut sélectionner n’importe quel sommet comme parent, et pour l’enfant, on doit nécessairement sélectionner une autre composante connexe. Or dans chaque autre composante connexe, il existe un unique sommet ayant degré entrant nul. De ce fait, pour chaque sommet, on peut le connecter à exactement $n-k-1$ arêtes.
Autrement dit, après avoir placé $k$ arêtes, il y a $n(n-k-1)$ possibilités pour sélectionner la prochaine arête.
$8.$ On peut donc exprimer $D_n$ sous forme d’un produit.
\[D_n = \prod\limits_{k=0}^{n-2} n(n-k-1)\]
On sort les $n$ du produit.
\[D_n = n^{n-1}\prod\limits_{k=0}^{n-2} (n-1-k) \]
Donc on reconnaît l’expression de la factorielle. Ce qui nous permet donc d’exprimer $D_n$.
\[D_n = n^{n-1}(n-1)!\]
$9.$ On réunit donc les deux formules de $D_n$.
\[C_n n! = n^{n-1}(n-1)!\]
Ce qui nous donne donc bien :
\[C_n = n^{n-2}\]