Generar todos los árboles enraizados no isomórficos a partir de un conjunto de vértices con una raíz común

Question

Para un conjunto de vértices $v = \left\{v_1...v_n \right\}$ y una raíz común $r$ ¿existe una forma eficiente (tal vez $O(1)$ por árbol) que genera todos los árboles no isomórficos en todos los nodos $v$ y con raíz $r$ .

Dos árboles son isomórficos si todas las relaciones padre-hijo son iguales, es decir, todos los nodos equivalentes de los dos árboles tienen el mismo padre y los mismos hijos.

Ejemplo: $v = \left\{v_1, v_2, v_3\right\}$

Todos los árboles deben tener la misma raíz y el mismo conjunto de nodos. La siguiente imagen muestra algunos árboles válidos:

La inclusión de un árbol debe hacer que se ignoren todos los demás árboles isomórficos

---

Otro post de SO muestra una implementación que encuentra topologías no enraizadas:

https://codereview.stackexchange.com/questions/202773/generating-all-unlabeled-trees-with-up-to-n-nodes

En una respuesta, aparece este algoritmo para crear topologías no isomórficas no enraizadas en $n$ nodos en tiempo constante por árbol.

Robert Alan Wrights, Bruce Richmond, Andrew Odlyzko y Brendan D. Mckay (1986). "Generación en tiempo constante de árboles libres". SIAM J. Comput. 15:2, pp. 540-548.

No estoy seguro de que sea posible ampliar este algoritmo de manera eficiente para generar los árboles enraizados deseados.

Answer 1

Puedo hacerlo en $O(n^2)$ por árbol.

El número de árboles posibles es $(n+1)^{n-1}$ ya que elegir un árbol en su problema equivale a elegir un no dirigido en el conjunto de vértices $v\cup \{r\}=\{v_1,\dots,v_n,r\}$ y luego dirigir todas las aristas hacia la raíz. El número de árboles no dirigidos en $n+1$ vértices es $(n+1)^{n-1}$ (este es el teorema de Cayley), y estos árboles pueden ser generados eficientemente usando códigos de Prüfer.

En concreto, iterar por todas las listas de longitud $n-1$ con entradas en $\{0,1,2,\dots,n\}$ , donde $0$ representa $r$ y $1$ a través de $n$ representan $v_1$ a través de $v_n$ . Para cada lista, genere el árbol correspondiente con vértices $\{r,v_1,\dots,v_n\}$ utilizando el algoritmo para convertir una secuencia de Prüfer en un árbol no dirigido . Por último, convierta esto en un árbol dirigido utilizando la búsqueda de amplitud primero a partir del vértice $r$ .