En la teoría de grafos , un árbol recursivo (es decir, un árbol desordenado) es un árbol enraizado etiquetado no plano . Un árbol recursivo de tamaño n está etiquetado por enteros distintos 1, 2, ..., n , donde las etiquetas aumentan estrictamente comenzando en la raíz etiquetada 1. Los árboles recursivos no son planos, lo que significa que los hijos de un nodo en particular no están ordenados. Por ejemplo, los siguientes dos árboles recursivos de tamaño tres son iguales.
1 1 / \ = / \ / \ / \ 2 3 3 2
Los árboles recursivos también aparecen en la literatura bajo el nombre Aumento de árboles Cayley.
Propiedades
El número de árboles recursivos de tamaño n está dado por
Por tanto, la función generadora exponencial T ( z ) de la secuencia T n está dada por
Combinatoriamente, un árbol recursivo se puede interpretar como una raíz seguida de una secuencia desordenada de árboles recursivos. Sea F la familia de árboles recursivos.
dónde denota el nodo etiquetado por 1, × el producto cartesiano y el producto de partición para objetos etiquetados.
Mediante la traducción de la descripción formal se obtiene la ecuación diferencial para T ( z )
con T (0) = 0.
Biyecciones
Hay biyectivas correspondencias entre los árboles recursivas de tamaño n y permutaciones de tamaño n - 1.
Aplicaciones
Los árboles recursivos se pueden generar mediante un proceso estocástico simple. Estos árboles recursivos aleatorios se utilizan como modelos simples para epidemias.
Referencias
- Combinatoria analítica , Philippe Flajolet y Robert Sedgewick, Cambridge University Press, 2008
- Variedades de árboles crecientes , Francois Bergeron, Philippe Flajolet y Bruno Salvy. En Actas del 17º Coloquio sobre árboles en álgebra y programación, Rennes, Francia, febrero de 1992. Actas publicadas en Lecture Notes in Computer Science vol. 581, J.-C. Raoult Ed., 1992, págs. 24–48.
- Perfil de árboles aleatorios: correlación y ancho de árboles recursivos aleatorios y árboles de búsqueda binaria Michael Drmota y Hsien-Kuei Hwang, Adv. Apl. Prob., 37, 1-21, 2005.
- Perfiles de árboles aleatorios: teoremas de límites para árboles recursivos aleatorios y árboles de búsqueda binaria , Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger., Algorithmica, 46: 3-4, 2006, 367-407, 2006.