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 o conceito de maneira apenas vaga; veja páginas 84 e 91-92.)

Definição

A definição de arborescência exige uma sentença 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 são conhecidas por vários outros nomes.  Eis alguns sinônimos de arborescência:

• árvore radicada (= rooted tree),
• árvore enraizada,
• árvore dirigida (= directed tree),
• árvore de busca (= search tree).

Embora Sedgewick diga "árvore" no lugar de "arborescência", eu prefiro reservar a palavra "árvore" para outro conceito.   [Acho que "diárvore" seria um bom substituto para "arborescência".]

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
   • r é o único vértice de G  ou 
   • o digrafo G−r consiste em k arborescências disjuntas (ou seja, sem vértices em comum), com raízes r₁, … , r_k respectivamente,  e os arcos de G incidentes a r são r-r₁, … , r-r_k.
   Mostre que essa definição recursiva é equivalente à definição dada na seção anterior.
2. 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

3. Escreva uma função que construa uma arborescência aleatória com V vértices. Cada vértice deve ter no máximo f filhos.

Varredura em preordem

Uma varredura em preordem de uma arborescência é uma maneira sistemática de visitar os vértices da arborescência. Eis uma descrição recursiva da varredura em preordem:

1. visite a raiz,
2. para cada filho v da raiz, faça uma varredura em preordem da subarborescência com raiz v.

Quando a busca em profundidade é aplicada a uma arborescência com raiz 0 ela faz uma varredura em preordem:

static int conta, pre[maxV];

/* A função preorder recebe uma arborescência G com raiz r e visita os vértices de G em preordem. A ordem em que os vértices são visitados é registrada no vetor pre. */

void preorder (Digraph G, Vertex r) { 
   conta = 0;
   visitR(G, r);
}

void visitR (Digraph G, Vertex v) { 
   link p; 
   pre[v] = conta++; 
   for (p = G->adj[v]; p != NULL; p = p->next)
      visitR(G, p->w); 
}

Exercícios

4. Visite os vértices da arborescência abaixo em preordem.

   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.

5. Considere a arborescência descrita abaixo. Note que ela tem raiz 0.

                   0-1 1-2 1-3 0-4 4-5 4-6
   

   Considere a seguinte numeração dos vértices

             v     0  1  2  3  4  5  6  7
         pre[v]    0  1  2  4  3  4  5  6
   

   Essa numeração corresponde a uma varredura em preordem?

6. [Postorder]  Defina varredura em pós-ordem de uma arborescência. Escreva uma função que execute a varredura de uma arborescência em pós-ordem.

Vetor de pais

O vetor de pais de uma arborescência é um vetor, 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:

             v     0  1  2  3  4  5  6  7  8  9  10 11
      parent[v]    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 v:  basta inverter a sequência impressa pelo seguinte fragmento de código:

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

Subdigrafos que são arborescências

Seja T uma arborescência e suponha que T é subdigrafo de um digrafo G.  Seja v-w um arco de G que tem ambas as pontas em T.

• Se v-w é um arco de T, dizemos que v-w é um  arco de arborescência (= tree arc).  É claro que nesse caso v é o pai de w em T.
• Se w é um descendente de v em T, mas não é filho de v,  dizemos que v-w é um arco descendente (= descendant arc).
• Se w é um ancestral de v em T, dizemos que v-w é um arco de retorno (= back arc).  No caso especial em que w é o pai de v em T, dizemos também que v-w é um arco-pai  (= parent arc).
• Se w não é ancestral de v nem descendente de v,  dizemos que v-w é um arco cruzado (= cross arc).

Desses quatro tipos de arco de G, apenas o primeiro pertence a T.