Arborescências em grafos

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 sequência da forma

onde v₀, … , v_k são vértices distintos dois a dois, a₁, … , a_k são arcos distintos dois a dois, e, para cada j, a_j é um arco da forma (v_i, v_j) tal que

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 sequência, v₀, é a raiz da arborescência. O número j é o índice ou posição do vértice v_j na arborescência.

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

Exercícios 1

Quantos arcos tem uma arborescência com t vértices?
[Importante!] Suponha que (v₀, a₁, v₁, a₂, v₂, … , a_k, v_k), é uma arborescência. Quantos arcos da arborescência entram em v₀? 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₀ 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,

é o predecessor de v_j. Podemos convencionar que v₀pred vale v₀ e que wpred vale NULL para todo w fora da arborescência.

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

Exercícios 2

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 uma arborescência ou não. A função deve devolver a raiz da arborescência se a resposta for afirmativa e NULL se a resposta for negativa.
Suponha dado um certo conjunto B de arcos de um grafo (digamos que apertence ≡ 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

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

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 3

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

rpred = r

declare r ativo

enquanto existe vértice ativo faça

escolha um vértice ativo v

para cada arco a saindo de v faça

w = atip

se wpred não está definido então

wpred = v

declare w ativo

declare v inativo

A análise deste algoritmo prova 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 é de nenhum dos tipos anteriores).

Exercícios 4

Implemente o algoritmo acima em C. Use a estrutura de dados do SGB. Use uma lista encadeada para administrar o conjuntos de vértices ativos.
Repita o exercício anterior de modo a construir 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.
Repita o exercício anterior de modo a construir 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 5

[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 é alen.) O comprimento de uma arborescência é a soma dos comprimentos dos seus arcos.
Problema: Dado um vértice r, encontrar, 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.
[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.