Teoria dos Grafos Aplicada

• Este repositório contém códigos e recursos relacionados à aplicação de teoria dos grafos.

Conteúdo

Pasta "intro":

Introdução a Grafos: Implementação de algoritmos básicos para representação e manipulação de grafos.

Pasta "Busca":

Algoritmos de Busca: Implementação de algoritmos de busca em grafos, incluindo busca em largura, busca em profundidade.

Pasta "Karger_algoritmo"

Algoritmo de Karger: Implementação do algorítmo de Karger para a determinação de um corte mínimo em um grafo simples não direcionado.
Além disso, existe uma implementação de um 'naive cut', ou seja, cortes ingênuos. No qual divide-se aleatoriamente o grafo em dois grupos de vértices e determina-se o corte dessa divisão. É feita uma análise empírica da probabilidade de encontrar o corte ótimo
entre o Krager e o Naive Cut.

Requisitos

Os códigos foram escritos em Python 3 e foram utilizadas as seguintes bibliotecas:

- NumPy

Como utilizar

Basta clonar o repositório e executar os códigos na pasta correspondente a cada problema. Os resultados depende de qual arquivo for executado.

Contribuição

Contribuições são bem-vindas! Caso queira contribuir, abra uma issue ou submeta um pull request.