Definição

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 (árvore radicada, árvore enraizada, árvore dirigida, etc).

Exemplos: 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

As duas figuras abaixo definem arborescências de raiz r:



Propriedades

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

Varredura em pré-ordem

Uma varredura em pré-ordem de uma arborescência é uma maneira sistemática de visitar os vértices da arborescência. Eis uma descrição recursiva da varredura em pré-ordem:
1. visite a raiz,
2. para cada filho v da raiz, faça uma varredura em pré-ordem da subarborescência com raiz v.

Quando a busca em profundidade é aplicado a uma arborescência com raiz 0 ela faz uma varredura em pré-ordem:

int count, ordem[MAXV];
int G[MAXV][MAXV]; //Grafo representado como Lista de adjacência
int grau[MAXV]; //Número de vértices adjacentes a cada vértice

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

void preordem(int r){
   count = 0; //não visitou ninguém
   visita(r); //vai visitar a raiz
}

void visita(int v){
   ordem[v] = count++; //v foi visitado neste valor de count e incrementa count
   for (int i = 0; i < grau[v]; ++i) //roda todos os adjacentes a v
      visitR(G[v][i]); //visita o outro lado deste arco
}

Vetor de pais

O vetor de pais de uma arborescência é um vetor, digamos pai tal que, para cada vértice w distinto da raiz, pai[w] é o pai de w. Quanto à raiz r, é muito conveniente adotar a definição pai[r] = r. Essa definição permite distinguir a raiz dos demais vértices, pois pai[w] ≠ w quando w não é a raiz. Exemplo: Eis o vetor de pais da arborescência do primeiro exemplo mostrado acima:
       v 0 1 2 3 4 5 6 7 8 9 10 11
pai[v] 0 0 1 1 3 3 0 6 6 6 0   10

Dado o vetor de pais, pai, de uma arborescência, é fácil determinar o caminho que leva da raiz a um dado vértice v: basta inverter a seqüência impressa pelo seguinte fragmento de código:

int x; //um vértice qualquer
for (x = v; pai[x] != x; x = pai[x]) //enquanto o pai não for igual ao filho continua andando (pai == filho significa que é a raiz)
 printf("%d-", x); //imprime vértice
printf("%d", x); //imprime vértice

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.

Exercícios para Fixação

1. Escreva o vetor pai para os dois grafos representados nas figuras acima.
2. Escreva o algoritmo preordem e visita para grafos represetandos através de listas de adjacências.
3. Escreva o conjunto D(v) para v = 3 para os dois grafos representados nas figuras acima.

Referência: IME