Teorema del número de árboles de Cayley

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de enero de 2022; la verificación requiere 1 edición .

El teorema del número de árboles de Cayley es un teorema que establece que el número de árboles con vértices numerados es . $norte$ $n^{{n-2}}$

Historia

El teorema lleva el nombre de Arthur Cayley , quien lo demostró en 1889. [1] Cayley mismo admitió que la misma afirmación había sido probada anteriormente por Carl Borchard y en una formulación equivalente incluso antes en un artículo de 1857 de James Joseph Sylvester . [2]

En su artículo, Cayley prueba esencialmente una declaración más general. Si abres los paréntesis de la expresión

{(x_{1}+\puntos +x_{n})}^{n-2}\cdot (x_{1}\cdot x_{2}\cdot \ldots \cdot x_{n}),

entonces el coeficiente del monomio de la forma será igual al número de árboles cuyos grados de vértices sean iguales a los grados de las variables del término dado: . $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ ${\displaystyle d_{1},\puntos,d_{n))$

Cayley elabora el caso y afirma que la prueba es fácilmente generalizable. $n=6$

Formulaciones

Dos formulaciones equivalentes:

El número de árboles diferentes en los vértices, numerados de a es igual a . $norte$ $una$ $norte$ $n^{{n-2}}$

El número de árboles de expansión en el gráfico completo es . $K_n$ $n^{{n-2}}$

Declaraciones relacionadas

El número de árboles en los vértices numerados también resulta ser igual al número de descomposiciones del ciclo en el producto de la transposición . $norte$ $norte$ ${\ estilo de visualización (1 \ puntos n)}$ $n-1$

El número de árboles en los vértices numerados también resulta ser igual al número de polinomios de grado (apropiadamente normalizados) con valores críticos dados en posición general. $norte$ $norte$ $n-1$
- Finalmente, este último es un caso especial de la clasificación topológica de cubiertas ramificadas de la esfera de Riemann - así, contar el número de árboles resulta ser un caso especial de cálculo de los números de Hurwitz correspondientes al caso de una superficie de cubierta del género 0.

Acerca de la evidencia

La fórmula de Cayley se deriva inmediatamente de las propiedades del código de Prufer , una forma de codificar de forma única un árbol etiquetado con n vértices mediante una secuencia ordenada de sus números de vértice. $norte$ $n-2$

La fórmula de Cayley también se deriva fácilmente del teorema del árbol de matrices .

Una de las demostraciones se basa en la siguiente relación ${\displaystyle a(x)=x\cdot e^{a(x)))$

a la función generadora exponencial

a(x)=a_{1}\cdot x+{\tfrac {1}{2}}\cdot a_{2}\cdot x^{2}+\dots +{\tfrac {1}{n !}}\cdot a_{n}\cdot x^{n}+\dots

donde denota el número de árboles enraizados en los vértices dados. Según el teorema de Lagrange sobre la inversión de series , de esta relación se sigue que . Esto último implica la fórmula de Cayley ya que para cada árbol de expansión hay formas exactas de elegir un vértice raíz. [3]

un

norte

{\displaystyle a_{n}=n^{n-1))

norte

Variaciones y generalizaciones

El número de formas de vincular un gráfico que consta de componentes desconectados, cada uno con un tamaño de vértice, es $metro$ $x_{yo}$ $T[x_{m}]=x_{1}\cdot x_{2}\dots x_{m}\cdot (x_{1}+x_{2}+\dots +x_{m})^{ m-2}=[x_{m}]!\ n^{m-2}$ Aquí está el número total de vértices del gráfico. ${\displaystyle n=x_{1}+x_{2}+\puntos +x_{m))$ Si cada componente consta de un vértice , entonces , y la fórmula da el número de Cayley original . ${\ estilo de visualización (x_ {i} = 1)}$ $n=m$ $n^{{n-2}}$

El número de árboles de expansión en un gráfico bipartito completo es $K_{{m, n}}$ $T(K_{m,n})=m^{n-1}\cdot n^{m-1}.$

El teorema del árbol de matrices da una expresión para el número de árboles de expansión de un gráfico como el determinante del Laplaciano (matriz de Kirchhoff) del gráfico.

Notas

↑ Cayley A. Un teorema sobre los árboles. Cuarto de galón. J. Aplicación pura. Matemáticas 23 (1889), 376-378; Artículos matemáticos recopilados, vol. 13, Prensa de la Universidad de Cambridge, 1897 , 26–28.
↑ Biggs NL, Lloyd EK, Wilson RJ Graph Theory 1736-1936. Clarendon Press, Oxford, 1976.
↑ Harari F., Palmer E. Enumeración de gráficos. - Mundo, 1977.

Literatura

Yu. M. Burman, notas del curso " Valores críticos de polinomios ": [1] , [2] , [3] , [4] .
M. E. Kazaryan, notas del curso " Geometría, topología y combinatoria de cubiertas ramificadas de la esfera ".
A. Cayley. Un teorema sobre árboles (neopr.) // Quart. Matemáticas J. - 1889. - T. 23 . - S. 376-378 .
T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Números de Hurwitz e integrales de Hodge .