Problema da Árvore Geradora Mínima
Transcrição
Problema da Árvore Geradora Mínima
Instituto Federal do Espírito Santo Campus Serra Problema da Árvore Geradora Mínima Diego Pasti Jefferson Rios Sumário Apresentação do Problema da AGM.......................................3 Raízes do Problema Definindo o Problema O Problema da AGM nos dias de hoje Algoritmo Geral......................................................................4 Apresentando Obtendo a Árvore Geradora Mínima Regra Prova Algoritmo de Kruskal.............................................................6 Apresentando o Algoritmo Algoritmo de Prim..................................................................7 Apresentando o Algoritmo Exercícios...............................................................................8 Referências.............................................................................9 2 Apresentação do Problema Alusão Histórica do Problema Com o aumento das atividades Fabris a partir da Revolução Industrial, e o crescimento das zonas urbanas, foi necessário desenvolver e aprimorar diversos serviços, por exemplo, rodovias, esgotos, linhas de energia. Dessa forma acabou surgindo à necessidade de atender esses serviços a “todos os cantos das cidades” o que levou a desenvolver métodos que garantissem os menores custos possíveis com tais empreendimentos. Descrição do Problema em si Gerar a partir de um Grafo não-direcional, conexo e com “pesos” em cada aresta, uma arvora acíclica que interligue todos os pontos (vértices) e que tenha o menor custo total. Aonde é usado atualmente O problema da árvore geradora mínima aparece em uma série de aplicações (Chunde, 1996;Chang & Lee, 1999; Raidl & Julstrom, 2003), por exemplo, na instalação de linhas telefônicas (ou elétricas) entre um conjunto de localidades, utilizando a infra-estrutura das rodovias com o menor uso de material. Outros casos como análise de clusters, armazenamento de informações, dentre outros, também podem ser resolvidos por essa modelagem, que possui eficientes algoritmos como Kruskal, Prim e Sollin (Ahuja et al., 1993). 3 Algoritmo Geral Apresentação do Algoritmo Considere um grafo conexo e não-direcionado G=(V,E), onde cada Aresta (u,v) pertence a E tem um custo w(u,v) associado a ela. Então desejamos encontra um subconjunto T pertence a E que conecte todos Vértices de G e cuja soma total do custo de suas Arestas definida por seja minimizada. Sabendo que T é acíclica e conecta todos os Vértices de G a consideramos uma Árvore, e como seu custo total é minimizado a chamamos de Árvore Geradora Mínima ou Árvore Espalhada Mínima. Obtendo a AGM Suponha que temos um grafo conexo e não orientado G= (V,E) com uma função de custo de w: , onde desejamos encontrar uma AGM para G através do Algoritmo Geral. O Algoritmo Geral constrói a AGM adicionando uma aresta por vez, ele administra um conjunto de arestas A, onde A é um subconjunto de alguma AGM. A cada etapa do processo o Algoritmo define uma aresta (u,v) para ser acrescentada a A sem violar assim sua estrutura, ou seja, a união de A com a aresta(u,v) é também um subconjunto de alguma AGM. Chamamos tal aresta de Aresta Segura para A. O Algoritmo geral é definido a seguir. AGM_GERAL(G,w) A ← 0 enquanto A não forma uma AGM faça: encontre uma aresta (u,v) que é segura para A A← A U {(u,v)} retorne A Onde: i. ii. iii. Após a linha 1, o conjunto A satisfaz a propriedade do loop. O loop nas linhas 2, 3 e 4 adiciona assim ao conjunto A apenas Arestas Seguras. A linha 5 assim retorna uma árvore que deve ser uma AGM. Regra Trivialmente a parte de maior complexidade é encontrar as arestas seguras na linha 3, porem quando ela é executada a estrutura conclui que existe uma arvore geradora T, tal que , então deve haver uma aresta tal que sendo assim (u, v) é segura para A. 4 Definiremos a seguir alguns conceitos para mais tarde fornecermos uma regra de reconhecimento de arestas seguras para A. I. II. III. IV. Corte (S, S-V) é uma partição de V em um grafo não direcionado G=(V,E). Uma aresta(u,v) Cruza o Corte quando um de seus pontos extremos está em S e o outro em S-V. Um corte Respeita o conjunto A de arestas se nenhuma aresta em A cruza o Corte. Aresta Leve ou Aresta Mínima é aquela que tem o menor custo entre as arestas que cruzam o corte. Com os conceitos apresentados podermos assim estabelecer nossa Regra para reconhecer Arestas Seguras através do seguinte Teorema: Seja G = (V,E) um grafo conexo não-direcionado com função de custo . Seja A um subconjunto de E que está incluído em alguma Árvore Geradora Mínima de G e seja (S,V - S) qualquer corte de G que respeita A. Seja (u,v) uma aresta leve atravessando o corte (S,V - S). Então, a aresta (u,v) é segura para A. Prova Seja T uma árvore geradora mínima tal que A pertence T, e assuma que T não contém a aresta leve (u,v). A aresta (u,v) forma um ciclo com as arestas pertencentes ao caminho p de u para v em T. Supondo que u e v estão em lados opostos do corte (S,V - S), existe ao menos uma aresta no caminho p que também cruza o corte. Seja (x,y) essa aresta. A aresta (x,y) não pertence a A porque o corte respeita A. Como (x,y) está no caminho de u para v em T, ao removemos (x,y) dividimos T em duas partes. Adicionando (u,v), as partes de T são reconectadas formando uma nova árvore T’ = (T – (x,y)) + {(u,v)}. Como (u,v) é uma aresta leve cruzando o corte (S,V - S) e (x,y) também cruza este corte, w(u,v) ≤ w(x,y). Então: w(T’) = w(T) – w(x,y) + w(u,v) w(T). Porém, T é uma AGM então w(T) ≤ w(T’). Desta forma T’ também deve ser uma AGM. Resta mostrar que (u,v) é realmente uma aresta segura para A. Temos que A subconjunto T’, pois A U T e (x,y) para A. pertence A. Então A U {(u,v)} pertence T’. Conseqüentemente, como T’ é AGM, (u,v) é segura 5 Algoritmo de Kruskal Apresentação do Algoritmo Seu funcionamento é mostrado a seguir: - Crie uma floresta F (um conjunto de árvores). - - Crie um conjunto S contendo todas as arestas(pesos) do grafo. -Enquanto S for não-vazio, faça: - Remova uma aresta com peso mínimo de S - Se essa aresta conecta duas árvores diferentes, adicione-a à floresta, combinando duas árvores numa única árvore parcial - Do contrário, descarte a aresta Ao fim do algoritmo, a floresta tem apenas um componente e forma uma árvore geradora mínima do grafo. Representação do Algoritmo de Kruskal em Execução: Com o uso de uma estrutura de dados aceitável, o algoritmo de Kruskal pode ser demonstrado que executa em tempo: O (Aresta * log Vértices). 6 Algoritmo de Prim Apresentação do Algoritmo Dado um Grafo G, com n vértices e (n-1) aresta com determinados pesos. Seu funcionamento dá-se da seguinte forma: - Cria-se uma arvore A sem elementos. - Um vértice é selecionado. - Enquanto num. de elem. de A for menor que num. de Vértices faça: - Procura-se um vértice mais próximo aos elementos que já estão na Arvore A. - Ao encontrá-lo anexamos este vértice a arvore A. Ao fim teremos uma Arvore com o menor custo total. Representação do Algoritmo de Prim em Execução: A ordem de complexidade para o algoritmo de Prim é: O( |Arestas| * log |Vértices| ) 7 Exercícios Gerais Questão 1: Suponhamos que uma empresa que faça instalação de fibra ótica necessite interligar os bairros abaixo representados: A partir de um estudo meticuloso, os dados relevantes á instalação da fibra ótica, pode ser resumidas ao Grafo mostrado acima. Com posse deste, resolva os exercícios proposto. Gere a Árvore Geradora Mínima para este caso, usando a idéia do Algoritmo de Kruskal e de Prim. Questão 2: Use o Algoritmo de Prim para resolver a Árvore Geradora Mínima para o Grafo indicado.( Fundamentos Matemáticos para a Ciência da Computação, Quinta Edição, Exercício 19 pagina 361) 8 Questão 3: Dado a seguinte matriz de adjacência, gere a arvore geradora mínima usando Prim ou Kruskal. Respostas: 1- 2- 3- Referências: Fundamentos Matemáticos para a Ciência da Computação, Quinta Edição, Judith L. Gerstring. Algoritmos, Teoria e Prática, Thomas H. Cormen. Além dos sites das Universidades UFRJ,USP,IME,UNICAMP... dentre outros. 9
Documentos relacionados
5COP096 Teoria da Computação Teoria da Computação
Sumário - Árvore Geradora Mínima - Teorema pare reconhecer arestas seguras; - Algoritmo de Prim; - Algoritmo de Kruskal; - Caminhos Mais Curtos - Algoritmo de Dijkstra
Leia mais22 Algoritmo de Prim
Algoritmo de Prim para encontrar uma MST de um grafo
ENTRADA: Grafo G=
Algoritmo de Prim
Como tornar a idéia em algoritmo (eficiente)? adicionar o vértice que aumenta o custo o menos possível Idéias: Manter um conjunto de vértices da árvore Manter custo para adicionar cada vértice até ...
Leia mais