Escrito por Samyra Almeida e Lúcio Figueiredo
Diâmetro de uma Árvore
Diâmetro de uma árvore (também chamado de largura) é a maior das distâncias entre quaisquer dois vértices da árvore. Na imagem abaixo, podemos observar que o diâmetro é igual a $$6$$, sendo igual a distância entre os nós $$7$$ e $$11$$.
Como encontrar o diâmetro de uma árvore
O algoritmo abaixo indica uma maneira de encontrar o diâmetro de um árvore com complexidade $$O(n)$$.
Algoritmo 1 – Encontrar o Diâmetro de uma árvore:
1. Escolha um nó $$R$$ arbitrário para ser a raiz da árvore.
2. Encontre o nó $$V$$ que está mais distante de $$R$$
3. Encontre o nó $$U$$ que está mais distante de $$V$$.
4. A distância entre $$V$$ e $$U$$ será igual ao diâmetro da árvore.
[spoiler title=’Prova do Algoritmo 1′ style=’default’ collapse_link=’true’]
Suponha que a árvore está enraizada em um vértice $$R$$.
Defina $$d(x, y)$$ como a distância do vértice $$x$$ ao vértice $$y$$ e $$h(x)$$ como $$d(R, x)$$. Defina também $$LCA(x, y)$$ como o menor ancestral comum dos vértices $$x$$ e $$y$$. Por fim, defina $$D$$ como o diâmetro da árvore.
Seja $$V$$ o vértice de maior profundidade na árvore, ou seja o vértice mais distante de $$R$$. Note que $$V$$ é o vértice encontrado na etapa $$2$$ do Algoritmo 1. Vamos provar, por absurdo, que $$V$$ sempre pertence a algum diâmetro.
Suponha, por absurdo, que $$V$$ não pertence a diâmetro algum. Sejam $$A$$ e $$B$$ dois vértices tais que $$dist(A, B) = D$$. Defina $$L$$ como $$LCA(A, B)$$. Vamos dividir a prova em dois casos:
Caso 1: $$LCA(V, L) \neq L$$.
Note que $$dist(A, B) = (h(A) – h(L)) + (h(B) – h(L)) = h(A) + h(B) – 2 \cdot h(L) = D$$.
Perceba que $$h(LCA(V, A)) < h(L)$$. Porém,
$$dist(V, A) = h(V) + h(A) – 2 \cdot h(LCA(V, A))$$.
Como $$h(V) \geq h(B)$$ (por definição) e $$h(LCA(V, A)) < h(L)$$, chegamos que
$$dist(V, A) > dist(A, B) \implies dist(V, A) > D$$, absurdo!
Assim, a prova deste caso está concluída.
Caso 2: $$LCA(V, L) = L$$ e $$LCA(V, A) = L$$.
Note que
$$dist(V, A) = h(V) + h(A) – 2 \cdot h(L)$$
e
$$dist(A, B) = h(A) + h(B) – 2 \cdot h(L)$$.
Como $$h(V) \geq h(B)$$, obtemos que $$dist(V, A) \geq dist(A, B) = D$$. Absurdo, pois assumimos que $$V$$ não pertence a nenhum diâmetro. Assim, a prova deste caso está concluída.
Caso 3: $$LCA(V, L) = L$$ e $$LCA(V, B) = L$$.
A prova deste caso é análoga à prova do Caso 2.
Como não é possível que $$LCA(V, L) = L$$ e $$LCA(V, A) \neq L$$ e $$LCA(V, B) \neq L$$, a prova de que $$V$$ pertence a algum diâmetro está concluída.
Por fim, seja $$U$$ o vértice mais distante de $$V$$ (o vértice encontrado na etapa $$3$$ do algoritmo). Seja $$W$$ um vértice tal que $$dist(V, W) = D$$. Como $$dist(V, U) \geq dist(V, W) = D$$, conluímos que $$dist(V, U) = D$$, e assim, a prova do Algoritmo 1 está finalizada.
[/spoiler]
Como um exemplo do algoritmo, usaremos a árvore da figura acima. Inicialmente, vamos enraizar a árvore no nó $$1$$.
Depois, vamos procurar (com uma DFS ou BFS, por exemplo) o nó que está mais distante de $$1$$. Podemos perceber que o vértice $$11$$ é o vértice mais distante de $$1$$, com uma distância igual a $$4$$. O próximo passo é encontrar o nó mais distante de $$11$$. Descobrimos que este nó é o $$7$$ com distância $$6$$. Assim, achamos que o diâmetro da árvore é igual a $$6$$.
O código abaixo encontra o diâmetro de uma árvore, utilizando o Algoritmo 1.
Centro de uma Árvore
Em uma árvore qualquer, defina $$p(x)$$ como a distância do vértice $$x$$ para o vértice mais distante de $$x$$. Este valor é conhecido como excentricidade de $$x$$.
O centro de uma árvore é o vértice $$C$$ tal que o valor $$p(C)$$ é mínimo, ou seja, o centro de uma árvore é o vértice que possui menor excentricidade. O lema abaixo introduz um fato importante sobre centros:
Lema 1: O centro $$C$$ de uma árvore pertence a todos os diâmetros presentes nela.
[spoiler title=’Prova’ style=’default’ collapse_link=’true’]
Enraize a árvore no vértice $$C$$.
Sejam $$U$$ e $$V$$ duas pontas de um diâmetro qualquer. Vamos realizar uma prova por absurdo, ou seja, vamos supor que $$C$$ não está no caminho de $$U$$ para $$V$$.
Seja $$L$$ igual a $$LCA(U, V)$$. Vamos dividir nossa prova em dois casos:
Caso 1: $$L = C$$.
Neste caso, $$C$$ está no caminho entre $$U$$ e $$V$$ por definição, logo, chegamos num absurdo.
Caso 2: $$L \neq C$$.
Assuma, sem perda de generalidade, que $$dist(L, V) \geq dist(L, U)$$. Perceba que $$V$$ é o vértice na subárvore de $$L$$ mais distante de $$L$$, pois caso contrário, poderíamos trocar um dos vértices $$U$$ ou $$V$$ por tal vértice e aumentaríamos o valor do diâmetro da árvore.
Seja $$W$$ um vértice que não pertence à subárvore de $$L$$. Note que $$dist(L, W) \leq dist(L, U)$$, pois, caso contrário, poderíamos aumentar o valor do diâmetro da árvore.
Note que $$p(L)$$ é igual a $$max(d_{dentro}, d_{fora})$$, onde $$d_{dentro}$$ é a maior distância entre $$L$$ e um vértice na subárvore de $$L$$ e $$d_{fora}$$ é a maior distância entre $$L$$ e um vértice fora da subárvore de $$L$$.
Perceba que, pelos dois primeiros argumentos acima,
$$d_{dentro} = dist(L, V)$$ e $$d_{fora} \leq dist(L, U)$$.
No entanto,
$$dist(L, V) < dist(C, V) \leq p(C)$$, já que $$L \neq C$$.
Analogamente,
$$dist(L, U) < dist(C, U) \leq p(C)$$.
Portanto, concluímos que ambos os valores $$d_{dentro}$$ e $$d_{fora}$$ são estritamente menores que $$p(C)$$, ou seja, $$p(L) < p(C)$$, absurdo pela definição de $$C$$.
Assim, concluímos a prova do Lema 1.
[/spoiler]
Como encontrar o centro de uma árvore
O algoritmo abaixo indica uma maneira de encontrar um centro de uma árvore com complexidade $$O(n)$$:
Algoritmo 2: Encontrar um centro de uma árvore
1. Encontre um diâmetro qualquer com pontas $$U$$ e $$V$$.
2. Encontre o vértice $$C$$ no caminho de $$U$$ para $$V$$ tal que $$max(dist(C, U), dist(C, V))$$ possui o menor valor possível.
3. O vértice $$C$$ é um centro da árvore.
[spoiler title=’Prova do Algoritmo 2′ style=’default’ collapse_link=’true’]
Suponha, por absurdo, que $$p(C) \neq max(dist(C, U), dist(C, V))$$. Então, defina $$B$$ como o vértice tal que $$dist(C, B) = p(C)$$. É fácil perceber que $$B$$ não pertence ao caminho de $$U$$ para $$V$$.
Por definição, $$dist(C, B) > max(dist(C, U), dist(C, V))$$. Assim, vamos dividir a prova em dois casos:
Caso 1: $$dist(U, B) \leq dist(V, B)$$.
Neste caso, perceba que o caminho de $$V$$ para $$B$$ não passa por $$U$$, pois, caso contrário, $$dist(V, B) > dist(V, U)$$, absurdo já que $$dist(V, U)$$ é diâmetro.
Logo,
$$dist(V, B) = dist(V, C) + dist(C, B)$$.
Como $$dist(C, B) > dist(C, U)$$, temos que
$$dist(V, B) = dist(V, C) + dist(C, B) > dist(V, C) + dist(C, U) \implies$$
$$\implies dist(V, B) > dist(U, V)$$,
absurdo, já que $$dist(U, V)$$ é diâmetro.
Caso 2: $$dist(V, B) < dist(U, B)$$.
A prova deste caso é análoga à prova do Caso 1.
Assim, está concluída a prova do Algoritmo 2.
[/spoiler]
O código abaixo encontra o centro de uma árvore, utilizando o Algoritmo 2.