Á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
Desta forma, a exponencial função de geração T(z) da sequência Tn é dada por
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.
onde 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)
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.