Sin utilizar el teorema de Cayley, demuestre que hay a lo sumo $n^{2n−2}$ árboles etiquetados con n vértices.

Question

Estoy estudiando para un examen que tengo y he encontrado un problema del pasado que no tengo ni idea de cómo hacer.. Mis pensamientos son. Sé que no hay que usar el teorema de Cayley pero dice que hay $n^{n-2}$ árboles etiquetados en n vértices.

Gracias :)

Answer 1

Un árbol tiene (exactamente) $n-1$ aristas, cada una de las cuales implica 2 vértices (distintos).

Ahora, consideremos el número de gráficos en $n$ vértices con $n-1$ aristas, donde para simplificar el recuento permitimos múltiples aristas entre vértices. Hay $ { n \choose 2 } ^{n-1} $ tales gráficos, y éstos son claramente menores que $n^{2n-2}$ .

Answer 2

La afirmación que intenta demostrar no utiliza más que el hecho de que un árbol tiene $n-1$ bordes. Para satisfacer a @ijkilchenko: esto se deduce del hecho de que un árbol que tiene cualquier arista, debe tener un vértice de grado 1 (si no, podemos seguir un camino a través de los vértices hasta que se intersecte a sí mismo, en cuyo punto tenemos un ciclo). Colapsando la arista hasta el vértice de grado 1 tenemos un objeto con un vértice y una arista menos, que sigue siendo un árbol (colapsar la arista no crea ciclos). Por inducción, podemos colapsar aristas hasta obtener un grafo sin aristas. Como colapsar una arista no aumenta el número de componentes conectados, debemos tener un solo vértice, y ninguna arista, por lo que $|v-e|$ (que es constante durante todo el proceso de colapso) es $1,$ que es lo que reclamamos.

Answer 3

Se puede identificar un árbol etiquetado, con un etiquetado arbitrario $e_1,..,e_{n-1}$ de las aristas, con una función

$$f: \{1,2,.., n-1\} \to \{ 1, 2, ...,n \} \times \{1,2,...,n\} $$ a través de

$$f(e_i)=(j,k)$$

Como el número de estas funciones es $(n^2)^{n-1}$ hemos terminado.

Answer 4

Así que el número de formas de etiquetar un árbol es $(\frac{n(n-1)}{2})^{n-1}$

Podemos ver que :

$(\frac{n(n-1)}{2})^{n-1} < (\frac{n*n}{2})^{n-1} < (n*n)^{n-1}$

$(n*n)^{n-1} = n^{2(n-1)}$

$\blacksquare$