Olá pessoal!
Nosso próximo tutoria vai falar sobre as Árvores Spanning Mínima e usaremos um algoritmo (Kruskal ou Prim) para exemplificar a construção dessa árvore.
- O que é uma Árvore Spanning Mínima (MST) ?
É importante definir Árvore antes de mais nada:
"Seja G = (V,E) um grafo:
- G é acíclico se não contém ciclos;
- G é uma árvore se for um grafo acíclico conexo."
(1) NICOLLETI, Maria. p.89
A partir da definição conclui-se também que não há loops em G, caso seja árvore, logo trata-se de um gravo acíclico simples.
Caso essa árvore possua todos os vértices do grafo é chamado de Árvore Spanning, ou Árvore Geradora. Ou seja:
"Seja G = (V, E) um grafo. Uma árvore spanning do grafo F é um subgrafo spanning de G que é uma árvore."
(1) NICOLLETI, Maria. p.99
A partir de agora usaremos o conceito de peso da aresta para entender o que é uma MST. O peso aparece em grafos ponderados que em cada aresta possui um número real associado a ela, que identificaremos por w(e), peso da aresta e.
Encontrar uma Árvore Spanning Mínima consiste em identificar a cada passo a aresta de menor peso segura, que não forma ciclos, e assim gerar uma árvore que passe por todos os vértices com menor custo.
Existem dois algoritmos para achar a MST, são eles: Algoritmo de Kruskal e Algoritmo de Prim.
(3) Imagem disponível em <http://stackoverflow.com/questions/1195872/kruskal-vs-prim>. Último acesso: 18/10/2014
Existem dois algoritmos para achar a MST, são eles: Algoritmo de Kruskal e Algoritmo de Prim.
- Algoritmo de Kruskal x Algoritmo de Prim
O algoritmo de Kruskal tem como objetivo escolher a cada passo a aresta de menor peso e que não forme um ciclo. Já o algoritmo de Prim inicia um uma raiz qualquer e a cada passo adicionar a árvore a aresta de menor custo que sai do conjunto dos vértices já visitados e chega no conjunto do vértices não visitados, o objetivo é salvar o menor custo de entrada para qualquer vértice v. (2)
Observe abaixo uma imagem explicando o funcionamento:
(3)
- Enfim...
Então, esse será o tema do nosso próximo tutorial. Ainda não decidimos qual algoritmo utilizar. Caso você queira algum específico comenta aí que daremos preferência. Abaixo o grafo que será utilizando para exemplificação.
- Referências
(1) NICOLETTI, Maria do Carmo. HRUSCHKA, Estevam Rafael. Fundamentos da teoria dos grafos para computação. EdUFSCar, 2011.
(2) Anotações das aulas de Teoria dos Grafos, turma B, ministrada pelo Prof. Dr. Alexandre Levada.
(2) Anotações das aulas de Teoria dos Grafos, turma B, ministrada pelo Prof. Dr. Alexandre Levada.
(3) Imagem disponível em <http://stackoverflow.com/questions/1195872/kruskal-vs-prim>. Último acesso: 18/10/2014



Nenhum comentário:
Postar um comentário