Diâmetros e Centros de Árvores

Nesta lição, vamos falar de um tipo específico de grafo: árvores. Como vimos na lição de introdução, as árvores são grafos acíclicos conexos. Embora as árvores pareçam normais à primeira vista, elas têm muitas propriedades e algoritmos interessantes que funcionam especificamente para elas. Agora vamos estudar apenas dois tópicos que são específicos para este tipo de grafo. No entanto, iremos cobrir mais destes tópicos em cursos futuros.

Primeiro, vamos discutir a propriedade das árvores que relaciona o número de vértices e o número de arestas de uma árvore. Esta importante propriedade diz que o número de vértices em uma árvore é igual ao número de arestas mais . Assim, se a nossa árvore tiver vértices e arestas, podemos afirmar que .

Vamos começar com duas definições:

• Diametro de uma árvore: o caminho mais longo em uma árvore, ou seja, a distância máxima entre dois vértices em uma árvore;
• Centro de uma árvore: um vértice que minimiza a distância máxima entre ele e todos os outros vértices

Vamos concentrar-nos inicialmente no diâmetro de uma árvore. Mais tarde, vamos discutir sobre o centro de uma árvore.

Consideremos que estamos trabalhando com uma árvore com vértices.

Diâmetro de uma árvore

Como podemos encontrar o diâmetro de uma árvore?

Há uma solução simples que funciona em . Para cada vértice, apenas encontramos o vértice mais distante dele. Para encontrar este nó mais distante, podemos utilizar qualquer algoritmo de busca em grafos, uma vez que uma árvore tem exatamente um caminho entre dois vértices. Usaremos uma DFS no nosso código. Para encontrar a distância de todos os vértices a uma raiz usando a DFS, inicializamos a sua distância a si mesma como , e, sempre que estamos num vértice e descobrimos um filho não marcado, definimos a distância desse filho como distância do vértice atual mais .

Como sempre, reutilizaremos a nossa classe Graph da aula de representação com os seguintes métodos adicionais: