Este trabalho prático da disciplina Teoria dos Grafos abordou os temas de árvores geradoras mínimas e das comunidades. Nele, escolhemos um dataset específico (grafo ponderado) armazenado em arquivo .gml e implementamos o algoritmo de Prim para uma árvore Mínima Spanning Tree (MST) do Grafo.

Para contextualizar, vamos fazer uma breve descrição de Árvores Geradoras e Algoritmo de Prim em grafos.

Uma subárvore de um grafo G é qualquer subgrafo de  G que uma árvore (não radicada). E Comum suprimir o ” sub” e Dizer Que T E UMA Árvore de  G . Uma Árvore de hum grafo G E  Geradora   (=  abrangendo ) se Contém de Todos os vértices de  G [1].

Já Uma Árvore Geradora Mínima de hum grafo ponderado (um grafo é ponderado quando suas arestas possuem um peso), ou MST ( Minimum Spanning Tree ), é qualquer Árvore Geradora que tenha Custo Mínimo. Há vários algoritmos que são usados para encontrar um MST, mas este trabalho usa o Algoritmo de Prim.

Esse algoritmo é iniciado com um raiz qualquer do grafo e cada passo adiciona a arvore a aresta de menor peso. Para isso, ele salva o menor custo de entrada para todo vértice v ∈ V (conjunto de vértices do grafo).

Dadas as seguintes variáveis:

Λ (v): menor custo de entrada para v.
Π (v): predecessor de v.
Q: Fila de prioridades, uma maior prioridade.

G: grafo ponderado.
W: pesos associados às arestas do grafo G.
r: vértice raiz.
V: conjunto de vértices do grafo G.
N (v): conjunto de vértices vizinhos do grafo G.

Pseudocódigo para o algoritmo de Prim (retirado das Notas de Aula do Prof. Dr. Alexandre Levada)

pseudo

O código implementado em Python, usando as bibliotecas Numpy e Networkx:

pyt

Aplicando Prim no nosso dataset, temos a seguinte MST:

figure_1_t3

O código fonte e demais arquivos usados nesse trabalho estão disponíveis em: https://github.com/WellitonAlt/Grafos

Referências:

Árvore geradora de custo mínimo (MST):

https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/mst.html

Notas de aula da disciplina.

Advertisements