Número de árboles etiquetados con un subgrafo dado utilizando un código prufer.

Aug 17 2020

Planteamiento del problema

Quiero contar el número de árboles con vértice establecido $V$ = {1, 2, 3, ..., 10} que tienen $\\$

árbol $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (parece 1 - 2 - 3) como un subgrafo.

Entonces, si pienso correctamente, necesito encontrar el número de árboles etiquetados con n vértices y 2 bordes fijos.

Por la fórmula de Cayley hay $n^{n-2}$ árboles con n vértices.

Mi opinión es que árbol -> el algoritmo de código prufer es encontrar la hoja más pequeña, agregar la secuencia con el padre de esta hoja y eliminar esta hoja y el borde conectados con ella. Tendremos dos espacios en nuestra secuencia prufer ocupados por (2,2), (3,2), (1, 2). Una de estas subsecuencias puede comenzar en$n-1$ranuras. Cualquiera de los n vértices puede utilizar otras ranuras. Entonces obtenemos$3 \cdot (n-1) \cdot n^{n-4}$. Pero está completamente equivocado. Intenté usar algunas de las pruebas de problemas similares con un borde fijo, pero parece que tengo problemas para entenderlos ...

Respuestas

1 BrianM.Scott Aug 17 2020 at 08:17

Imagina que el arbol $T$( 3---2---1) se contrae a un solo vértice etiquetado$0$. Existen$8^6$ árboles etiquetados en el conjunto de vértices $\{0,4,5,6,7,8,9,10\}$. por$k=1,\ldots,7$, en cuántos de estos árboles tiene vértice $0$ tener grado $k$?

Vértice $0$ aparece $k-1$ veces en el código Prüfer de tal árbol, y cada uno de estos códigos Prüfer tiene $6$ ranuras, entonces hay $\binom6{k-1}$ formas de colocar el $k-1$ceros en el código. Entonces hay$7$ opciones para cada uno de los restantes $6-(k-1)=7-k$ ranuras, por lo que hay en total $\binom6{k-1}7^{7-k}$ tales árboles.

Cada uno de estos corresponde a más de un árbol en el conjunto de vértices $V$ que contiene el arbol $T$. Específicamente, si el vértice$0$ tiene grado $k$ en uno de estos árboles, cada uno de los bordes que lo dejan se puede unir a cualquiera de los tres vértices $1,2$y $3$ cuando expandimos el vértice $0$ a $T$, entonces el árbol se expande a $3^k$ diferentes árboles en el conjunto de vértices. $V$.

Resumiendo $k=1,\ldots,7$, encontramos que hay en total

$$\begin{align*} \sum_{k=1}^73^k\binom6{k-1}7^{7-k}&=\sum_{k=0}^6\binom6k3^{k+1}7^{6-k}\\ &=3\sum_{k=0}^6\binom6k3^k7^{6-k}\\ &=3(3+7)^6\\ &=3,000,000 \end{align*}$$

árboles en el vértice $V$ que contienen $T$. (El penúltimo paso usa el teorema del binomio).

Este análisis se generaliza fácilmente a una fórmula para el número de árboles etiquetados en $n$ vértices que contienen un subárbol específico $T$ con $m$ vértices.