Algoritmos para Grafos, via Sedgewick | Índice remissivo

Arborescências

Esta página introduz um tipo simples mas importante de digrafo: a arborescência. [O livro de Sedgewick define arborescências de maneira apenas vaga; veja páginas 84 e 91-92.]

Definição

A definição de arborescência exige é um tanto longa e convoluída. Uma arborescência é um digrafo em que

não existem vértices com grau de entrada maior que 1,
existe exatamente um vértice com grau de entrada 0,
cada um dos vértices é término de um caminho com origem no único vértice que tem grau de entrada nulo.

O único vértice com grau de entrada nulo é a raiz da arborescência. É claro que todos os vértices diferentes da raiz têm grau de entrada igual a 1. Arborescências também são conhecidas por vários outros nomes. Eis alguns sinônimos de arborescência: árvore radicada (= rooted tree), árvore enraizada (= rooted tree), árvore dirigida (= directed tree), árvore de busca (= search tree). (Acho que o neologismo diárvore também seria um bom sinônimo de arborescência.) [Embora Sedgewick diga árvore no lugar de arborescência, eu prefiro reservar a palavra árvore para outro conceito.]

Exemplo: O conjunto de arcos abaixo define um arborescência com raiz 0.

     0-1 1-2 1-3 3-4 3-5 0-6 6-7 6-8 6-9 0-10 10-11

Exercícios 1

Seja G um digrafo e r um de seus vértices. Dizemos que G é uma arborescência com raiz r se
1. r é o único vértice de G ou
2. os arcos de G incidentes a r são r-s, r-t, r-u, … e o digrafo G - r consiste em arborescências disjuntas (ou seja, sem vértices em comum) com raízes s, t, u, …
Mostre que essa definição recursiva é equivalente à definição dada na seção anterior.
Escreva uma função que decida se um dado digrafo é ou não uma arborescência. Em caso afirmativo, a função deve devolver a raiz da arborescência. Em caso negativo, a função deve devolver -1.

Propriedades

É fácil constatar que, para todo vértice v de uma arborescência, existe um e apenas um caminho simples que começa na raiz e termina em v.

É fácil constatar também que toda arborescência com V vértices tem exatamente V - 1 arcos.

Pais e filhos

Todo vértice w de uma arborescência, exceto a raiz, tem um pai: trata-se do único vértice v tal que v-w é um arco.

Para qualquer vértice v de uma arborescência, cada vértice adjacente a v é um filho de v. Vértice sem filhos são chamados folhas (= leaves) ou vértices externos (= external nodes).

Ancestrais, descendentes e subarborescências

Em uma arborescência, um vértice v é ancestral de um vértice w se o único caminho que vai da raiz até w passa por v. Nessas mesmas condições, diz-se que w é um descendente de v. É claro que todo vértice é descendente da raiz.

Um ancestral próprio de um vértice w é qualquer ancestral de w exceto o próprio w. Analogamente, um descendente próprio de um vértice v é qualquer descendente de v que seja diferente de v.

Para qualquer vértice v da arborescência, seja D(v) o conjunto de todos os descendentes de v. O conjunto de todos os arcos que têm ambas as pontas em D(v) define uma arborescência com raiz v. Diremos que esta é a subarborescência com raiz v.

Exercícios 2

Escreva uma função que construa uma arborescência aleatória com V vértices. Faça isso de modo que cada vértice tenha no máximo f filhos.

Varredura em pré-ordem

A busca em profundidade de uma arborescência a partir da raiz é conhecida como varredura da arborescência em pré-ordem. A ordem em que os vértices são visitados pode ser descrita recursivamente assim:

visite a raiz,
para cada filho v da raiz, faça uma varredura em pré-ordem da subarborescência com raiz v.

É um bom exercício escrever uma versão especializada de DIGRAPHdfs que faça uma varredura em pré-ordem de uma arborescência. Também é um bom exercício considerar a varredura em pós-ordem.

Exercícios 3

Visite os vértices da arborescência abaixo em pré-ordem.
```
     0-1 1-2 1-3 3-4 3-5 0-6 6-7 6-8 6-9 0-10 10-11
```
Registre a ordem em que os vértices são visitados num vetor pre indexado pelos vértices.
Considere a arborescência definida pelos arcos 0-1 1-2 1-3 0-4 4-5 4-6. Note que ela tem raiz 0. Considere a seguinte numeração dos vértices:
```
         v     0  1  2  3  4  5  6
     pre[v]    0  4  6  5  1  2  3
```
Essa numeração corresponde a uma varredura em pré-ordem?
Escreva uma versão especializada de DIGRAPHdfs que receba uma arborescência e sua raiz r e faça uma varredura da arborescência em pré-ordem. (Essa versão especializada é ligeiramente mais simples que DIGRAPHdfs porque não precisa verificar, repetidamente, se já visitou um vértice.) [Solução]
[Pós-ordem] A varredura em pós-ordem de uma arborescência consiste no seguinte: para cada filho v da raiz, faça uma varredura em pós-ordem da subarborescência com raiz v; depois, visite a raiz. Escreva uma função que execute a varredura de uma arborescência em pós-ordem.

Vetor de pais

Uma arborescência pode ser representada, como qualquer outro digrafo, por sua matriz de adjacência ou por suas listas de adjacência. Mas arborescências admitem uma representação especial mais simples: o vetor de pais. O vetor de pais de uma arborescência é um vetor indexado pelos vértices, digamos parent, tal que, para cada vértice w distinto da raiz,

parent[w] é o pai de w.

[Sedgewick escreve st no lugar do meu parent, pois está pensando na expressão spanning tree.] Quanto à raiz r, é muito conveniente adotar a definição parent[r] = r . Essa definição permite distinguir a raiz dos demais vértices, pois parent[w] != w quando w não é a raiz.

Exemplo: Eis o vetor de pais da arborescência de um dos exemplos acima:

            w    0  1  2  3  4  5  6  7  8  9  10  11
     parent[w]   0  0  1  1  3  3  0  6  6  6   0  10

Dado o vetor de pais, parent, de uma arborescência, é fácil determinar o caminho que leva da raiz a um dado vértice w: basta inverter a sequência

     w parent[w] parent[parent[w]] parent[parent[parent[w]]] ... r

que pode ser impressa pelo seguinte fragmento de código:

     Vertex x;
     for (x = w; parent[x] != x; x = parent[x])
        printf( "%d-", x);
     printf( "%d", x);