Loading AI tools
De Wikipedia, la enciclopedia libre
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.