Esta página discute os subdigrafos de um digrafo que têm a estrutura de uma arborescência.
Um digrafo H é subdigrafo de um digrafo D se todo vértice de H é vértice de D e todo arco de H é arco de D. Uma arborescência de um digrafo D é qualquer arborescência que seja subdigrafo de D. [Quem sabe teria sido melhor dizer subarborescência de um digrafo.]
Uma r-arborescência T de um digrafo D é maximal (ou geradora) se o seu conjunto de vértice é igual ao território de r em D, ou seja, se não existe arco de D que tenha ponta inicial em T e ponta final fora de T. [O adjetivo geradora é uma tradução inadequada de spanning. Meu uso do adjetivo geradora foge à tradição, uma vez que a expressão "arborescência geradora" é tradicionalmente usada apenas nos casos em que o território de r cobre todos os vértices do digrafo.] [Quem sabe deveríamos adotar o termo r-esqueleto no lugar de r-arborescência maximal.]
Problema da arborescência maximal: Dado um vértice r de um digrafo, encontrar uma r-arborescência maximal do digrafo.
O algoritmo que resolve o problema é essencialmente o mesmo que calcula o território de r. Ele devolve o vetor de predecessores que representa a arborescência procurada. Vamos supor que os vértices do digrafo são 1, … , n e que o digrafo é dado por suas listas de adjacência Adj[1..n].
| Arborescência-Maximal (n, Adj, r) |
| 11 o para u crescendo de 1 até n faça |
| 12 oooo pai[u] ← nil |
| 13 o pai[r] ← r |
| 14 o L ← Cria-Lista(r) |
| 15 o enquanto L não estiver vazia faça |
| 16 oooo u ← Retira-da-Lista(L) |
| 17 oooo para cada v em Adj[u] faça |
| 18 ooooooo se pai[v] = nil |
| 19 oooooooooo então pai[v] ← u |
| 10 oooooooooo então Insere-na-Lista(v, L) |
| 11 o devolva pai[1..n] |
Antes da primeira iteração, os pais dos vértices estão indefinidos. Esse estado indefinido é representado por nil. [Como os vértices do digrafo são 1, … , n, poderíamos usar 0 no lugar de nil.] Em virtude do teste na linha 8, é importante que pai[r] seja diferente de nil. Esta é a razão para a linha 3.
Durante o processo iterativo, o algoritmo usa uma lista de vértices análoga à usada pelo algoritmo Território. Se as rotinas Cria-Lista, Retira-da-Lista e Insere-na-Lista consumirem tempo constante (isto é, uma quantidade de tempo independente do tamanho do digrafo) então nosso algoritmo consumirá tempo Ο(n+m).
Seja T uma r-arborescência maximal de um digrafo D. Em relação a T, os arcos de D no território de r podem ser assim classificados: um arco uv que não pertencem a T é
Cada arco no território de r pertence a T ou é de um e apenas um desses três tipos. Essa classificação é útil para discutir as propriedades de diferentes tipos de arborescências maximais, como as que veremos adiante.
Dado um vértice r de um digrafo D, uma r-arborescência das distâncias de D é qualquer r-arborescência maximal T de D que tenha a seguinte propriedade: para todo vértice v no território de r, a distância de r a v em T é igual à distância de r a v em D.
Problema da arborescência das distâncias: Dado um vértice r de um digrafo D, encontrar uma r-arborescência de distâncias em D.
Para resolver o problema, basta usar uma simples adaptação do algoritmo Distâncias. O algoritmo devolve o vetor de predecessores que representa a arborescência procurada.
| Arborescência-de-Distâncias (n, Adj, r) |
| 11 o para u crescendo de 1 até n faça |
| 12 oooo pai[u] ← nil |
| 13 o pai[r] ← r |
| 14 o F ← Cria-Fila(r) |
| 15 o enquanto F não estiver vazia faça |
| 16 oooo u ← Sai-da-Fila(F) |
| 17 oooo para cada v em Adj[u] faça |
| 18 ooooooo se pai[v] = nil |
| 19 oooooooooo então pai[v] ← u |
| 10 oooooooooo então Entra-na-Fila(v, F) |
| 11 o devolva pai[1..n] |
Tal como no algoritmo Distâncias, a fila de vértices F usa a política FIFO.
Uma arborescência de distâncias pode também ser chamada de arborescência de busca em largura.
Em relação a qualquer r-arborescência de distâncias, todo arco direto ou cruzado uv é tal que d(v) ≤ d(u)+1, sendo d(x) a distância de r a x.
a f-distância de r a v em T é igual à f-distância de r a v em D.
Escreva um algoritmo que encontre uma r-arborescência de f-distâncias em um digrafo dado. Inspire-se no algoritmo Dijkstra.
Suponha que cada arco uv de um digrafo tem um peso numérico f(uv). O peso de uma arborescência do digrafo é a soma dos pesos de seus arcos. O peso de uma arborescência T será denotado por f(T). Diremos que uma r-arborescência maximal T tem peso mínimo se
f(T) ≤ f(T′)
para toda r-arborescência maximal T′ do digrafo.
Problema da arborescência maximal de peso mínimo: Dado um vértice r de um digrafo cujos arcos têm pesos numéricos, encontrar uma r-arborescência maximal de peso mínimo.
O problema também é conhecido como optimum branchings problem. A solução do problema é muito interessante mas não muito fácil. Veja a seção 4.9 de KT.
| Busca-em-Profundidade (n, Adj, r) |
| o para u crescendo de 1 até n faça |
| oooo cor[u] ← branco |
| oooo pai[u] ← nil |
| o B-em-Prof (r, cor) |
| o devolva pai[1..n] |
| B-em-Prof (u, cor) |
| 11 o cor[u] ← cinza |
| 12 o para cada v em Adj[u] faça |
| 13 oooo se cor[v] = branco |
| 14 ooooooo então pai[v] ← u |
| 14 ooooooo então B-em-Prof (v, cor) |
| 15 o cor[u] ← preto |
Em relação a qualquer r-arborescência de busca em profundidade, todo arco reverso pertence a um ciclo. Reciprocamente, todo ciclo do digrafo tem um arco reverso. Por outro lado, arcos cruzados não pertencem a ciclos. Pode-se dizer que o algoritmo de busca em profundidade resolve o seguinte
Problema da arborescência de busca em profundidade: Dado um vértice r de um digrafo, encontrar uma r-arborescência maximal do digrafo que tenha as seguintes propriedades: (1) todo ciclo tem pelo menos um arco reverso e (2) nenhum ciclo contém arco cruzado.