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
-
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.