x
1

Fórmula de Cayley



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 .

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

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 pseudobosques dirigidos.

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.



Escribe un comentario o lo que quieras sobre Fórmula de Cayley (directo, no tienes que registrarte)


Comentarios
(de más nuevos a más antiguos)


Aún no hay comentarios, ¡deja el primero!