Arvore Geradora

Árvore Geradora
Mínima
prof. Leandro G. M. Alvim

Árvore Geradora
Mínima (MST)
• Seja um grafo G=(V,E) com custos ce nas

aretas, uma MST é um subconjunto de arestas T c E tal que T é um árvore geradora cuja soma dos custos das aretas é a menor possível. (Kleinberg e Tardos,
2005)

Árvore Geradora
Mínima (MST)

• Seja um grafo G=(V,E) com custos ce nas

aretas, uma MST é um subconjunto de arestas T c E tal que T é um árvore geradora cuja soma dos custos das aretas é a menor possível. (Kleinberg e Tardos,
2005)

• Teorema de Caley ( n^(n-2) árvores)
• Inviável por força bruta

Árvore Geradora
Mínima (MST)

Árvore Geradora
Mínima (MST)

Algumas Aplicações
• Projeto de Redes
• Tv a cabo, rede elétrica, hidráulica, computadores, estradas

• Agrupamento
• Algoritmos aproximativos para problemas da classe NP-Difícil (ex. Caixeiro Viajante)

TV a Cabo
• Conectar regiões com o menor custo possível • Certos “caminhos” precisam de cabos maiores • Em certos “caminhos” é necessário

passar o cabo em um maior profundidade

Agrupamento

• Agrupar vértices em k grupos
• Encontrar MST
• Remover k-1 maiores arestas

Algoritmos para MST
• Kruskal
•

•

Comece com T={}. Insira, em ordem crescente de custo, arestas que não gerem ciclos

Prim

•

Escolha um vértice s. Construa uma árvore T a partir de s adicionando o vértice cuja aresta possui menor custo e que possua apenas um vertice em T.

• Remoção Reversa
•

Comece com T=E. Seja as arestas em ordem decrescente, remova cada aresta e que não desconecta T.

Ciclo
• Conjunto de arestas na forma (a,b),
(b,c), ..., (y,z).

Ciclo C = {(1,2),
(2,3),(3,4), (4,5),
(5,6), (6,1)}

Conjunto de Corte
• Um corte é um subconjunto dos vértices

de S. O correspondente conjunto de corte
D é o subconjunto de arestas com exatamente um vértice em S.
Corte S = {5,4,8}
Conjunto de corte D = {(5,6),
(5,7), (5,3), (4,3),
(8,7)}

Kruskal
Arestas ordenadas a 13
10

12 b 5

c

23
50

d

e
17

Aresta

Peso

{b,d}
{a,d}
{a,b}
{a,c}
{d,e}
{c,e}