Informática - Ideia 03

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.

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.

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.