Formule de Cayley

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

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 :

Théorème — Le nombre d'arbres que l'on peut construire sur n sommets numérotés, avec n > 1 est égal à n^{n-2}.

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

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

Cette formule a d'abord été découverte par Karl Wilhelm Borchardt en 1860[réf. nécessaire] et prouvée à l'aide d'un déterminant. Dans une brève note en 1889, 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[modifier | modifier le code]

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.

Article détaillé : Théorème de Kirchhoff.

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

n^n\ =\ \text{Card}\ \left([\![1,n]\!]^{[\![1,n]\!]}\right)\ =\ \text{Card}\ \left(\mathcal{C}_n\times[\![1,n]\!]^2\right)\ =\ n^2\,\text{Card}\ \mathcal{C}_n

.

Article détaillé : Bijection de Joyal.

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

Article détaillé : Codage de Prüfer.

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}\ \mathcal{C}_n n! et n^{n-2} n! arêtes orientées couvrant les n sommets. Il en déduit la formule de Cayley.

Bibliographie[modifier | modifier le code]

  • Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer-Verlag, 1998.
  • (de) Borchardt, C.W., « Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung », Math. Abh. der Akademie der Wissenschaften zu Berlin,‎ 1860, p. 1–20
  • (en) A. Cayley, « A theorem on trees », Quart. J. Math, vol. 23,‎ 1889, p. 376–378 (lire en ligne)
  • (en) Alok Shukla, A short proof of Cayley's Tree Formula, 2009.