Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Arborescências

Os algoritmos de busca sugerem o seguinte conceito, que pode ser entendido como uma generalização do conceito de caminho simples. Uma arborescência (= rooted directed tree = search tree =  árvore de busca) é uma seqüência da forma

( v[0],  a[1], v[1],  a[2], v[2],  . . . , a[k], v[k] ),

onde  v[0], . . . , v[k]  são vértices distintos dois a dois,  a[1], . . . , a[k]  são arcos distintos dois a dois, e, para cada  j ,

a[ j]  é um arco da forma  (v[i], v[ j]) ,   com  i < j.

Para cada  j,  dizemos que a ponta inicial de  a[ j]  é o predecessor (ou pai) do vértice  v[ j]. O primeiro vértice da seqüência,  v[0],  é a raiz da arborescência. O número  j  é o índice ou posição do vértice  v[ j]  na arborescência.

Exemplo:  No grafo definido no exemplo 1 do capítulo O que é um grafo?, a seqüência  (6, d, 0, f, 4, b, 2)  é uma arborescência com raiz  6 . O predecessor do vértice  2  é o vértice  0 . O índice de  2 é  3 e o índice de seu predecessor é  1.

Para qualquer vértice  w  de uma arborescência, alguma subseqüência da arborescência é um caminho simples que começa na raiz  v[0]  da arborescência e vai até  w:  trata-se da subseqüência  (v[0],  . . . , pppw,  ppw,  pw,  w),  onde  pw  é o predecessor de w,  ppw  é o predecessor de pw,  etc.  

Exemplo:  No exemplo acima, o caminho que vai de  6  a  2  na arborescência é  (6, d, 0, b, 2) .

Exercícos

1. Quantos arcos tem uma arborescência com  t  vértices?

2. (Importante!)  Suponha que  (v[0],  a[1], v[1],  a[2], v[2],  . . . , a[k], v[k]), é uma arborescência. Quantos arcos da arborescência entram em  v[0] ?  Quantos arcos da arborescência entram em  v[ j],  para  j = 1 . . k ?

Representação de arborescências

Como representar uma arborescência usando as convenções do SGB? Basta registrar o predecessor de cada vértice. É claro que  v[0]  bem como os vértices fora da arborescência não têm predecessor. O predecessor de cada vértice pode ser confortavelmente acomodado em um utility field, digamos  pred ; assim,

v[ j]–>pred

é o predecessor de  v[ j].  Podemos convencionar que  v[0]–>pred  vale  v[0].  Para todo  w  fora da arborescência,  w–>pred  vale  NULL.

É claro que essa representação envolve uma certa perda de informação:  se, por exemplo, o grafo tem dois arcos da forma  (v[0], v[1]) , não saberemos qual dos dois faz parte da arborescência. A prática mostra, entretanto, que é perfeitamente possível conviver com a ambigüidade.

Exercícios

3. Suponha que cada vértice de um grafo do SGB tem um campo  pred  do tipo Vertex *.  Escreva uma função C que diga se  pred  define ou não uma arborescência. A função deve devolver a raiz da arborescência se a resposta for afirmativa e  NULL  se a resposta for negativa.

4. Suponha dado um certo conjunto  B  de arcos de um grafo (digamos que  a–>pertence == 1  se e só se  a  está em  B ). Escreva uma função C que decida se  B  é o conjunto de arcos de uma arborescência. A função deve definir os predecessores dos vértices em caso afirmativo.

Arborescências maximais e territórios

Uma arborescência é maximal se não existe arco no grafo com ponta inicial na arborescência e ponta final fora dela. É fácil perceber que

toda arborescência maximal com raiz  r  contém todos os vértices do território de  r .

É fácil deduzir daí que qualquer arborescência maximal com raiz  r  tem exatamente  |T|–1  arcos, onde  T  é o território de  r .

Exemplo:  Suponha que os vértices do grafo são cidades, que os arcos são estradas de mão única sem pavimentação, e que  r  é a cidade principal. Suponha que desejamos pavimentar o menor número possível de estradas de modo que seja possível viajar de  r  a qualquer outra cidade (mas não necessariamente de volta) por estradas pavimentadas.

Para evitar confusão com a terminologia de outros textos, convém esclarecer que em grafos simétricos com um só componente as arborescências maximais são conhecidas como árvores geradoras (= spanning trees).

Exercícios

5. Suponha que  B  é o conjunto de arcos de uma arborescência maximal com raiz  r . Mostre que  B  é mínimo com relação à seguinte propriedade: para qualquer vértice  v  no território de  r, existe um caminho de  r  a  v  que só usa arcos de  B .

Construção de arborescências maximais

A seguinte variante do algoritmo genérico de busca constrói uma arborescência maximal com raiz  r: 

r–>pred = r

declare  r  ativo

enquanto existe vértice ativo faça

escolha um vértice ativo  v 

para cada arco  a  que esteja saindo de  v  faça

w = a–>tip

se  w–>pred  não está definido então

w–>pred = v

declare  w  ativo

declare  v  inativo

A análise deste algoritmo é a melhor maneira de provar que toda arborescência maximal com raiz  r  contém todos os vértices do território de  r.

Dependendo de como o conjunto de vértices ativos é administrado, teremos uma arborescência de busca em largura ou uma arborescência de busca em profundidade (ou uma arborescência de busca que não é nenhuma das anteriores).

Exercícios

6. Implemente o algoritmo acima em C. Use a estrutura de dados do SGB. Use uma lista encadeada para administrar o conjuntos dos vértices ativos.

7. Repita o exercício anterior de modo a contruir uma arborescência "de busca em largura". Registre, para cada vértice, o seu índice (= posição) na arborescência; use um utility field para isso.

8. Repita o exercício anterior de modo a contruir uma arborescência "de busca em profundidade". Registre, para cada vértice, o seu índice (= posição) na arborescência; use um utility field para isso.

Exercícios

8. [Avançado. Arborescências Maximais de Comprimento Mínimo]  Suponha que cada arco do grafo tem um comprimento, que é um número inteiro não-negativo. (Na estrutura de dados do SGB, o comprimento de um arco  a  é  a–>len .) O comprimento de uma arborescência é a soma dos comprimentos dos seus arcos.

   Problema:  Dado um vértice  r, determinar, dentre as arborescências maximais com raiz  r , uma que tenha comprimento mínimo.

   Invente um algoritmo que resolva o problema. Escreva o algoritmo em C, usando as estruturas de dados do SGB. Veja a seção 3.5 ("Optimal directed subgraphs"), p. 81, do livro Graph Theory de Ronald Gould (editora Benjamin Cummings, 1988). Melhor: veja a seção 8.14 ("A special case: directed spanning trees"), p. 348, do livro Combinatorial Optimization: Networks and Matroids de E. Lawler (editora Holt, Rinehart and Winston, 1976). Veja também artigo de R. Karp em Networks, 1971, p. 265. Veja ainda artigo de E. Tarjan em Information Processing Letters, 1974, p. 25.

9. [Bem mais fácil que o anterior]  Escreva uma função C que resolva o problema da arborescência maximal de comprimento mínimo (veja exercício anterior) no caso em que o grafo é simétrico e o comprimento de cada arco da forma  (v,w)  é igual ao comprimento do mais curto dos arcos da forma  (w,v) .

   O módulo MILES_SPAN do SGB apresenta várias soluções para este problema; as soluções apresentadas lá usam estruturas de dados sofisticadas para tornar o algoritmo mais rápido. O presente exercício não tem esta preocupação: basta escrever uma função simples e razoavelmente eficiente.