Árvore geradora baratas (MST) em grafos

O problema da árvore geradora de custo mínimo é um problema fundamental sobre grafos não-dirigidos com custos nas arestas. (Há um problema semelhante para grafos dirigidos, mas ele é bem mais difícil.)

Árvore geradora mínima

Uma árvore geradora mínima de G é qualquer árvore geradora de G que tenha custo mínimo. Em outras palavras, uma árvore geradora T de G é mínima se nenhuma outra árvore geradora tem custo menor que o de T. Árvores geradoras mínimas também são conhecidas pela abreviatura MST de minimum spanning tree.

É claro que o problema tem solução se e somente se o grafo é conexo. Outra observação óbvia: se todos as arestas tiverem o mesmo custo então toda árvore geradora é uma MST.

Este capítulo faz uma introdução geral ao problema da MST. Algoritmos serão examinados em capítulos subsequentes.

Exemplo A. A figura mostra uma MST de um grafo não-dirigido com custos nas arestas. Os 250 vértices são pontos no plano e o custo de cada aresta v-w (há 1273 delas) é igual à distância geométrica entre os pontos v e w.

Exemplo B. Considere o grafo não-dirigido com custos nas arestas definido a seguir. (O custo de cada aresta é proporcional ao comprimento geométrico do segmento de reta que representa a aresta na figura.)

O conjunto de arestas 4-5 5-7 0-7 2-3 1-7 0-2 6-2 define uma árvore geradora do grafo. O custo dessa árvore é 35 + 28 + 16 + 17 + 19 + 26 + 40 = 181. Essa árvore é uma MST, embora isso não seja óbvio.

Exercícios 1

[Sedgewick 20.1] Mudança de escala. Seja T uma MST de um grafo não-dirigido G com custos nas arestas. Mostre que T continua sendo uma MST de G se o custo de cada aresta for multiplicado por uma constante p ≥ 0. (A propriedade continua válida se p for negativo?) Mostre que T continua sendo uma MST de G se somarmos uma constante q ao custo de cada aresta (a constante pode ser positiva ou negativa).
Suponha que todas as arestas de um grafo não-dirigido conexo têm o mesmo custo. Mostre que toda árvore geradora do grafo é uma MST.
Mostre que um grafo não-dirigido conexo com custos nas arestas pode ter mais de uma MST. (Por isso dizemos uma MST e não a MST.)
É verdade que quaisquer duas MSTs de um grafo não-dirigido têm pelo menos uma aresta em comum?
[Sedgewick 20.5] Suponha que os custos das arestas de um grafo não-dirigido conexo são distintos entre si (ou seja, não há duas arestas com o mesmo custo). Mostre que o grafo não-dirigido tem uma única MST.
[Sedgewick 20.6] Certo ou errado? Se um grafo não-dirigido tem uma única MST então os custos de suas arestas são distintos entre si.
Seja G um grafo não-dirigido conexo com custos nas arestas. Suponha que uma aresta e de G é mais cara que qualquer outra aresta de G. É verdade que nenhuma MST de G contém e?
Certo ou errado? Dadas duas árvores geradoras T e T ', se T é mais barata que T ' então T tem uma aresta mais barata que qualquer das arestas de T '.
[Sedgewick 20.25] Suponha que os custos das arestas de um grafo não-dirigido conexo são distintos entre si. Seja C um circuito do grafo. É verdade que a aresta mais barata de C pertence à (única) MST do grafo?
Seja T uma MST de um grafo não-dirigido com custos nas arestas. Suponha que um corte tem uma única aresta de custo mínimo. É verdade que T tem uma única aresta desse corte?

[Sedgewick figura 20.1] Tente encontrar uma MST no grafo não-dirigido com custos nas arestas descrito a seguir.

0-6  0-1  0-2  4-3  5-3  7-4  5-4  0-5  6-4  7-0  7-6  7-1
 51   32   29   34   18   46   40   60   51   31   25   21

