Esta página trata da restrição do problema da arborescência maximal de peso mínimo a digrafos simétricos com função-peso simétrica. A restrição é mais conhecida como "problema da árvore geradora de peso mínimo de um grafo". Eu prefiro não usar esse palavreado tradicional pelas razões indicadas abaixo.
Esta página é inspirada no capítulo 23 de CLRS. Veja também a seção 4.5 de KT. Veja ainda o verbete Minimum spanning tree na Wikipedia.
Convém lembrar que um digrafo é simétrico se não tem laços e, para cada arco uv, o par vu também é um arco. Suponha agora que cada arco uv de um digrafo simétrico tem um peso inteiro p(uv), que pode ser positivo, negativo, ou nulo. Diremos que a função-peso p é simétrica se
p(uv) = p(vu) para cada arco uv.
O peso de uma arborescência T é a soma dos pesos dos arcos de T. Esta página estuda o seguinte caso especial do problema da arborescência maximal de peso mínimo:
Problema da arborescência maximal de peso mínimo em digrafo simétrico: Dado um digrafo simétrico G, um vértice r de G e uma função-peso simétrica sobre os arcos de G, encontrar uma r-arborescência maximal de G que tenha peso mínimo.
Uma r-arborescência T de G é maximal se o seu conjunto de vértices é igual ao território de r, ou seja, se não existe arco de G com ponta inicial em T e ponta final fora de T.
Uma r-arborescência de G é ótima se for maximal e tiver peso mínimo. Nosso problema, portanto, é encontrar uma r-arborescência ótima de G.
Eu gostaria muito de seguir a tradição e dizer árvore, grafo (não dirigido) e aresta no lugar de arborescência, digrafo simétrico e arco. Infelizmente, nenhuma estrutura de dados é capaz de representar, diretamente, as arestas (não dirigidas) de um grafo. Todas as estruturas representam arestas como pares antiparalelos de arcos de um digrafo simétrico.
Eu também gostaria muito de seguir a tradição e dizer árvore geradora no lugar de arborescência maximal. Para fazer isso, entretanto, eu teria que supor que os grafos submetidos aos algoritmos são conexos. Ocorre que para decidir se um grafo (ou digrafo simétrico) é conexo eu teria que executar um algoritmo muito semelhante ao algoritmo da arborescência ótima que está em discussão!
O problema que vamos estudar é bem mais fácil em digrafos simétricos que em digrafos arbitrários. Isso acontece porque digrafos simétricos com função-peso simétrica têm a seguinte propriedade: dados dois vértices r e s ligados por um caminho, uma r-arborescência maximal de peso mínimo tem o mesmo peso que uma s-arborescência maximal de peso mínimo.
O célebre algoritmo de Prim — descoberto por R.C. Prim em 1957 — resolve nosso problema. Podemos descrevê-lo vagamente assim: em cada iteração, acrescente à arborescência o arco mais leve dentre os que ligam a arborescência ao resto do digrafo. Segue uma descrição mais precisa.
No início de cada iteração do algoritmo, temos uma r-arborescência T do digrafo. Todos os vértices de T são considerados pretos e os demais são considerados brancos. Dizemos que o conjunto de arcos com ponta inicial preta e ponta final branca é a franja de T. Cada iteração consiste no seguinte:
| o se a franja de T está vazia |
| oooo então devolva T e pare |
| oooo senão escolha um arco da franja que tenha peso mínimo |
| oooo senão seja uv o arco escolhido |
| oooo senão acrescente uv a T e pinte v de preto |
No início da primeira iteração, r é o único vértice de T. A menos que o digrafo seja conexo, a execução do algoritmo termina antes que todos os vértices fiquem pretos.
O algoritmo tem um caráter guloso, pois escolhe o arco uv com base em considerações locais, sem qualquer preocupação com o objetivo global de obter uma r-arborescência maximal de peso mínimo.
É claro que o algoritmo produz uma r-arborescência maximal. Resta saber se ela é ótima. Para isso, basta mostrar que, no início de cada iteração,
T faz parte de uma r-arborescência ótima.
Eis um esboço da demonstração. Suponha que T faz parte de uma r-arborescência ótima R no início de uma certa iteração. Durante esta iteração, o arco uv será acrescentado a T. Se este arco já está em R não é preciso se preocupar com mais nada. Suponha agora que uv não está em R.
A arborescência R tem um único caminho, digamos C, de r a v. Algum arco xy de C está na franja de T e portanto o seu peso não é menor que o de uv. Seja Y o segmento terminal de C que começa em y (e vai até v). Se trocarmos cada arco ij de Y pelo seu inverso ji, teremos um caminho Y′ de v a y. Então
(R − xy + uv) − Y + Y′
é uma r-arborescência. Essa nova arborescência tem peso não superior ao de R pois Y e Y′ têm o mesmo peso (uma vez que o digrafo tem cusos simétricos) e o peso de xy não é menor que o de uv. Concluímos que a nova r-arborescência é tão ótima quanto R. Assim, no início da próxima iteração, T pertence a uma r-arborescência ótima.
Essa ideia está correta?
A única dificuldade de implementação do algoritmo de Prim está na administração da franja. Podemos resolver essa dificuldade de diversas maneiras:
As primeiras possibilidades são detalhadas na página Algoritmo de Prim para Digrafos Representados por Matrizes, onde o digrafo é representado por sua "matriz de pesos". A terceira será examinada abaixo.
Suponha que os vértices do digrafo são 1, 2, …, n e que os arcos são dados por listas de adjacência. Para cada vértice v, seja
chave[v]
o peso do arco mais leve dentre os que estão na franja e têm ponta final v. O algoritmo mantém os vértices numa fila com prioridades dadas por chave. Cada iteração acrescenta à arborescência um vértice que tem chave mínima juntamente com o arco da franja que tem peso igual à chave.
Para simplificar o código, suporemos que nosso digrafo simétrico é conexo. (É fácil remover essa restrição.) Nosso algoritmo não devolve uma r-arborescência maximal de peso mínimo mas apenas o seu peso. (Não é difícil modificar o código para que o algoritmo devolva a arborescência propriamente dita.)
| Prim-com-Fila-de-Vértices (n, Adj, p, r) |
| 11 o para v crescendo de 1 até n faça |
| 12 oooo chave[v] ← ∞ |
| 13 oooo cor[v] ← branco |
| 14 o cor[r] ← preto |
| 15 o total ← 0 |
| 16 o para cada x em Adj[r] faça |
| 17 oooo chave[x] ← p(rx) |
| 18 o Q ← Cria-Fila-Vazia ( ) |
| 19 o para v crescendo de 1 até n faça |
| 10 oooo se v ≠ r então Insere-na-Fila (v, Q) |
| 11 o enquanto Q não está vazia faça |
| 12 oooo v ← Extrai-Min (Q) |
| 13 oooo total ← total + chave[v] |
| 14 oooo para cada x em Adj[v] faça |
| 15 ooooooo se cor[x] = branco e p(vx) < chave[x] |
| 16 oooooooooo então Diminui-Chave (x, Q, p(vx)) |
| 17 oooo cor[v] ← preto |
| 18 o devolva total |
O subalgoritmo Cria-Fila-Vazia cria uma fila vazia com prioridades ditadas por chave. O subalgoritmo Extrai-Min retira da fila um vértice com chave mínima. O comando Diminui-Chave(x,Q,p(vx)) na linha 16 faz chave[x] ← p(vx) e o que mais for preciso para restaurar a estrutura da fila de prioridades Q.
Os seguintes invariantes explicam o funcionamento do algoritmo: no início de cada iteração,
Suponha que a fila Q é implementada como um min-heap. Como Q tem no máximo n elementos, cada execução de Insere-na-Fila consome tempo Ο(lg n) e portanto o bloco de linhas 1-10 (que trata do pré-processamento) consome tempo Ο(n lg n).
Cada execução de Extrai-Min consome tempo Ο(lg n) (uma vez que Q tem no máximo n elementos). O bloco de linhas 12-17 será repetido no máximo n vezes, pois um vértice sai da fila em cada iteração e não há inserção de novos vértices na fila. Portanto, o consumo de tempo total de todas as execuções das linhas 12-13 e 17 é Ο(n lg n).
Cada execução de Diminui-Chave consome tempo Ο(lg n). Esta cota superior também vale para cada execução do bloco de linhas 15-16. Para cada valor fixo de v, o bloco de linhas 15-16 é executado tantas vezes quantos são os arcos com ponta inicial v. Como temos um valor diferente de v em cada iteração do bloco de linhas 12-17, cada execução das linhas 15-16 examina um arco diferente. Assim,
o tempo total dedicado a todas as execuções do bloco de linhas 15-16 está em Ο(m lg n),
sendo m o número de arcos do digrafo. A conclusão final é que o algoritmo Prim-com-Fila-de-Vértices cuja fila é implementada como um heap consome
Ο((n+m) lg n)
unidades de tempo. A estimativa é justa pois no pior caso o algoritmo consome Ω((n+m) lg n) unidades de tempo.
Se m = Ω(n²), ou seja, se o digrafo é "denso", o consumo de tempo está em Ω(n² lg n) no pior caso. Nesse caso, uma implementação mais simples é assintoticamente melhor, pois consome Ο(n²) unidades de tempo.
Qual a relação entre o consumo de tempo e o tamanho, digamos N, de uma instância do nosso problema? Como os digrafos estão sendo representados por listas de adjacência, é razoável dizer que N = n+m. Podemos dizer então que Prim-com-Fila-de-Vértices consome Ο(N lg N) unidades de tempo.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 3 | 4 | 5 | ||||||
| 2 | 3 | 9 | 6 | ||||||
| 3 | 9 | 8 | 2 | ||||||
| 4 | 4 | 6 | 6 | 7 | |||||
| 5 | 5 | 6 | 8 | 6 | 9 | 8 | |||
| 6 | 2 | 9 | |||||||
| 7 | 6 | 8 | |||||||
| 8 | 7 | 8 | 8 | ||||||
| 9 |
| 11 o para v crescendo de 1 até n faça |
| 12 oooo chave[v] ← ∞ |
| 13 oooo cor[v] ← branco |
| 14 o chave[r] ← 0 |
| 15 o total ← 0 |
| 18 o Q ← Cria-Fila-Vazia ( ) |
| 19 o para v crescendo de 1 até n faça |
| 10 oooo Insere-na-Fila (v, Q) |