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