Árvore recursiva

Em teoria dos grafos, uma árvore recursiva (i.e., uma árvore não ordenada) é uma organização não-planar de uma árvore com uma raíz e rótulos. Uma árvore recurisva de tamanho n  é tem seus nodos rotulados por distintos números inteiros 1, 2, ..., n,  estritamente de forma crescente, começando por 1 na raiz. Árvores recursivas são não-planares, o que significa que os filhos de um nó específico não são ordenados. Por exemplo, as duas árvores recursivas seguintes, de tamanho três, são iguais:

       1          1
      / \   =    / \
     /   \      /   \
    2     3    3     2

Árvores recursivas também aparecem na literatura sob o nome Increasing Cayley trees.

Propriedades

O número de árvores recursivas de tamanho n é dada por

$T_{n}=(n-1)!.\,$

Desta forma, a exponencial função de geração T(z) da sequência T_n é dada por

$T(z)=\sum _{n\geq 1}T_{n}{\frac {z^{n}}{n!}}=\log \left({\frac {1}{1-z}}\right).$

Combinatoriamente, uma árvore recursiva pode ser interpretada como uma raiz, seguido por uma sequência não ordenada árvores recursivas. Deixe que F denote a família das árvores recursivas.

$F=\circ +{\frac {1}{1!}}\cdot \circ \times F+{\frac {1}{2!}}\cdot \circ \times F*F+{\frac {1}{3!}}\cdot \circ \times F*F*F*\cdots =\circ \times \exp(F),$

onde $\circ$ indica o nó rotulado por 1,× indica o produto cartesiano e $*$ representa a partição do produto para os objetos rotulados.

Pela tradução da descrição formal, obtém-se a equação diferencial para T(z)

$T'(z)=\exp(T(z)),$

com T(0) = 0.

Bijeções

Existe correspondências bijectivas entre árvores recursivas de tamanho n e permutações de tamanho n − 1.

Aplicações

Árvores recursivas podem ser gerados utilizando um simples processo estocástico. Tais árvores recursivas aleatórias são usadas como modelos simples para epidemias.

Referências

• Analítico Combinatória, Philippe Flajolet e Robert Sedgewick, Cambridge University Press, 2008
• Variedades de Aumentar Árvores, François Bergeron, Philippe Flajolet, e Bruno Vencimento. Anais do 17º Colóquio sobre as Árvores em Álgebra e de Programação, em Rennes, França, de fevereiro de 1992. Processo publicado no Lecture Notes in Computer Science, vol. 581, J.-C. Raoult Ed., 1992, pp. De 24 a 48.
• Perfil do aleatório árvores: a correlação e a largura da aleatório recursiva árvores e árvores de busca binária Michael Drmota e Hsien-Kuei Hwang, Adv. Appl. Prob., 37, 1-21, 2005.
• Perfis aleatórios árvores: Limite de teoremas para aleatórios recursiva árvores e árvores de busca binária, Michael Fuchs, Hsien-Kuei Hwang, Ralph Neininger., Algorithmica, 46:3-4, 2006, 367-407, 2006.