Na aula de hoje continuamos nossos estudos em teoria dos grafos com um tópico central: as árvores. Uma árvore é um tipo especial de grafo que aparece em todas as áreas da computação, desde sistemas operacionais até inteligência artificial.

O que define uma árvore?

Formalmente, uma árvore é um grafo conexo e acíclico. Isso significa que entre qualquer par de vértices existe exatamente um caminho simples. Se o grafo tem V vértices, ele possui V-1 arestas. Inserir uma nova aresta sempre cria um ciclo; remover qualquer aresta torna o grafo desconexo.

Uma árvore minimal possível é um único vértice (grafo trivial), que também é considerado uma árvore. Uma árvore com mais de um vértice tem pelo menos dois vértices de grau 1, conhecidos como folhas.

Outra forma de entender: um grafo é uma árvore se, e somente se, ele é conexo e o número de arestas é igual ao número de vértices menos um. Essa propriedade é muito útil para identificar árvores rapidamente.

Chamamos de floresta um grafo acíclico que pode ser desconexo. Cada componente conexo de uma floresta é uma árvore.

Propriedades fundamentais

  • Uma árvore com V vértices tem exatamente V-1 arestas.
  • Uma árvore é um grafo minimalmente conexo: se removermos qualquer aresta, ele se torna desconexo.
  • Uma árvore é um grafo maximalmente acíclico: se adicionarmos qualquer aresta, formamos um ciclo.
  • Para dois vértices quaisquer, o caminho entre eles é único.
  • Qualquer árvore com V ≥ 2 possui ao menos duas folhas.
  • O número de árvores geradoras diferentes em um grafo completo K_n é dado pela fórmula de Cayley: n^{n-2}.

Essas propriedades são a base para muitos algoritmos e demonstrações.

Árvores enraizadas

Na computação, muitas vezes tratamos de árvores com uma raiz definida. Em uma árvore enraizada, um vértice é designado como raiz e os demais são organizados em níveis. A partir da raiz, cada vértice possui um único pai (exceto a raiz) e zero ou mais filhos. Nós sem filhos são folhas. A altura de um nó é a distância até a folha mais distante; a profundidade é a distância até a raiz.

Árvores binárias, onde cada nó tem no máximo dois filhos, são um caso particular amplamente usado em algoritmos de busca, compressão e representação de expressões.

Árvores geradoras

Dado um grafo conexo G, uma árvore geradora (spanning tree) é um subgrafo que conecta todos os vértices utilizando o menor número possível de arestas (exatamente V-1) sem criar ciclos. BFS e DFS em um grafo produzem árvores geradoras, mas não necessariamente as de menor custo.

Árvore geradora mínima (MST)

Se o grafo possui arestas com pesos, o problema de encontrar a árvore geradora de peso total mínimo é clássico e resolvido por algoritmos gulosos.

Algoritmo de Kruskal

Kruskal ordena todas as arestas em ordem crescente de peso e as adiciona uma a uma, desde que não forme ciclo. Para detectar ciclos de forma eficiente, utiliza a estrutura union-find. O custo é dominado pela ordenação, O(E log E).

Algoritmo de Prim

Prim inicia a partir de um vértice e expande a árvore adicionando sempre a aresta de menor peso que conecta um vértice já incluído a um vértice externo. Pode ser implementado com uma fila de prioridade, alcançando O(E log V).

Ambos os algoritmos são ótimos para MST e a escolha entre eles depende da densidade do grafo: Prim tende a ser melhor em grafos densos (com muitas arestas), enquanto Kruskal é mais simples e se adapta bem a grafos esparsos.

Aplicações práticas de árvores

Sistemas de arquivos: diretórios e subdiretórios formam uma árvore enraizada no diretório raiz. Essa organização permite navegação hierárquica e gerenciamento eficiente de permissões.

Redes de computadores: o Spanning Tree Protocol (STP) utiliza o conceito de spanning tree para garantir uma topologia livre de loops em redes Ethernet com bridges ou switches.

Compressão: a codificação de Huffman constrói uma árvore binária onde os caracteres mais frequentes recebem códigos mais curtos, resultando em compressão ótima para símbolos independentes.

Bancos de dados: árvores B (B-trees) e suas variações são a estrutura de índice mais comum em sistemas gerenciadores de bancos de dados, mantendo dados ordenados e balanceados.

Inteligência artificial: árvores de decisão particionam o espaço de atributos e são a base de modelos como Random Forest; árvores de busca (minimax, Monte Carlo) são usadas em jogos.

Biologia e redes sociais: árvores filogenéticas representam relações evolutivas entre espécies, e árvores de amizade modelam hierarquias em redes.

O que vimos na prática

Resolvemos exercícios de identificação de árvores, cálculo de spanning trees e aplicação passo a passo dos algoritmos de Kruskal e Prim em exemplos pequenos. Também discutimos a importância da escolha da representação do grafo (matriz de adjacência versus lista de adjacência) para a eficiência dos algoritmos.

Perguntas frequentes

Como verificar se um grafo é uma árvore?
Verifique se o grafo é conexo e se o número de arestas é exatamente V-1. Alternativamente, execute uma DFS e verifique se não há arestas de retorno (back edges).
Existe mais de uma árvore geradora para o mesmo grafo?
Sim, exceto no caso trivial. Grafos completos têm muitas spanning trees (fórmula de Cayley).
Quando usar Kruskal versus Prim?
Kruskal é mais simples e eficiente em grafos esparsos com arestas ordenáveis. Prim é preferível em grafos densos ou quando o grafo é representado por matriz de adjacência.
O que é uma árvore binária de busca?
É uma árvore binária enraizada onde, para cada nó, todos os valores na subárvore esquerda são menores e todos na subárvore direita são maiores. Suporta busca, inserção e remoção em O(log n) em média.

Com este conteúdo, encerramos a aula 291. Na próxima aula continuaremos com árvores binárias, percursos e balanceamento. Se quiser revisar aulas anteriores ou ver outros temas, acesse a página de posts.