Árvores Abrangentes de Custo Mı́nimo
Em inglês, Minimum Spanning Trees (MST)
Fernando Lobo
Algoritmos e Estrutura de Dados II
1 / 18
Minimum Spanning Tree
I
Input: grafo G = (V , E ) não orientado, conexo. Cada arco
(u, v ) ∈ E tem um peso associado → w (u, v ).
I
Output: Um conjunto de arcos A ⊆ E tal que:
1. A é uma árvore que conecta todos os nós do grafo (A é uma
spanning tree), e
P
2. w (A) = (u,v )∈A w (u, v ) é mı́nimo.
I
Problema tem muitas aplicações práticas. Por exemplo, na
construção de uma rede de comunicações.
2 / 18
Exemplo de uma MST
Custo: 6 + 5 + 9 + 7 + 15 + 8 + 3 = 53
3 / 18
Propriedades de uma MST
I
Tem |V | − 1 arcos.
I
Não tem ciclos.
I
Pode não ser única.
Vamos ver dois algoritmos distintos para obter uma MST. Ambos
são exemplos de algoritmos greedy.
4 / 18
Problema tem subestrutura óptima
MST T :
(outros arcos do grafo não aparecem)
5 / 18
Problema tem subestrutura óptima
Se retirarmos um arco (u, v ) ∈ T , ficamos com duas sub-árvores:
T1 e T2
6 / 18
Problema tem subestrutura óptima
Teorema
I
I
A sub-árvore T1 é uma MST do grafo G1 = (V1 , E1 ), o
sub-grafo de G induzido pelos nós de T1 .
I
V1 = nós de T1
I
E1 = {(x, v ) ∈ E : x, y ∈ V1 }
A mesma coisa para T2 .
7 / 18
Demonstração
Por redução ao absurdo
I
w (T ) = w (T1 ) + w (T2 ) + w (u, v )
I
Se existisse uma spanning tree T10 com menor custo que T1
em G1 , então T 0 = {T10 ∪ T2 ∪ (u, v )} seria uma spanning tree
de G com menor custo que T , o que é uma contradição.
8 / 18
Propriedade de escolha greedy
I
O problema tem outra propriedade importante: Uma escolha
óptima local também é uma escolha óptima global → greedy
choice property.
9 / 18
Propriedade de escolha greedy
Para vermos isso, necessitamos de algumas definições:
I
Um corte (S, V − S) é uma partição dos nós V em dois
conjuntos: S e V − S.
I
Um arco (u, v ) ∈ E atravessa o corte (S, V − S) se um dos
extremos estiver em S e o outro em V − S.
I
Um corte respeita A sse não existir nenhum arco em A que
atravesse o corte.
I
Um arco diz-se leve se o seu peso for o mı́nimo de todos os
arcos que atravessam o corte (pode haver mais do que um
arco leve).
10 / 18
Exemplo
I
Corte (S, V − S)
I
Temos 3 arcos que atravessam o corte: (x, y ), (u, v ), (p, z).
I
(u, v ) é um arco leve para o corte (S, V − S).
11 / 18
Definição de um arco seguro (safe edge)
I
Seja A um conjunto de arcos ⊆ MST.
I
(u, v ) é um arco seguro para A sse A ∪ {(u, v )} ⊆ MST.
Teorema:
I
Seja A um subconjunto de uma MST, e seja (S, V − S) um
corte que respeita A. Se (u, v ) for um arco leve para o corte
(S, V − S), então (u, v ) é um arco seguro para A.
I
Por outras palavras, (u, v ) pertence a uma MST.
12 / 18
Demonstração
A → arcos a vermelho. (u, v ) é um arco leve.
13 / 18
Demonstração (cont.)
I
Seja T uma MST que contém A e que não inclui (u, v ).
I
Se não contém (u, v ), terá de conter pelo menos outro arco
que atravessa o corte (S, V − S). Seja esse arco (x, y ).
I
Então (x, y ) está no caminho de u ; v em T
(ver figura, caminho p).
14 / 18
Demonstração (cont.)
I
Se retirarmos (x, y ), partimos T em 2 sub-árvores.
Acrescentando (u, v ) juntamos outra vez as sub-árvores e
obtemos uma nova spanning tree
T 0 = T − {(x, y )} ∪ {(u, v )}.
I
Como (u, v ) é um arco leve,
=⇒
w (u, v ) ≤ w (x, y )
=⇒
w (T 0 ) ≤ w (T )
=⇒
T 0 é uma MST
15 / 18
Algoritmo genérico para obter uma MST
I
Isto dá origem a um algoritmo genérico para obter uma MST.
I
Algoritmo mantém um conjunto A de arcos que é sempre um
subconjunto de alguma MST.
I
Inicialmente A = ∅
I
A cada iteração acrescentamos um arco a A mantendo o
invariante que A continue a ser um subconjunto de uma MST
=⇒ apenas acrescentamos arcos seguros a A.
16 / 18
Pseudocódigo
Generic-MST(G )
A=∅
while A is not a spanning tree
find an edge (u, v ) that is safe for A
A = A ∪ {(u, v )}
return A
17 / 18
Algoritmo genérico para obter uma MST
I
A parte interessante é como descobrir os arcos seguros.
I
Na próxima aula veremos dois algoritmos que são exemplos
concretos deste algoritmo genérico.
1. Algoritmo de Prim: Começa com um nó s qualquer e cresce
uma árvore A a partir de s. Em cada iteração, acrescenta o
arco (u, v ) de custo mı́nimo em que um dos extremos pertence
a A.
2. Algoritmo de Kruskal: Começa com A = ∅. Ordena os arcos do
grafo por ordem crescente de peso. A cada iteração acrescenta
o arco (u, v ) a A desde que isso não dê origem a um ciclo.
18 / 18