Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Florestas e árvores

Uma árvore é o grafo que se obtém quando acrescentamos um arco antiparalelo 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

1. Mostre que toda floresta com V vértices e C componentes tem exatamente V-C arestas.
2. Prove que toda floresta com pelo menos uma aresta tem pelo menos duas folhas.
3. 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.  Escreva uma segunda versão de sua função que imprima um ciclo não trivial imediatamente antes de devolver 0. Compile e teste sua função.
4. 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.
5. Escreva uma função que construa uma árvore aleatória com V vértices. Cada vértices deve ter no máximo g vizinhos.