Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Seminário Grafos

Algoritmo de Boruvka
by

Raphael Castro

on 21 September 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Seminário Grafos

Alunos:
Antonio Carlos Aldebaran Ribeiro Pinto
Camila Bastos
Gabrielle Moretti de Souza
Raphael Vinicius Castro Silva
Renata Faria de Oliveira

Professor:
Douglas Castilho Algoritmo de Borůvka O objetivo do algoritmo de Borůvka é encontrar uma árvore geradora mínima em um grafo. Objetivo Características do Grafo Projetos de Redes de Telecomunicação.
Projetos de Rodovias, Ferrovias, etc.
Projetos de Redes de Transmissão de Energia.
Projetos de Circuitos Integrados. Aplicações O Algoritmo de Boruvka, consiste em 2 passos(no caso de grafos conexos): O Algoritmo Acompanhamento Borůvka x Prim x Kruskal Dúvidas?! Robert Sedgewick, Algorithms in C (part 5: Graph Algorithms), 3rd. edition, Addison-Wesley/Longman, 2002.
http://pt.wikipedia.org/wiki/Algoritmo_de_Boruvka (acesso em 19 de setembro de 2012)
http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm (acesso em 19 de setembro de 2012)
http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/boruvka.html (acesso em 19 de setembro de 2012)
GOODRICH, Michael T.; TAMASSIA, Roberto. Projeto de Algoritmos: Fundamentos, Análise e Exemplos da Internet. Porto Alegre: Bookman, 2004. p. 369-370 Bibliografia Pesos de arestas distintos e positivos.
Grafo não orientado.
Grafo conexo (se for aplicado a um grafo desconexo, o algoritmo produzirá uma AGM para cada componente). Borůvka x Prim x Kruskal O algoritmo de Borůvka não usa uma fila de prioridades como os algoritmos de Prim e Kruskal.

A adição de arestas é feita em fases,em que para cada fase se adicionam várias arestas. Em cada fase determina-se as arestas mais curtas que ligam cada sub-árvore com outra. Em seguida adiciona-se todas essas arestas.

É um algoritmo com uma velocidade de convergência muito rápida, por isso é ideal para implementação em computadores paralelos já que a AGM de cada um dos subgrafos pode ser calculada em uma máquina diferente(no caso de grafos desconexos). Ele foi inicialmente desenvolvido por Otakar Boruvka em 1926, onde forneceu uma solução para encontrar a distribuição mais econômica através de uma rede de energia .

O algoritmo foi redescoberto por Choquet em 1938 e novamente por Florek , Lukasiewicz , Perkal , Steinhaus , e Zubrzycki em 1951, e depois por Sollin até o início da década de 1960 . Este algoritmo é frequentemente chamado algoritmo Sollin. História 1 - Para cada vértice do grafo, escolher a aresta de menor peso que "sai" dele. 2 - Agrupar cada conjunto de vértices ligados como um único vértice e executar novamente o passo 1 até que cheguemos em somente um único vértice. X={} Acompanhamento X={} Acompanhamento X={} Acompanhamento X={} Acompanhamento X={} Acompanhamento X={} Acompanhamento X={} Acompanhamento X={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a)} Todas as arestas selecionadas são adicionas a AGM. Acompanhamento X={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a)} Terminamos o passo 1 do algoritmo, agora devemos agrupar os vértices ligados em um único vértice. Acompanhamento X={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a)} Separamos os conjuntos e os renomeamos, formando um novo grafo, da seguinte forma: SG1={(a,b),(h,a)} e V1={a,b,h}
SG2={(c,i)} e V2={c,i}
SG3={(d,e),(f,e),(g,f)} e V3={d,e,f,g} Onde SG1,SG2 e SG3 tornam-se cada um, um novo vértice. Acompanhamento Agrupando os vértices, e observando no grafo original as arestas que ligam esses conjuntos de vértices. Grafo não orientado e ponderado com pesos distintos.
Grafo conexo, se for desconexo, o algoritmo retornará uma AGM para cada componente. Características do Grafo Acompanhamento Executamos novamente o passo 1, mas agora no novo grafo. X={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a)} Acompanhamento Quais são as arestas selecionadas no passo 1? Acompanhamento Depois de adicionadas as arestas na AGM, executamos o passo 2, agrupando os vértices ligados. X={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a),(b,c)(h,g)} X={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a),(b,c)(h,g)} Acompanhamento Feito o agrupamento, chegamos a único vértice e então o algoritmo é finalizado. X={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a),(b,c)(h,g)} Acompanhamento Temos, então, a AGM do grafo original. X={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a),(b,c)(h,g)} SG4={(a,b),(c,i),(d,e),(f,e),(g,f),(h,a),(b,c)(h,g)}
V4={a,b,c,d,e,f,g,h,i} DÚVIDAS?! Número de passos do algoritmo: O(lg V)
Número de arcos analisados em cada passo: O(E)
Manutenção das árvores em cada passo: O(E)
Logo, é possível assegurar O(E lg V) Borůvka x Prim x Kruskal Fila de prioridade baseada em amontoados (heap)
Quando um vértice é extraído da fila Q, implica actualização de Q
Cada vértice é extraído apenas 1 vez O(V)
Actualização de Q: O(lg V)
Então, O(V lg V)
Para cada arco (i.e. O(E)) existe no pior-caso uma actualização de Q
em O(lg V)
Complexidade algoritmo Prim: O(V lg V +E lg V)
Logo, é possível assegurar O(E lg V) porque grafo é ligado Borůvka x Prim x Kruskal Depende da implementação das operações sobre conjuntos disjuntos
Inicialização: O(E lg E) devido à ordenação dos arcos
Operações sobre os conjuntos disjuntos
O(V) operações de Make-Set
O(E) operações de Find-Set e Union
Com estruturas de dados adequadas (árvores com compressão de caminhos e união por categorias) para conjuntos disjuntos é possível
estabelecer que O((V +E) a(E,V))
Como |E| ≥ V −1 porque o grafo é ligado, então temos O(E a(E,V))
Logo, é possível assegurar O(E lg E)
Dado que E < V2, obtém-se também O(E lg V) Borůvka x Prim x Kruskal
Full transcript