Árvores geradoras de custo mínimo (MST)
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
Seja G um
grafo não-dirigido com custos nas arestas.
O custo de cada aresta pode ser
positivo ou negativo.
O custo de um
subgrafo não-dirigido
T de G
é a soma dos custos das arestas de T.
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.
Problema da MST:
Dado um grafo não-dirigido com custos nas arestas,
encontrar uma árvore geradora mínima do grafo.
É 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.)
4-5 4-7 5-7 0-7 1-5 0-4 2-3 1-7 0-2 1-2 1-3 2-7 6-2 3-6 6-0 6-4
35 37 28 16 32 38 17 19 26 36 29 34 40 52 58 93
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
Critério de minimalidade baseado em circuitos:
Uma árvore geradora T de um grafo não-dirigido com custos nas arestas
é uma MST
se e somente se
toda aresta e fora de T
tem custo máximo no
circuito fundamental de e relativo a T.
Se denotarmos por ca
o custo de uma aresta a,
podemos formular o critério assim:
T é uma MST
se e somente se ce
≥ ct
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.)
4-5 4-7 5-7 0-7 1-5 0-4 2-3 1-7 0-2 1-2 1-3 2-7 6-2 3-6 6-0 6-4
35 37 28 16 32 38 17 19 26 36 25 34 40 52 58 93
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
Critério de minimalidade baseado em cortes:
Uma árvore geradora T de um grafo não-dirigido com custos nas arestas
é uma MST
se e somente se
cada aresta t de T
tem custo mínimo
no corte fundamental de t
relativo a T.
Se denotarmos por ca
o custo de uma aresta a,
podemos formular o critério assim:
T é uma MST se e somente se ct
≤ ce
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.)
4-5 4-7 5-7 0-7 1-5 0-4 2-3 1-7 0-2 1-2 1-3 2-7 6-2 3-6 6-0 6-4
35 37 28 16 32 38 17 19 26 36 25 34 40 52 58 93
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.
4-5 4-7 5-7 0-7 1-5 0-4 2-3 1-7 0-2 1-2 1-3 2-7 6-2 3-6 6-0 6-4
35 37 28 16 32 38 17 19 26 36 29 34 40 52 58 93
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?