Número: 078
Enunciado:
Seja F(n) o número de árvores filogenéticas distintas completamente resolvidas sem raiz definidas sobre um conjunto de n espécies.
A expressão que melhor relaciona F(n) com F(n-1) é:
- F(n)=F(n-1)*(2n-5)
- F(n)=F(n-1)2
- F(n)=F(n-1)*(n-2)
- F(n)=F(n-1)*2n
- NDA
Para adicionar uma folha, poderíamos ligar a nova folha a algum dos nós já existentes na árvore. Porém, nesse caso, o nó já existente passaria a ter grau 2, se antes fosse uma folha, ou grau 4, se antes fosse um nó interno, fazendo com que a árvore com n-1 folhas não seja totalmente resolvida. Logo, a única alternativa possível é dividir alguma aresta da árvore, criando um novo nó, e ligar a folha a este nó. Assim teremos um novo nó interno com grau igual a 3.
ResponderExcluirEntão, o número de maneiras de se colocar essa nova folha é igual ao número de arestas na árvore.
Quantas arestas existem numa árvore completamente resolvida com n folhas?
Um grafo conexo e acíclico com v vértices tem v-1 arestas, portanto
Uma árvore completamente resolvida com n folhas e i nós internos terá A arestas:
A = (n + i - 1)
->
i = A - n + 1 (1)
Mas sabemos que cada folha tem grau 1 e cada nó interno tem grau 3, então também podemos calcular A da seguinte forma:
A = (n*1 + i*3) /2 (2)
Substituindo (1) em (2):
A = (n+3*(A-n+1))/2
2A = n+3A-3n+3
A = 2n - 3 (3)
Todas as árvores de n folhas tem o mesmo número A de arestas.
Seja F(n) o número de árvores possíveis com n folhas, logo
F(n)=F(n-1)*(numero de arestas numa árvore de n-1 folhas)
Utilizando (3):
F(n)=F(n-1)*(2(n-1)-3)
F(n)=F(n-1)*(2n-5)
Alternativa correta: 1
Bom comentário, nota 10,0.
ResponderExcluir