Uma árvore é o grafo que se obtém quando acrescentamos um arco anti-paralelo a cada arco de uma arborescência. Embora correta, essa caracterização de árvores não é conveniente como definição. É melhor adotar uma definição mais tradicional.

O primeiro passo da definição introduz um outro tipo de grafo: a floresta.

Florestas

Uma floresta (= forest) é um grafo sem ciclos não-triviais.

Para cada arco v-w da floresta, o caminho v-w-v é um ciclo, mas esse ciclo é trivial.

Por exemplo, o grafo definido pelo conjunto de arestas abaixo é uma floresta.
0-1 0-5 1-2 1-3 1-4 6-7 6-8

Florestas também são conhecidas como grafos acíclicos. Uma folha (= leaf) de uma floresta é qualquer vértice de grau 1.

Árvores

Uma árvore (= tree) é uma floresta conexa. Portanto, cada componente de uma floresta é um árvore.

Por exemplo, o grafo definido pelo conjunto de arestas 0-1 0-5 1-2 1-3 1-4 é uma árvore.

Não confunda árvores com arborescências. Uma árvore é um digrafo simétrico, enquanto uma arborescência é um digrafo não-simétrico. As palavras "raiz", "pai" e "filho" não fazem sentido numa árvore.

Propriedade 1: Para cada par s,t de vértices de uma árvore existe um e um só caminho simples de s a t.
Propriedade 2: Toda árvore com V vértices tem exatamente V-1 arestas.

Exercícios para Fixação
1. Essa afirmação está correta: "Toda árvore com V vértices tem exatamente V-1 arestas."? Porque?
2. Mostre que toda floresta com V vértices e C componentes tem exatamente V-C arestas.
3. Prove que toda floresta com pelo menos uma aresta tem pelo menos duas folhas.
4. Escreva uma função que reconheça florestas. Ao receber um grafo G, a função deve devolver 1 se G é uma floresta e devolver 0 em caso contrário.
5. Escreva uma segunda versão para a função do exercício anterior, que imprima um ciclo não-trivial imediatamente antes de devolver 0.
6. Escreva uma função que reconheça árvores. Ao receber um grafo G, a função devolve 1 se G é uma árvore e devolve 0 em caso contrário.

Referência: IME