Grafos: Árvore Geradora Mínima

Prévia do material em texto

Grafos: Árvore Geradora 
ORD 
DFW 
SFO 
LAX 
80
2 
1843 
1233 
337 
ÁRVORE GERADORA 
ÁRVORE GERADORA MÍNIMA 
ÁRVORE GERADO MÁXIMA 
2 
3 
Subgrafos 
Um subgrafo S de um grafo G 
é um grafo tal que: 
n  Os vértices de S são um 
subconjunto dos vértices de G 
n  As arestas de S são um 
subconjunto das arestas de G 
Um subgrafo gerador 
(spanning sugraph) de G é 
um subgrafo que contém 
todos os vértices de G 
Subgrafo 
Subgrafo gerador 
4 
Conectividade 
Um grafo G é conectado se 
existe um caminho entre 
qualquer par de vértices de G 
Componente conectado de 
um grafo G é um subgrafo 
conectado de G 
Uma árvore é um grafo 
conectado que não possui 
ciclos 
Grafo conectado 
Grafo não-conectado com dois 
componentes conectados 
Árvore 
5 
Árvore Geradora 
Uma árvore geradora 
(spanning tree) de um 
grafo conectado é um 
subgrafo gerador que é 
uma árvore 
Uma árvore geradora não 
é única, a menos que o 
grafo seja uma árvore 
Existem muitas aplicações 
de árvores geradoras: por 
exemplo, no projeto de 
redes de comunicação 
Grafo 
Árvore geradora 
6 
Árvore Geradora Mínima 
ORD 
PIT 
ATL 
STL 
DEN 
DFW 
DCA 
10 
1 
9 
8 
6 
3 
2 5 
7 
4 
Subgrafo Gerador: 
n  Subgrafo de um grafo G 
contendo todos os vértices 
de G 
Árvore Geradora 
n  Subgrafo gerador conectado 
e sem ciclos 
Árvore Geradora Mínima 
n  Árvore geradora de um grafo 
valorado com mínimo peso 
total de arestas 
n  Minimum Spanning Tree 
(MST) 
Exemplos de Aplicações 
n  Redes de Comunicações 
7 
Algoritmo: Prim-Jarnik’s 
Inicia por um vértice arbitrário s, e cresce a árvore 
geradora mínima como uma “nuvem” de vértices 
n  Particiona o grafo em dois conjuntos de vértices, aqueles dentro 
e fora da árvore geradora mínima 
Armazena em cada vértice v: 
n  v.dist = menor peso de uma aresta conectando v a um vértice na 
nuvem 
Em cada passo: 
n  Adiciona-se à árvore geradora mínima o vértice u com o menor 
valor dist dentre os vértices de fora da nuvem 
n  Atualiza-se os valores dist dos vértices adjacentes ao vértice u 
fora da nuvem 
8 
Prim-Jarnik’s Algorithm 
(cont.) 
Uma fila de prioridade Q 
armazena cada vértice v 
fora nuvem 
Vértice v armazena: 
n  v.dist = chave para Q 
n  v.pai = vértice predecessor 
Aresta e armazena: 
n  e.peso = peso 
Fila de Prioridade Q: 
n  insert(Q, v, k): insere 
item v com chave k. 
n  remove(Q): remove e 
retorna item com menor 
chave 
n  replaceKey(Q, v, k): 
substitui por k a chave do 
item v e reorganiza a fila 
PrimJarnikMST(G, s) 
 
 Q ← nova min-heap (fila de prioridade) 
 for all v ∈ G.vertices 
 if v = s 
 v.dist = 0 
 else 
 v.dist = +∞ 
 v.pai = ∅ 
 v.label = “fora” //da nuvem 
 insert(Q, v, v.dist) 
 
while ~isEmpty(Q) 
 u ← remove(Q) 
 v.label =“dentro” //da nuvem 
 for all e ∈ G.incidente(u) 
 z ← G.endpoint(u,e) 
 if z.label=“fora” & z.dist > e.peso 
 z.dist = e.peso 
 z,pai = u 
 replaceKey(Q, z, z.dist) 