[Sedgewick 20.21] Considere o grafo não-dirigido cujos vértices são os pontos no plano dados a seguir por suas coordenadas.
```
  0     1     2     3     4     5
(1,3) (2,1) (6,5) (3,4) (3,7) (5,3)
```
Suponha que as arestas do grafo são 1-0 3-5 5-2 3-4 5-1 0-3 0-4 4-2 2-3 e o custo de cada aresta v-w é igual ao comprimento do segmento de reta que liga os pontos v e w no plano. Tente encontrar uma MST desse grafo.
[Sedgewick 20.2] Subgrafo gerador conexo mínimo. Suponha que os custos das arestas de um grafo não-dirigido conexo G são todos estritamente positivos. Seja H um grafo de custo mínimo dentre todos os subgrafos não-dirigidos geradores conexos de G. Mostre que H é uma MST de G.
[Sedgewick 20.3] Repita o exercício anterior sob uma hipótese mais fraca: todo circuito de G tem pelo menos uma aresta de custo estritamente positivo.
[Sedgewick 20.4] Árvore de custo máximo. Como encontrar uma árvore geradora de custo máximo num grafo não-dirigido conexo com custos nas arestas?
CPT versus MST. Mostre que MSTs e CPTs (árvores de caminhos baratos) de grafos não-dirigidos podem ser muito diferentes. Dê um exemplo de um grafo não-dirigido conexo G com custos positivos nas arestas e uma MST T nesse grafo que tenha a seguinte propriedade: para todo vértice s existe um vértice t tal que a distância de s a t em G é diferente da distância de s a t em T. (Dica: existem exemplos com 4 vértices apenas.)

Critério de minimalidade baseado em circuitos

Dada uma MST de um grafo, não é necessariamente verdade que todas as arestas baratas estão na MST e todas as caras estão fora. Mas uma versão mais fraca dessa afirmação é verdadeira. Especificamente, a propriedade dos circuitos (propriedade insere-remove) do capítulo Árvores geradoras leva ao seguinte

Se denotarmos por c_a o custo de uma aresta a, podemos formular o critério assim: T é uma MST se e somente se c_e ≥ c_t para cada aresta e fora de T e qualquer aresta t do circuito fundamental de e.

Exemplo C. Considere o grafo não-dirigido com custos nas arestas definido a seguir. (Os custos das arestas não exatamente iguais aos do exemplo B.)

O conjunto de arestas 4-5 5-7 0-7 2-3 1-7 0-2 6-2 define uma árvore geradora T do grafo. A aresta 1-3 não tem custo máximo no circuito 1-3-2-0-7-1 pois ela é mais barata que a aresta 0-2. Portanto, T não é uma MST. (De fato, se substituirmos 0-2 por 1-3 na árvore T, teremos uma árvore geradora mais barata.)

Exercícios 2

Prove o critério de minimalidade baseado em circuitos. (Qual das duas partes da prova é mais fácil: a parte se ou a parte só se?) [Solução]
Seja T uma MST de um grafo não-dirigido G com custos nas arestas. Seja e uma aresta fora de T. É verdade que e é a única aresta de custo máximo no único circuito de T + e?
[Sedgewick 20.22] Seja a uma aresta de custo mínimo em um grafo não-dirigido conexo G. É verdade que a pertence a alguma MST de G? É verdade que a pertence a toda MST de G?
Seja C um circuito em um grafo não-dirigido conexo G com custos nas arestas. Suponha que uma aresta e de C é mais cara que qualquer outra aresta de C. É verdade que nenhuma MST de G contém e?
Seja G um grafo não-dirigido com custos nas arestas. Seja C um circuito e T uma MST de G. É verdade que toda aresta e de C que não está em T tem custo máximo em C? Ou seja, é verdade que nenhuma aresta de C é mais cara que e?
★ Análise de sensibilidade. Seja G um grafo não-dirigido com custos nas arestas e T uma MST de G. Seja e uma aresta fora de T e imagine alterar o custo de e mantendo os custos das demais arestas. Em quanto posso aumentar o custo de e sem que T deixe de ser uma MST? Em quanto posso diminuir o custo de e sem que T deixe de ser uma MST? Escreva uma função que responda essas perguntas.

Critério de minimalidade baseado em cortes

Dada uma MST de um grafo, não é necessariamente verdade que todas as arestas baratas estão na MST e todas as caras estão fora. Mas uma versão mais fraca dessa afirmação é verdadeira. Especificamente, a propriedade dos cortes (propriedade remove-insere) do capítulo Árvores geradoras leva ao seguinte

Se denotarmos por c_a o custo de uma aresta a, podemos formular o critério assim: T é uma MST se e somente se c_t ≤ c_e para cada aresta t de T e qualquer aresta e do corte fundamental de t.

Exemplo D. Considere o grafo não-dirigido com custos nas arestas definido a seguir. (Os custos das arestas não são exatamente iguais aos do exemplo B.)

