Propriedades básicas de árvores

Uma árvore é um tipo de grafo conexo não direcionado com várias propriedades especiais (se não sabes o que é um grafo começa por aqui): primeiro não têm ciclos, ou seja, não é possível caminhar pelas arestas de uma árvore partindo de um nó $v$ e chegar ao mesmo nó $v$ sem repetir arestas no processo; têm exatamente $n - 1$ arestas (sendo $n$ o número de vértices); todos os caminhos entre pares de nós são únicos, ou seja, entre quaisquer dois nós há apenas um único caminho que não repete arestas. Mais interessante que ter estas propriedades, é que qualquer uma delas define uma árvore, isto é, se um grafo respeita pelo menos uma das 3 propriedades, então respeita as outras duas e é uma árvore. Isto significa que se num enunciado de um problema nos dizem "é dado um grafo com $n$ nós e $n - 1$ arestas", então sabemos logo que se trata de uma árvore.

Centro, diâmetro e outras métricas

Devido à ausência de ciclos, as árvores têm um conjunto de nós especiais: o centro ou bicentro da árvore. O centro de um grafo é um nó tal que se tomarmos o tamanho máximo dos caminhos mais curtos entre esse nó e todos os outros, o centro tem o máximo mais pequeno, ou seja, minimiza a distância a todos os nós. Uma árvore tem ou um centro ou um bicentro (dois centros unidos por uma aresta).

Analogamente ao centro, podemos pensar no diâmetro de uma árvore como o caminho mais comprido entre um par de nós. Podemos provar que o centro faz parte deste caminho, caso contrário podíamos encontrar um caminho maior, contradizendo a definição de diâmetro.

Vamos ver um conjunto de artigos que esclarece estas definições e ainda descreve algoritmos para calcular as duas de forma eficiente:

Adicionalmente, podem ver ainda o capítulo 14 do livro Competitive Programmer’s Handbook que tem um excelente resumo deste tópico assim como uma discussão sobre outras métricas.

Aplicações

Se quiserem treinar um problema muito interessante que necessita destes conceitos, experimentem este: