............................... deprecated ......................

Arborescências

Esta página discute uma classe de grafos 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.

O que é uma arborescência?

Uma arborescência (= arborescence) (ou árvore radicada, ou árvore com raiz) (= rooted tree) é um grafo com

tal que todos os vértice do grafo estão ao alcance de r. O vértice r é a raiz (= root) 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.

   a tree

Exercícios 1

  1. Que acontece se eliminarmos a condição  exatamente um vértice com grau de entrada 0  da definição de arborescência?
  2. Que acontece se eliminarmos a condição  todos os vértices estão ao alcance de r da definição de arborescência?
  3. Seja T uma arborescência com raiz r. Mostre que, para todo vértice v de T, existe apenas um caminho de rv.
  4. Suponha que um grafo D tem as seguintes propriedades:  (1) todo vértice tem grau de entrada 1;  (2) todos os vértices estão ao alcance de um determinado vértice r.  É verdade que rr é um arco do grafo? É verdade que Drr é uma arborescência?
  5. [Importante]  Seja V o conjunto {1,  …  , n}.  Seja f uma função de V−{1} em V tal que f(j) < j para cada j.  Seja A o conjunto de todos os pares da forma  (f(j),j).  Mostre que (V,A) é uma arborescência com raiz 1.
  6. Suponha que um vértice r de um grafo tem as seguintes propriedades:  (1) para todo vértice v diferente de r, existe um e um só caminho de rv ;  (2) r não pertence a um ciclo.  Mostre que o grafo é uma arborescência.
  7. Quantos arcos tem uma arborescência com n vértices?
  8. Escreva um algoritmo que decida se um dado grafo é ou não é uma arborescência.
  9. Mostre que todo heap é um tipo especial de arborescência.

Número de arcos

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 grafo, a soma dos graus de entrada de todos os vértices é igual ao número de arcos do grafo.

Representação por vetor de predecessores

Uma arborescência pode ser representada, como qualquer outro grafo, 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 (= parent array) (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

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 . se pai[v] = v
2 .ooo então imprima v
3 .ooo senão Imprime-Caminho (pai[v])
4 .ooo senão imprima v

Veja a seguir uma versão iterativa do algoritmo. O comando Nova-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 . S := Nova-Pilha (v)
2 . enquanto pai[v] ≠ v faça
3 .ooo Coloca-na-Pilha(pai[v], S)
4 .ooo v := pai[v]
5 . enquanto S não estiver vazia faça
6 .ooo u := Tira-da-Pilha (S)
7 .ooo imprimau

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.

Ancestrais, descendentes e subarborescências

Em uma arborescência, um vértice v é ancestral (= ancestor) 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 (= descendant) 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 grafo

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

Exercícios 2

  1. Escreva uma versão especializada de busca em largura para arborescências.
  2. Escreva uma versão especializada de busca em profundidade para arborescências.
  3. Escreva um algoritmo que imprima os vértices de uma arborescência em pós-ordem. Aplique o algoritmo à arborescência da figura 1.
  4. Escreva um algoritmo que imprima os vértices de uma arborescência em pré-ordem. Aplique o algoritmo à arborescência da figura 1.