Formule de Cayley

En mathématiques, et plus particulièrement en théorie des graphes, la formule de Cayley est un résultat sur les arbres du théoricien Arthur Cayley.

Elle affirme le résultat suivant :

Note : on parle aussi d'arbres décorés ou étiquetés pour dire que l'on identifie les sommets avec des couleurs, des nombres, etc. On parle aussi d'arbres de Cayley.

Liste complète des arbres à 2, 3 et 4 sommets.

Exemple

Pour l'exemple illustré ci-contre, on obtient les résultats suivants, en appliquant le théorème :

• $2^{2-2}=$ 1 arbre avec 2 sommets,
• $3^{3-2}=$ 3 arbres avec 3 sommets,
• $4^{4-2}=$ 16 arbres avec 4 sommets.

Historique

Cette formule a d'abord été découverte par Karl Wilhelm Borchardt en 1860Modèle:Refnec et prouvée à l'aide d'un déterminant. Dans une brève note en 1889, Arthur Cayley a étendu la formule dans plusieurs directions, en tenant compte du degré des sommets. Bien que Cayley ait mentionné le travail de Borchardt, le nom « formule de Cayley » est resté attaché à cette formule.

Démonstrations

On connaît plusieurs preuves remarquables de la formule de Cayley.

Une démonstration classique utilise le théorème de Kirchhoff, un théorème plus puissant qui donne le nombre d'arbres couvrants pour un graphe quelconque, alors que la formule de Cayley ne donne ce nombre que pour les graphes complets. Modèle:Article détaillé

Une démonstration élégante est due à André Joyal. Pour compter les éléments de l'ensemble ${𝒞}_n$ des arbres numérotés à n sommets, il établit une bijection entre ${𝒞}_n\times [[1,n]{]}^2$ et l'ensemble des applications de $[[1,n]]$ dans $[[1,n]]$, noté usuellement $[[1,n]{]}^{[[1,n]]}$. On a ainsi

$n^n=\text{Card}([[1,n]{]}^{[[1,n]]})=\text{Card}({𝒞}_n\times [[1,n]{]}^2)=n^2\text{Card}{𝒞}_n$

.

Une autre démonstration élégante est due à Heinz Prüfer. Le codage de Prüfer établit une bijection de ${𝒞}_n$ vers l'ensemble des (n-2)-uplets à valeurs prises dans l'intervalle $[[1,n]]$, or le cardinal de ce dernier vaut $n^{n-2}$. Modèle:Article détaillé

Une dernière démonstration élégante par double dénombrement a été apportée par Jim Pitman. Il compte de deux façons différentes les suites d'arêtes orientées formant des arbres couvrant les n sommets, et obtient $\text{Card}{𝒞}_{n}n!$ et $n^{n-2}n!$ arêtes orientées couvrant les n sommets. Il en déduit la formule de Cayley. Modèle:Article détaillé

Bibliographie

• Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, 1998.
• Modèle:Article
• Modèle:Article
• Modèle:En Alok Shukla, A short proof of Cayley's Tree Formula, 2009.

Modèle:Portail