9 
Exemplo: Árvore Geradora Mínima 
B 
D 
C 
A 
F 
E 
7 
4 
2 
8 
5 
7 
3 
9 
8 
0 7 
2 
8 ∞ 
∞ 
B 
D 
C 
A 
F 
E 
7 
4 
2 
8 
5 
7 
3 
9 
8 
0 7 
2 
5 ∞ 
7 
B 
D 
C 
A 
F 
E 
7 
4 
2 
8 
5 
7 
3 
9 
8 
0 7 
2 
5 ∞ 
7 
B 
D 
C 
A 
F 
E 
7 
4 
2 
8 
5 
7 
3 
9 
8 
0 7 
2 
5 4 
7 
10 
Exemplo: Árvore Geradora Mínima 
B 
D 
C 
A 
F 
E 
7 
4 
2 
8 
5 
7 
3 
9 
8 
0 3 
2 
5 4 
7 
B 
D 
C 
A 
F 
E 
7 
4 
2 
8 
5 
7 
3 
9 
8 
0 3 
2 
5 4 
7 
11 
Análise 
Algoritmos Prim-Jarník representa um exemplo de algoritmo 
guloso que leva a soluções globalmente ótimas 
Prim-Jarník utilizando uma min-heap (priority queue) 
n  Pode ser implementado com tempo de execução O((V + E) log V) 
w  Cada vértice V é inserido uma vez na fila à O(V) 
w  While loop executa V vezes, cada remove tem complexidade O(logV) à O(V logV) 
w  For loop executa E vezes no total, cada replaceKey O(logV) à O(E logV) 
12 
Resumo 
Subgrafos e árvore geradora 
n  Um subgrafo gerador (spanning sugraph) de G é um subgrafo que 
contém todos os vértices de G 
n  Uma árvore geradora (spanning tree) é um subgrafo gerador que é 
uma árvore 
Caminhamento em grafos para cálculo da árvore geradora 
n  Procedimento sistemático para explorar um grafo através da 
examinação de todos os seus vértices e arestas 
n  Busca em amplitude (Breadth-First Search - BFS) 
n  Busca em largura (Depth-First Search – DFS) 
n  Árvore geradora mínima 
Próxima aula: Grafos valorados e caminhos mínimos 
(shortest-paths) 
13 
Bibliografia 
M. T. Goodrich and R. Tamassia, Algorithm Design: 
Foundations, Analysis and Internet Examples, John 
Wiley & Sons, 2002. 
T. H. Cormen, C. E. Leiserson, and R. L. Rivest, 
Introduction to Algorithms, MIT Press, 3rd Edition, 
2009. 
Material adicional: 
n  N. Ziviani, Projeto de Algoritmos, Thomson, 2a. Edição, 2004. 
n  S. Skiena e M. Revilla, Programming Challenges: The 
Programming Contest Training Manual, Springer-Verlag, 2003. 
Exercício 
■  Existem 8 pequenas ilhas em um 
arquipélago e o governo deseja 
construir 7 pontes conectando-as 
de forma que cada ilha possa ser 
alcançada de qualquer outra ilha 
através de uma ou mais pontes 
■  O custo de construção de uma 
ponte é proporcional ao seu 
comprimento 
■  As distâncias entre os pares de 
ilhas são dadas na tabela 
■  Ache quais pontes devem ser 
construídas para que o custo da 
construção seja mínimo 
1 2 3 4 5 6 7 8 
1 - 240 210 340 280 200 345 120 
2 - - 265 175 215 180 185 155 
3 - - - 260 115 350 435 195 
4 - - - - 160 330 295 230 
5 - - - - - 360 400 170 
6 - - - - - - 175 205 
7 - - - - - - - 305 
8 - - - - - - - -