Seja T a árvore geradora definida pelo conjunto de arestas 4-5 5-7 0-7 2-3 1-7 0-2 6-2. A aresta 0-2 não tem custo mínimo no corte 1-3 1-2 7-2 0-2 0-6 4-6 pois o custo de 0-2 é maior que o custo de 1-3. Portanto, T não é uma MST. (De fato, se substituirmos 0-2 por 1-3 em T, teremos uma árvore geradora mais barata.)

Exemplo E. Considere mais uma vez o grafo não-dirigido do exemplo B (a tabela de custos está reproduzida a seguir). Seja T a árvore geradora sugerida na figura. Cada aresta que não está em T tem custo máximo no seu circuito fundamental (verifique!). Segue daí que T é uma MST.

Podemos fazer uma verificação análoga para as arestas de T: cada aresta de T tem custo mínimo no seu corte fundamental (verifique!). Segue daí que T é uma MST.

Exercícios 3

Prove o critério de minimalidade baseado em cortes. (Qual das duas partes da prova é mais fácil: a parte se ou a parte só se?)
Seja T uma MST de um grafo não-dirigido G com custos nas arestas. Seja C um corte de G. É verdade que toda aresta t de T em C tem custo mínimo em C? Ou seja, é verdade que nenhuma aresta de C é mais barata que t?
Seja T uma MST de um grafo não-dirigido G com custos nas arestas. Seja t uma aresta de T. É verdade que t é mais barata que qualquer outra aresta do corte fundamental de t relativo a T?
★ [Sedgewick 20.26] Seja T uma MST de um grafo não-dirigido G com custos nas arestas. Suponha agora que uma das arestas de T é removida de G. Mostre como encontrar uma MST do novo grafo em tempo no pior caso proporcional ao número de arestas de G.
★ Análise de sensibilidade. Seja G um grafo não-dirigido com custos nas arestas e T uma MST de G. Seja t uma aresta de T e imagine alterar o custo de t (sem alterar os custos das demais arestas). Em quanto posso aumentar o custo de t sem que T deixe de ser uma MST? Em quanto posso diminuir o custo de t sem que T deixe de ser uma MST? Escreva uma função que responda essas perguntas.
Seja T uma árvore geradora de um grafo não-dirigido G com custos nas arestas. Prove que T satisfaz o critério de minimalidade baseado em circuitos se e somente se satisfaz o critério de minimalidade baseado em cortes.

Algoritmos

Há algoritmos muito eficientes para resolver o problema da MST. A maioria consome não mais que E log V unidades de tempo para processar um grafo não-dirigido com V vértices e E arestas. Nos capítulos seguintes examinaremos

Esses algoritmos têm caráter guloso (= greedy): em cada iteração, abocanham a aresta que parece mais promissora naquele momento sem se preocupar com o efeito global dessa escolha. Esses algoritmos são os protótipos da estratégia gulosa que resolve vários outros problemas computacionais.

Exercícios 4

[Sedgewick 20.27] Comece com uma árvore geradora qualquer T do grafo especificado abaixo. Transforme T numa MST tomando as arestas na ordem dada e aplicando, repetidamente, o critério de minimalidade baseado nos circuitos.
```
0-6  0-1  0-2  4-3  5-3  7-4  5-4  0-5  6-4  7-0  7-6  7-1
 51   32   29   34   18   46   40   60   51   31   25   21
```
Algoritmo. [Sedgewick 20.28]. Mostre que o seguinte algoritmo produz uma MST: Comece com uma árvore geradora T qualquer; escolha uma aresta fora de T, acrescente-a a T, e retire de T uma aresta máxima do circuito que se forma; repita enquanto não estabilizar.
Algoritmo. Mostre que o seguinte algoritmo produz uma MST: Comece com uma árvore geradora T qualquer; escolha uma aresta t de T, retire t de T, e coloque em seu lugar uma aresta mínima do corte fundamental de t relativo a T; repita enquanto não estabilizar.
[Sedgewick 20.18] Suponha dada uma função UGRAPHmstE() que coloca num vetor mst[] as arestas de uma árvore. Escreva uma função UGRAPHmst() que receba mst[] e calcule o vetor de pais pa[] da árvore.
Suponha dado um grafo não-dirigido com custos nos vértices e não nas arestas. Como encontrar uma árvore geradora de custo mínimo?

Árvores geradoras de custo mínimo (MST)