Se você já usou um sistema de arquivos, uma estrutura de dados de busca binária, um heap, ou analisou a sintaxe de um programa, você já trabalhou com árvores. Elas são, provavelmente, a estrutura de dados mais onipresente na ciência da computação — e sua elegância matemática é inseparável de sua utilidade prática.
Dentro da teoria dos grafos, árvores também ocupam um lugar especial: são a família de grafos mais simples e com as propriedades mais amigáveis. Por isso, sempre que se quer provar um resultado geral sobre grafos, a estratégia mais natural é verificar primeiro se ele vale para árvores. Se falhar já nesse caso mais simples, não há esperança para o caso geral; se valer, boa parte do trabalho de prova já está feita. Árvores também aparecem fora da computação, descrevendo desde a estrutura de moléculas em química até análises sintáticas em linguística — mas é em computação que sua utilidade é mais onipresente.
Por que Árvores Importam? #
Árvores são, ao mesmo tempo, o modelo teórico mais simples da teoria dos grafos e uma das estruturas de dados mais usadas na prática:
- Sistemas de arquivos: pastas e arquivos formam naturalmente uma árvore enraizada, onde cada pasta é filha de exatamente uma pasta-mãe.
- Compiladores e interpretadores: a análise sintática de um programa produz uma árvore de sintaxe abstrata (AST), usada para gerar código ou interpretar a linguagem.
- Estruturas de busca eficientes: árvores binárias de busca e heaps organizam dados de forma hierárquica para tornar busca, inserção e remoção rápidas — desde que a árvore se mantenha balanceada, com altura pequena.
- Redes de menor custo: encontrar a árvore geradora mínima de uma rede (a forma mais barata de manter tudo conectado, sem ciclos redundantes) é um problema clássico de otimização em telecomunicações e logística.
Definição de Árvore #
Uma árvore é um grafo conexo e acíclico (sem ciclos).
Um grafo acíclico é uma floresta: cada componente conexo de uma floresta é uma árvore.
A definição de árvore é minimalista: a árvore tem o mínimo de arestas necessárias para manter a conexidade — remover qualquer aresta a desconecta.
As três árvores a seguir ilustram bem essa definição:
O exemplo acima mostra três árvores bem diferentes entre si — uma parece um caminho torto, outra é uma estrela, a terceira se ramifica em vários níveis — mas todas compartilham as duas propriedades que definem a categoria: são conexas e não têm ciclos.
Uma floresta, por sua vez, é o que sobra quando se abre mão da conexidade mas se mantém a ausência de ciclos: cada pedaço isolado (cada componente conexo) é, por si só, uma árvore. As mesmas três árvores acima, por exemplo, podem ser vistas como os três componentes conexos de uma única floresta:
Folhas #
Uma folha (ou vértice pendente) é um vértice \(v\) tal que \(d(v) = 1\).
Nas mesmas três árvores, as folhas (destacadas em vermelho) são exatamente os vértices de grau 1 — nas pontas dos ramos:
Uma Caracterização de Árvores #
O resultado a seguir conecta a definição de árvore (conexa e acíclica) a uma propriedade equivalente, mas formulada de um jeito completamente diferente — em termos de caminhos:
Um grafo \(G\) é uma árvore se e somente se existe um único caminho entre qualquer par de vértices de \(G\).
Prova:
(⇒) Seja \(G\) uma árvore. Por definição \(G\) é conexo, logo entre cada par de vértices \(v\) e \(w\) existe pelo menos um caminho. Falta mostrar que esse caminho é único.
Suponha, por absurdo, que existam dois caminhos distintos \(P_1\) e \(P_2\) entre \(v\) e \(w\). Como os caminhos são distintos mas compartilham os extremos \(v\) e \(w\), existem necessariamente dois vértices \(t_1\) e \(t_2\) (podendo ser \(t_1 = v\) e \(t_2 = w\), se os caminhos só se tocam nos extremos) tais que, entre \(t_1\) e \(t_2\), os subcaminhos de \(P_1\) e de \(P_2\) são disjuntos em vértices — ou seja, \(t_1\) e \(t_2\) são o primeiro ponto em que os caminhos se separam e o próximo ponto em que voltam a se encontrar.
O subcaminho de \(P_1\) entre \(t_1\) e \(t_2\), unido ao subcaminho de \(P_2\) entre \(t_1\) e \(t_2\) (percorrido no sentido inverso), forma um ciclo. Isso contradiz o fato de \(G\) ser acíclico. Logo, o caminho entre \(v\) e \(w\) é único.
(⇐) Suponha que existe um único caminho entre cada par de vértices de \(G\). Em particular, existe pelo menos um caminho entre cada par de vértices, logo \(G\) é conexo.
Falta mostrar que \(G\) é acíclico. Suponha, por absurdo, que \(C\) seja um ciclo de \(G\), e seja \((v, w)\) uma aresta de \(C\). Então existem dois caminhos distintos entre \(v\) e \(w\): a própria aresta \((v,w)\) e o caminho \(C - (v,w)\) (o resto do ciclo). Isso contradiz a hipótese de caminho único. Logo \(G\) é acíclico.
Como \(G\) é conexo e acíclico, \(G\) é uma árvore. Portanto, um grafo é uma árvore se e somente se existe um único caminho entre cada par de seus vértices, que é o que queríamos demonstrar. \(\blacksquare\)
Na árvore abaixo, por exemplo, existe um único caminho entre os vértices \(a\) e \(f\) — destacado em vermelho:
Árvores e o Número de Arestas #
Se \(G\) é uma árvore com \(n\) vértices, então \(G\) tem exatamente \(n - 1\) arestas.
Prova por indução forte em \(n\):
Base: \(n = 1\). Uma árvore com 1 vértice (o grafo trivial) tem 0 arestas. \(n - 1 = 0\). ✓
Hipótese de indução: suponha que o resultado vale para toda árvore com menos de \(n\) vértices (\(n \geq 1\)).
Passo indutivo: seja \(T\) uma árvore com \(n\) vértices (\(n > 1\)). Como \(n > 1\), \(T\) contém ao menos uma aresta \(e = (v, w)\). Seja \(T’\) o grafo obtido removendo \(e\) de \(T\) (sem remover os vértices).
Pelo Teorema 1, o único caminho entre \(v\) e \(w\) em \(T\) é a própria aresta \(e\). Ao remover \(e\), \(v\) e \(w\) deixam de ser conexos em \(T’\): eles passam a estar em dois componentes conexos distintos de \(T’\). E não há outros componentes: todo vértice \(x\) continua ligado a \(v\) ou a \(w\), porque o caminho de \(x\) até \(v\) em \(T\), se usa a aresta \(e\), passa por \(w\) logo antes dela. Sejam \(T_1\) e \(T_2\) esses dois componentes. Cada um deles é acíclico (pois é subgrafo de uma árvore) e conexo (é um componente conexo) — logo \(T_1\) e \(T_2\) são árvores, cada uma com menos de \(n\) vértices.
Pela hipótese de indução, aplicada a \(T_1\) e a \(T_2\):
$$|E(T_1)| = |V(T_1)| - 1 \qquad \text{e} \qquad |E(T_2)| = |V(T_2)| - 1$$Como \(V(T_1) \cup V(T_2) = V(T)\) e \(E(T_1) \cup E(T_2) \cup \{e\} = E(T)\), temos:
$$n = |V(T)| = |V(T_1)| + |V(T_2)|$$$$m = |E(T)| = |E(T_1)| + |E(T_2)| + 1 = \big(|V(T_1)| - 1\big) + \big(|V(T_2)| - 1\big) + 1 = |V(T_1)| + |V(T_2)| - 1 = n - 1$$
Portanto, por indução, toda árvore com \(n\) vértices tem \(m = n - 1\) arestas, que é o que queríamos demonstrar. \(\blacksquare\)
Conferindo com código
A prova acima vale para qualquer \(n\), mas nada como gerar árvores aleatórias de tamanhos bem diferentes e conferir a relação \(m = n-1\) em cada uma delas:
import networkx as nx
for n in [5, 10, 20, 50, 100]:
T = nx.random_labeled_tree(n, seed=42)
m, v = T.number_of_edges(), T.number_of_nodes()
print(f"n={v:>3}: |V|={v:>3}, |E|={m:>3}, |E| == |V|-1? {m == v - 1}")n= 5: |V|= 5, |E|= 4, |E| == |V|-1? True
n= 10: |V|= 10, |E|= 9, |E| == |V|-1? True
n= 20: |V|= 20, |E|= 19, |E| == |V|-1? True
n= 50: |V|= 50, |E|= 49, |E| == |V|-1? True
n=100: |V|=100, |E|= 99, |E| == |V|-1? Truenx.random_labeled_tree(n) sorteia uma árvore aleatória entre todas as
\(n^{n-2}\) árvores rotuladas possíveis com \(n\) vértices (a mesma
Fórmula de Cayley que reaparece mais adiante, na seção de árvore
geradora) — e em todas elas, sem exceção, o número de arestas é
exatamente o número de vértices menos um.
O inverso também é verdadeiro: um grafo conexo com \(n\) vértices e \(n-1\) arestas é necessariamente uma árvore. Mais ainda, quaisquer duas das três condições abaixo implicam a terceira:
- \(G\) é conexo
- \(G\) é acíclico
- \(|E| = |V| - 1\)
Centro de uma Árvore #
Antes de falar do centro de uma árvore especificamente, vale relembrar a definição geral de excentricidade e centro de um grafo, que já vimos ao estudar distância, excentricidade e diâmetro.
Seja \(G = (V, E)\) um grafo. A excentricidade de um vértice \(v\) é
$$e(v) = \max_{w \in V} d(v, w)$$isto é, a maior distância de \(v\) até qualquer outro vértice do grafo. O centro de \(G\) é o conjunto
$$c(G) = \{w \in V \mid e(w) \text{ é mínimo}\}$$Em qualquer grafo, \(1 \leq |c(G)| \leq |V(G)|\).
Em um grafo qualquer, o centro pode ter qualquer tamanho entre 1 e todos os vértices. Em árvores, no entanto, esse número é sempre muito pequeno:
O centro de qualquer árvore consiste em um único vértice, ou em dois vértices adjacentes.
Prova: a demonstração se apoia em três fatos.
Fato 1: em uma árvore com pelo menos três vértices, nenhuma folha pertence ao centro. Se \(f\) é uma folha e \(u\) é o seu único vizinho, todo caminho que sai de \(f\) passa por \(u\); logo \(d(f, w) = 1 + d(u, w)\) para todo \(w \neq f\), e \(e(f) = e(u) + 1\). A folha fica sempre uma unidade mais longe de tudo do que a sua vizinha.
Fato 2: se removermos todas as folhas de uma árvore \(G\) (e as arestas incidentes a elas), obtendo um grafo \(G’\), cada vértice de \(G’\) tem excentricidade exatamente uma unidade a menos em \(G’\) do que tinha em \(G\). Isso ocorre porque, em uma árvore, os caminhos mais longos a partir de qualquer vértice terminam necessariamente em folhas — remover as folhas encurta esses caminhos em exatamente 1.
Fato 3: \(c(G) = c(G’)\). Como todos os vértices de \(G’\) tiveram sua excentricidade reduzida pela mesma quantidade (Fato 2), e as folhas removidas não estavam no centro (Fato 1), o conjunto de vértices de excentricidade mínima não muda.
Os fatos 1, 2 e 3 justificam o seguinte algoritmo iterativo para encontrar o centro:
- Remova todas as folhas de \(G\) (com as arestas incidentes)
- Repita o procedimento no grafo restante
- Pare quando sobrar um único vértice, ou dois vértices ligados por uma aresta — esse é o centro
Como o grafo tem um número finito de vértices e cada rodada remove pelo menos uma folha, o processo termina — e o único caminho para não sobrar mais de dois vértices é parar exatamente em um vértice isolado ou em dois vértices ligados por uma aresta (se sobrassem três ou mais vértices, ao menos dois deles ainda seriam folhas entre si, e a rodada seguinte os removeria). Portanto, o centro de qualquer árvore é um único vértice ou dois vértices adjacentes, que é o que queríamos demonstrar. \(\blacksquare\)
Árvores balanceadas #
Um conceito vizinho, muito usado em estruturas de dados, é o de árvore balanceada: uma árvore enraizada em que as subárvores que partem de cada vértice têm tamanhos parecidos, de modo que nenhum ramo fique muito mais comprido que os outros. O critério exato muda de uma estrutura para outra. Nas árvores AVL — sigla dos sobrenomes de Georgy Adelson-Velsky e Evgenii Landis, que as publicaram em 1962 —, as alturas das duas subárvores de qualquer vértice diferem de no máximo 1; nas rubro-negras, uma regra sobre as cores dos vértices garante que nenhum caminho da raiz até uma folha tenha mais que o dobro do comprimento de outro. Nos dois casos, a árvore se reequilibra a cada inserção ou remoção, o que mantém a altura logarítmica no número de elementos — e é justamente essa altura pequena que torna buscas, inserções e remoções rápidas nessas estruturas.
A figura abaixo mostra três árvores balanceadas:
Por que balancear importa: altura balanceada vs. degenerada
“Altura logarítmica” é uma frase abstrata até que se vê o tamanho da diferença na prática. Vamos comparar a altura de uma árvore binária balanceada (gerada com todos os níveis completos) com a de uma árvore degenerada — uma cadeia só de filhos únicos, como uma lista encadeada, que é o que se obtém, por exemplo, ao inserir dados já ordenados em uma árvore binária de busca comum, sem rebalanceamento:
import networkx as nx
import math
for h in [1, 2, 3, 4, 10]:
T_balanceada = nx.balanced_tree(r=2, h=h)
n = T_balanceada.number_of_nodes()
altura_balanceada = nx.eccentricity(T_balanceada, v=0) # 0 é a raiz
altura_degenerada = n - 1 # cadeia com n vértices, enraizada numa ponta
print(f"n={n:>5} | altura balanceada={altura_balanceada:>2} | altura degenerada={altura_degenerada:>5}")n= 3 | altura balanceada= 1 | altura degenerada= 2
n= 7 | altura balanceada= 2 | altura degenerada= 6
n= 15 | altura balanceada= 3 | altura degenerada= 14
n= 31 | altura balanceada= 4 | altura degenerada= 30
n= 2047 | altura balanceada=10 | altura degenerada= 2046Com apenas 2047 elementos, a árvore balanceada tem altura 10 — ou seja, qualquer busca encontra o que procura em no máximo 10 passos — enquanto a versão degenerada tem altura 2046, praticamente percorrendo todos os elementos um a um (o mesmo custo de buscar em uma lista). É exatamente essa diferença, que só cresce conforme \(n\) aumenta, que torna árvores balanceadas indispensáveis em estruturas de busca de alto desempenho.
Exemplos #
Exemplo 1: centro de um grafo em cruz
Enunciado: Encontre o centro da árvore em formato de cruz abaixo, com um vértice central \(c\) e quatro “braços” de comprimentos 1, 2, 2 e 4 partindo dele.
Solução: Aplicando o algoritmo: a cada rodada, removemos as folhas atuais (as pontas de cada braço). Como os braços têm comprimentos diferentes, alguns desaparecem antes de outros — e o processo converge para um único vértice. Repare que esse vértice não é o hub central \(c\) de onde os braços partem: é um vértice no meio do braço mais longo. O centro de uma árvore é definido pela excentricidade mínima, não pela posição “visualmente mais central” do desenho — por isso o algoritmo, e não a intuição, é a ferramenta confiável.
Exemplo 2: centro de uma árvore ramificada
Enunciado: Encontre o centro da árvore ramificada abaixo (não é um caminho simples nem uma cruz).
Solução: Aplicando o mesmo algoritmo de remoção de folhas, a aplicação termina com dois vértices adjacentes. Note que, mesmo em uma árvore com uma estrutura bem mais irregular que um caminho ou uma cruz, o algoritmo continua funcionando exatamente da mesma forma, e o resultado continua sendo 1 ou 2 vértices adjacentes — como o teorema garante.
Conferindo com código
Implementar o algoritmo de remoção de folhas manualmente é um bom
exercício, mas o networkx já traz essa conta pronta em nx.center.
Vamos aplicá-la aos dois grafos que acabamos de resolver à mão:
import networkx as nx
G_cruz = nx.Graph()
G_cruz.add_edges_from([
("c", "a1"),
("c", "b1"), ("b1", "b2"),
("c", "e1"), ("e1", "e2"),
("c", "d1"), ("d1", "d2"), ("d2", "d3"), ("d3", "d4"),
])
print("Centro do grafo em cruz:", sorted(nx.center(G_cruz)))
G_ramificada = nx.Graph()
G_ramificada.add_edges_from([
("c", "b"), ("c", "d"),
("b", "a"),
("d", "e"), ("d", "f"),
("f", "g"), ("f", "h"),
])
print("Centro da árvore ramificada:", sorted(nx.center(G_ramificada)))Centro do grafo em cruz: ['d1']
Centro da árvore ramificada: ['c', 'd']Os dois resultados batem exatamente com o que encontramos manualmente removendo folhas rodada a rodada — inclusive a “surpresa” do primeiro exemplo, em que o centro não é o vértice \(c\) de onde os braços partem, mas sim \(d_1\), no meio do braço mais longo.
Árvore Geradora #
Uma árvore geradora de um grafo conexo \(G\) é um subgrafo gerador de \(G\) que é uma árvore — ou seja, um subgrafo com todos os \(n\) vértices de \(G\) e \(n-1\) arestas formando uma árvore.
Toda árvore geradora é obtida de \(G\) removendo exatamente \(|E| - (n-1)\) arestas sem desconectar o grafo.
Para todo grafo conexo \(G\), é sempre possível achar uma árvore geradora de maneira sistemática: selecione arestas de \(G\), uma de cada vez, de forma que nenhum ciclo seja criado, e repita esse procedimento até ter escolhido \(n-1\) arestas — ou, o que dá no mesmo num grafo conexo, até que nenhuma aresta restante possa entrar sem fechar um ciclo. Não basta parar quando todos os vértices aparecerem em alguma aresta escolhida: no caminho \(a - b - c - d\), as arestas \((a,b)\) e \((c,d)\) já tocam os quatro vértices, mas formam uma floresta, não uma árvore.
Escolher arestas sem fechar ciclos é o princípio mais básico por trás da construção de uma árvore geradora — e é a partir dele que os algoritmos mais conhecidos se constroem:
- Algoritmo de Prim e Algoritmo de Kruskal: aplicam essa mesma ideia de seleção de arestas sem criar ciclos, mas escolhendo sempre a aresta de menor peso disponível, para encontrar a árvore geradora mínima (de menor custo total) em grafos ponderados
- Algoritmos BFS (busca em largura) e DFS (busca em profundidade): produzem naturalmente uma árvore geradora ao percorrer o grafo, marcando como aresta da árvore cada aresta usada para visitar um vértice ainda não visitado
Conferindo com código
Vamos ver a busca em largura produzindo uma árvore geradora na prática, usando o mesmo grafo \(G\) dos exemplos a seguir (vértices \(a,b,c,d,e,f\), com \(a\) adjacente a \(b\), \(c\), \(e\) e \(f\)):
import networkx as nx
G = nx.Graph()
G.add_edges_from([
("a", "b"), ("a", "c"), ("b", "c"),
("c", "e"), ("a", "e"),
("e", "f"), ("a", "f"),
("e", "d"), ("c", "d"),
])
T_bfs = nx.bfs_tree(G, "a")
print("Arestas da árvore BFS a partir de a:", sorted(tuple(sorted(e)) for e in T_bfs.edges()))
print("É árvore?", nx.is_tree(T_bfs.to_undirected()))Arestas da árvore BFS a partir de a: [('a', 'b'), ('a', 'c'), ('a', 'e'), ('a', 'f'), ('c', 'd')]
É árvore? TrueA busca em largura a partir de \(a\) visita primeiro todos os vizinhos diretos de \(a\) (\(b\), \(c\), \(e\), \(f\)) e só depois chega a \(d\), através de \(c\). O resultado é uma terceira árvore geradora de \(G\), diferente das duas que veremos a seguir nos Exemplos 1 e 2 — mais uma confirmação de que o método usado para construir a árvore geradora (seleção manual de arestas, BFS, DFS, …) determina qual árvore específica se obtém.
Exemplo 1: duas árvores geradoras diferentes
Enunciado: Encontre duas árvores geradoras diferentes do grafo \(G\) abaixo, com vértices \(a, b, c, d, e, f\) contendo alguns ciclos.
Solução: \(T_1\) e \(T_2\) são duas árvores geradoras distintas de \(G\) — ambas conexas, acíclicas, cobrindo todos os vértices de \(G\), mas usando conjuntos diferentes de arestas. Isso ilustra que a árvore geradora de um grafo, em geral, não é única.
Exemplo 2: a ordem de escolha das arestas importa
Enunciado: Aplique o algoritmo de seleção de arestas ao grafo \(G\) com a lista de arestas \(\{(a,b), (a,c), (b,c), (c,e), (a,e), (e,f), (a,f), (e,d), (c,d)\}\), percorrendo-a nessa ordem.
Solução: Aplicando o algoritmo de seleção de arestas nessa ordem, evitando ciclos a cada passo, obtemos a árvore geradora \(T_1\) do exemplo anterior. Se percorrêssemos a lista de arestas em outra ordem, poderíamos ter escolhido arestas diferentes nos pontos em que havia mais de uma opção sem ciclo — e o resultado seria uma árvore geradora diferente, ainda que igualmente válida (é exatamente isso que acontece no Exercício 3 a seguir, que produz \(T_2\)).
Quantas árvores geradoras um grafo pode ter?
Um grafo conexo com \(n\) vértices pode ter muitas árvores geradoras distintas. Para o caso do grafo completo \(K_n\), a Fórmula de Cayley mostra que esse número é \(n^{n-2}\) — o mesmo que o número de árvores com \(n\) vértices rotulados, e uma quantidade que cresce muito rapidamente com \(n\). O nome homenageia Arthur Cayley, que publicou uma nota sobre ela em 1889, mas a fórmula já tinha sido obtida por Carl Wilhelm Borchardt em 1860 (veja o verbete Cayley’s formula). Esse resultado vai além do que precisamos aqui, mas ajuda a entender por que a escolha do critério de seleção de arestas (como o peso mínimo, no caso de Prim e Kruskal) é tão importante: dentre exponencialmente muitas árvores geradoras possíveis, geralmente queremos uma específica.
O networkx calcula esse número diretamente (usando o Teorema da Árvore
Matricial de Kirchhoff, sem precisar enumerar as árvores uma a uma), e o
resultado bate exatamente com a fórmula de Cayley:
import networkx as nx
for n in [2, 3, 4, 5, 6]:
K_n = nx.complete_graph(n)
contagem = nx.number_of_spanning_trees(K_n)
formula = n ** (n - 2)
print(f"n={n}: nx.number_of_spanning_trees = {contagem:.0f} | n**(n-2) = {formula}")n=2: nx.number_of_spanning_trees = 1 | n**(n-2) = 1
n=3: nx.number_of_spanning_trees = 3 | n**(n-2) = 3
n=4: nx.number_of_spanning_trees = 16 | n**(n-2) = 16
n=5: nx.number_of_spanning_trees = 125 | n**(n-2) = 125
n=6: nx.number_of_spanning_trees = 1296 | n**(n-2) = 1296Árvores Enraizadas #
Em computação, usamos frequentemente árvores com uma raiz designada. Dada uma árvore \(T = (V, E)\), basta escolher um vértice qualquer \(v\) e chamá-lo de raiz — a árvore passa então a ser chamada de árvore enraizada, e sua representação gráfica costumeira (raiz no topo, ramos descendo) ganha uma hierarquia bem definida.
Para a teoria dos grafos, uma árvore é só um grafo conexo e acíclico: não tem raiz, nem ordem entre os vizinhos de um vértice, nem “esquerda” e “direita”. A árvore das estruturas de dados é mais rica: uma árvore binária de busca tem uma raiz fixa, a hierarquia pai/filho e a distinção entre filho esquerdo e filho direito. Por isso duas árvores binárias diferentes — a raiz \(r\) com um único filho \(x\) à esquerda, e a mesma raiz com \(x\) à direita — são o mesmo grafo: os vértices \(r\) e \(x\) ligados por uma aresta.
Exemplo: escolhendo uma raiz
Enunciado: Considere uma árvore sem raiz definida, com vértices \(a\) até \(n\). Escolha o vértice \(d\) como raiz e redesenhe a árvore de acordo.
Solução: ao escolher o vértice \(d\) como raiz, a mesma árvore passa a ser desenhada com \(d\) no topo e os demais vértices organizados em níveis abaixo dele.
Com uma raiz \(r\) fixada, definimos:
Sejam \(v\) e \(w\) dois vértices de uma árvore enraizada \(T\) com raiz \(r\). Se \(v\) pertence ao caminho de \(r\) a \(w\), então \(v\) é ancestral de \(w\), e \(w\) é descendente de \(v\). Se, além disso, \((v, w)\) é uma aresta, então \(v\) é pai de \(w\) (e \(w\) é filho de \(v\)).
A raiz é o único vértice sem pai; as folhas são os vértices sem filhos.
Exemplo: ancestral, descendente, pai e filho
Enunciado: Na árvore enraizada \(T\) abaixo (raiz \(r\), filhos \(b\) e \(c\) de \(r\), filhos \(d\) e \(e\) de \(c\), e filhos \(f\) e \(g\) de \(e\)), identifique as relações de ancestralidade e parentesco entre alguns vértices.
Solução:
- \(c\) é ancestral de \(d\), \(e\), \(f\) e \(g\)
- \(c\) é pai de \(d\) e de \(e\)
- \(b\) não é nem ancestral nem descendente de \(c\) — eles estão em ramos diferentes da árvore
- \(b\) e \(c\) são filhos da raiz \(r\)
O nível e a altura também são definidos a partir da raiz:
Seja \(T\) uma árvore enraizada com raiz \(r\). O nível de um vértice \(v\), denotado \(\text{nível}(v)\), é o comprimento do caminho único de \(r\) a \(v\). A altura de \(T\) é o maior nível entre todos os vértices:
$$\text{altura}(T) = \max_{v \in V} \text{nível}(v)$$
Exemplo: nível e altura
Enunciado: Na mesma árvore do exemplo anterior (raiz \(r\), filhos \(b\) e \(c\), netos \(d\) e \(e\), bisnetos \(f\) e \(g\)), calcule o nível de cada vértice e a altura da árvore.
Solução:
- \(\text{nível}(r) = 0\)
- \(\text{nível}(b) = \text{nível}(c) = 1\)
- \(\text{nível}(d) = \text{nível}(e) = 2\)
- \(\text{nível}(f) = \text{nível}(g) = 3\)
- \(\text{altura}(T) = 3\)
Recursão: calculando a altura programaticamente
A definição de altura — “o maior nível entre todos os vértices” — é natural de calcular top-down (da raiz para as folhas), mas o jeito mais direto de programá-la é justamente o oposto: uma função recursiva bottom-up, que pergunta a altura de cada filho antes de responder a sua própria.
Representando a árvore como um dicionário de filhos — a forma mais simples de guardar uma árvore enraizada em Python — a altura de um vértice é 0 se ele não tem filhos (é uma folha), ou 1 mais a maior altura entre seus filhos, caso contrário:
filhos = {
"r": ["b", "c"],
"b": [],
"c": ["d", "e"],
"d": [],
"e": ["f", "g"],
"f": [],
"g": [],
}
def altura(no):
if not filhos[no]:
return 0
return 1 + max(altura(filho) for filho in filhos[no])
for no in filhos:
print(f"altura({no}) = {altura(no)}")altura(r) = 3
altura(b) = 0
altura(c) = 2
altura(d) = 0
altura(e) = 1
altura(f) = 0
altura(g) = 0Note que altura(r) = 3 é exatamente a altura da árvore \(T\) inteira
(a raiz “pergunta” recursivamente a altura de toda a estrutura abaixo
dela), e que altura(b) = altura(d) = altura(f) = altura(g) = 0 para
todas as folhas — batendo com o fato de que o nível de uma folha é o
maior nível “local” da sua própria subárvore (que é só ela mesma).
Essa é a mesma ideia recursiva por trás de quase todo algoritmo que
processa árvores: resolver o problema nas subárvores primeiro, e depois
combinar as respostas na raiz.
Esses conceitos aparecem por toda parte em ciência da computação — sempre que uma estrutura organiza dados hierarquicamente, é uma árvore enraizada por baixo do capô. O exemplo mais literal de todos é justamente o que abriu este artigo: um sistema de arquivos.
Aplicação: a árvore por trás de um sistema de arquivos
Todo sistema de arquivos é uma árvore enraizada: a raiz é a pasta
principal, cada pasta é filha de exatamente uma pasta-mãe, e os arquivos
são as folhas. Vamos construir uma pequena estrutura de projeto de
verdade (em uma pasta temporária, para o código ser executável em
qualquer máquina) e calcular seu nível e sua altura com o networkx:
import os
import tempfile
from pathlib import Path
import networkx as nx
with tempfile.TemporaryDirectory() as tmp:
raiz = Path(tmp) / "projeto"
(raiz / "src").mkdir(parents=True)
(raiz / "tests").mkdir()
(raiz / "src" / "main.py").touch()
(raiz / "src" / "utils.py").touch()
(raiz / "tests" / "test_main.py").touch()
(raiz / "README.md").touch()
G = nx.Graph()
for pasta_atual, subpastas, arquivos in os.walk(raiz):
pasta_atual = Path(pasta_atual)
for nome in subpastas + arquivos:
origem = str(pasta_atual.relative_to(raiz.parent))
destino = str((pasta_atual / nome).relative_to(raiz.parent))
G.add_edge(origem, destino)
print("É árvore?", nx.is_tree(G))
niveis = nx.shortest_path_length(G, raiz.name)
for no, nivel in sorted(niveis.items(), key=lambda x: (x[1], x[0])):
print(f"nível({no}) = {nivel}")
print("altura(projeto) =", max(niveis.values()))É árvore? True
nível(projeto) = 0
nível(projeto/README.md) = 1
nível(projeto/src) = 1
nível(projeto/tests) = 1
nível(projeto/src/main.py) = 2
nível(projeto/src/utils.py) = 2
nível(projeto/tests/test_main.py) = 2
altura(projeto) = 2os.walk percorre a árvore de diretórios de cima para baixo, exatamente
como fizemos manualmente nos exemplos anteriores — só que agora em uma
estrutura de arquivos de verdade, com pathlib cuidando dos caminhos.
Cada pasta ou arquivo aninhado um nível mais fundo aumenta o “nível” em
1, e a altura da árvore é, como sempre, o maior desses valores.
Árvores enraizadas em computação
- Árvore binária de busca: cada nó tem no máximo 2 filhos; nó da subárvore esquerda < nó < nó da subárvore direita
- Heap: árvore binária quase completa; nó pai ≥ filhos (max-heap) ou nó pai ≤ filhos (min-heap)
- Trie: árvore para armazenar strings, com caminhos da raiz até cada nó representando prefixos
- Árvore de decisão: usada em aprendizado de máquina; cada nó interno representa uma condição de decisão, e o nível em que ela aparece reflete sua ordem de avaliação
Exercícios #
Os exercícios a seguir estão em ordem crescente de dificuldade: os dois primeiros fixam as propriedades básicas de árvores e florestas, e o terceiro retoma a árvore geradora do exemplo anterior.
Exercício 1: Número de arestas
Enunciado: Quantas arestas tem uma floresta com 10 vértices e 3 componentes conexos?
Solução: Cada componente conexo com \(n_i\) vértices é uma árvore com \(n_i - 1\) arestas. Se os componentes têm \(n_1, n_2, n_3\) vértices com \(n_1 + n_2 + n_3 = 10\), o total de arestas é \((n_1 - 1) + (n_2 - 1) + (n_3 - 1) = 10 - 3 = 7\) arestas.
Exercício 2: Unicidade do caminho
Enunciado: Em uma árvore com 6 vértices formando o caminho \(1 - 2 - 3 - 4 - 5 - 6\) com aresta extra \(\{2, 5\}\), o grafo resultante é ainda uma árvore?
Solução: Não. O grafo tem 6 vértices e 6 arestas (o caminho tem 5 + a aresta extra = 6). Uma árvore com 6 vértices tem exatamente 5 arestas. Além disso, existe um ciclo: \(2 - 3 - 4 - 5 - 2\). Portanto, não é árvore.
Exercício 3: outra ordem, outra árvore geradora
Enunciado: Reveja o grafo \(G\) com a lista de arestas \(\{(a,b), (a,c), (b,c), (c,e), (a,e), (e,f), (a,f), (e,d), (c,d)\}\) do Exemplo 2 de árvore geradora. Escolha uma ordem diferente para essa lista de arestas e encontre uma árvore geradora de \(G\) diferente da obtida anteriormente.
Solução: por exemplo, percorrendo as arestas na ordem \((a,e), (e,f), (e,d), (a,b), (a,c), (c,e), (b,c), (a,f), (c,d)\) — aceitando cada aresta que não fecha um ciclo com as já escolhidas — obtemos o conjunto de arestas \(\{(a,e), (e,f), (e,d), (a,b), (a,c)\}\), que já conecta os 6 vértices com exatamente 5 arestas: uma árvore geradora diferente da do Exemplo 2. Qualquer outra ordem que gere uma árvore com as mesmas propriedades (conexa, acíclica, 5 arestas, 6 vértices) também está correta — o importante é perceber que a ordem de escolha das arestas determina qual árvore geradora específica se obtém.
Resumo #
| Conceito | Descrição |
|---|---|
| Árvore | Grafo conexo e acíclico |
| Floresta | Grafo acíclico (cada componente é árvore) |
| Folha | Vértice de grau 1 |
| Teorema 1 | Existe caminho único entre cada par de vértices \(\Leftrightarrow\) o grafo é árvore |
| Teorema 2 (\(m = n-1\)) | Toda árvore com \(n\) vértices tem \(n-1\) arestas |
| Excentricidade / Centro | \(e(v) = \max_w d(v,w)\); \(c(G)\) = vértices de excentricidade mínima |
| Centro de uma árvore | 1 vértice, ou 2 vértices adjacentes; encontrado removendo folhas iterativamente |
| Árvore balanceada | Subárvores de cada vértice com tamanhos parecidos (nas AVL, alturas que diferem de no máximo 1); altura logarítmica |
| Árvore geradora | Subgrafo gerador que é árvore; em geral não é única |
| Raiz | Vértice especial em árvores enraizadas |
| Ancestral / Descendente / Pai / Filho | Relações definidas pelo caminho único da raiz a cada vértice |
| Nível / Altura | \(\text{nível}(v)\) = comprimento do caminho da raiz a \(v\); \(\text{altura}(T) = \max_v \text{nível}(v)\) |
Próximos Passos #
Árvores são o esqueleto mínimo que mantém um grafo conexo — mas, por serem acíclicas, elas não servem para responder perguntas sobre grafos que têm ciclos e onde queremos percorrer a estrutura inteira de alguma forma específica: visitar cada aresta exatamente uma vez, ou visitar cada vértice exatamente uma vez. Essas perguntas motivam grafos eulerianos e hamiltonianos, tema do próximo artigo da série: trajetos eulerianos (que percorrem todas as arestas de um grafo) e ciclos hamiltonianos (que visitam todos os vértices), incluindo o famoso problema do caixeiro-viajante.
