Fórmula de Cayley

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Lista completa de todos los árboles con 2,3 y 4 vértices etiquetados: 2^{2-2}=1 árboles con 2 vértices, 3^{3-2}=3 árboles con 3 vértices y 4^{4-2}=16 árboles con 4 vértices.

En teoría de grafos, la fórmula de Cayley es un resultado llamado así en honor a Arthur Cayley, que establece que para cualquier entero positivo n, el número de árboles en n vértices etiquetados es n^{n-2}.

Equivalentemente, la fórmula cuenta el número de árboles de expansión de un grafo completo con vértices etiquetados.

Demostración[editar]

Se conocen muchas demostraciones para esta fórmula. Una demostración clásica utiliza el teorema de Kirchhoff. Las secuencias de Prüfer otorgan una demostración biyectiva de la fórmula de Cayley. Otra demostración biyectiva, de André Joyal, encuentra una demostración uno-a-uno entre árboles de n vértices con dos nodos distinguibles y [pseudobosque]]s dirigidos.

Historia[editar]

La fórmula fue descubierta por Carl Wilhelm Borchardt en 1860, y demostrada a través de un determinante. En una pequeña nota de 1889, Cayley extendió la fórmula en muchas direcciones, tomando en cuenta el grado de los vértices. Aunque Cayley referenció el artículo original de Borchardt, es el nombre de "fórmula de Cayley" el que se convirtió en estándar dentro del campo.

Referencias[editar]