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: etano, butano e isobutano.

Á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

Mostre que toda floresta com V vértices e C componentes tem exatamente V − C arestas.
Prove que toda floresta com pelo menos uma aresta tem pelo menos duas folhas.
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 antes de devolver 0. Compile e teste sua função. [Veja função de detecção de ciclos e função que imprime ciclo.]
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.
Escreva uma função que receba uma árvore G (representada por suas listas de adjacência) e um vértice r de G e transforme G numa arborescência com raiz r mediante eliminação de metade dos arcos de G.
Escreva uma função que transforme uma arborescência com raiz r (representada por suas listas de adjacência) em uma árvore mediante acrescimo de um arco antiparalelo a cada arco da arborescência.
Mostre que toda árvore tem no máximo dois vértices centrais, e se tiver dois então eles são adjacentes. Escreva uma função que calcule todos os vértices centrais de qualquer árvore dada.
Escreva uma função que construa uma árvore aleatória com V vértices. Cada vértices deve ter no máximo g vizinhos.