Exemplo 1: Uma arborescência com vértices a, b, … , k, l e raiz a.
Esta página discute uma classe de digrafos simples mas importantes: as arborescências.
Veja apêndice B.5.2 e seção 10.4 de CLRS. Veja também o verbete Rooted tree na Wikipedia.
Uma arborescência (ou árvore radicada, ou árvore com raiz) é um digrafo com
tal que o território de r contém todos os vértices do digrafo. O vértice r é a raiz da arborescência.
Uma r-arborescência é uma arborescência com raiz r. É claro que todos os vértices diferentes de r têm grau de entrada igual a 1. É fácil constatar que, para todo vértice v de uma r-arborescência, existe um e apenas um caminho que começa em r e termina em v. (Veja um dos exercícios abaixo.)
Exemplo 1: Uma arborescência com vértices a, b, … , k, l e raiz a.
Toda arborescência com n vértices tem exatamente
n − 1 arcos.
Prova: Seja W o conjunto de todos os vértices exceto a raiz. Há uma bijeção entre o conjunto A de arcos da arborescência e o conjunto W: a imagem de cada arco uv é sua ponta final v. (Essa correspondência é, de fato, uma bijeção pois cada vértice em W tem grau de entrada 1.) A existência da bijeção garante que |A| = |W|. A prova termina com a observação de que |W| = n−1.
Outra maneira de formular a prova: observe que, em qualquer digrafo, a soma dos graus de entrada de todos os vértices é igual ao número de arcos do digrafo.
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 e mais útil: o vetor de predecessores (ou vetor de pais). Trata-se do vetor pai definido da seguinte maneira: para cada vértice v distinto da raiz,
pai[v] é o único vértice u tal que uv é um arco.
Quanto à raiz r, é muito conveniente adotar a definição
pai[r] = r
(apesar de rr não ser um laço). Essa definição permite distinguir r dos demais vértices, pois pai[v] ≠ v quando v ≠ r. [O CLRS prefere usar a convenção pai[r] = nil.] A arborescência definida na figura 1, por exemplo, tem o seguinte vetor de predecessores:
| a | b | c | d | e | f | g | h | i | j | k | l |
| a | a | a | a | b | b | c | c | c | d | f | f |
Dado o vetor de predecessores, digamos pai, de uma arborescência, é fácil determinar o caminho que leva da raiz a um dado vértice v: basta construir a sequência
v, pai[v], pai[pai[v]], etc.
até chegar a r e imprimir a sequência de-trás-pra-frente. Eis um algoritmo recursivo que faz o serviço:
| Imprime-Caminho (v) |
| 1 o se pai[v] = v |
| 2 oooo então imprima v |
| 3 oooo senão Imprime-Caminho (pai[v]) |
| 4 oooo senão imprima v |
Veja a seguir uma versão iterativa do algoritmo. O comando Cria-Pilha (v) cria uma pilha com um só elemento igual a v. O comando Coloca-na-Pilha (x,S) coloca x no topo da pilha S. O comando Tira-da-Pilha (S) remove o elemento que está no topo da pilha S.
| Imprime-Caminho-It (v) |
| 1 o S ← Cria-Pilha (v) |
| 2 o enquanto pai[v] ≠ v faça |
| 3 oooo Coloca-na-Pilha (pai[v], S) |
| 4 oooo v ← pai[v] |
| 5 o enquanto S não estiver vazia faça |
| 6 oooo u ← Tira-da-Pilha (S) |
| 7 oooo imprima u |
O vetor de predecessores, digamos pai, de uma arborescência descreve a arborescência completamente: o conjunto dos vértices da arborescência é o conjunto dos índices do vetor e o conjunto dos arcos da arborescência é o conjunto de todos os pares da forma (pai[v],v) onde v é qualquer vértice para o qual pai[v] ≠ v.
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. Para cada vértice v da arborescência, denotaremos por
Z(v)
o conjunto de todos os descendentes de v. Observe que v pertence a Z(v). Se w pertence a Z(v) mas é diferente de v, diremos que w é descendente próprio de v e v é ancestral próprio de w.
Para todo vértice v da arborescência, seja A(v) o conjunto dos arcos que têm ambas as pontas em Z(v). O digrafo
(Z(v), A(v)) é uma arborescência
com raiz v. Diremos que esta é a subarborescência com raiz v ou a subarborescência de v.
