/MinVertexCover

EEL857 - Otimização em Grafos - UFRJ 2016.2

Primary LanguagePythonMIT LicenseMIT

#

EEL857 - Otimização em Grafos - UFRJ 2016.2

Algoritmos para resolução do problema de cobertura minima de vertices

Trabalho desenvolvido por: Marcos Aurélio
Para a disciplina do Profº. Luidi Simonetti

  1. Tecnologias
  • Python
  1. Funções e Algoritmos
  • Algoritmo de força bruta
  • Algoritmo backtracking
  • Algoritmo branch and bound
  • Algoritmo utilizando a heurística de vertice de maior grau
  • Função para gerar um grafo aleatório
  1. Instruções

    • Download

    • Clone

        git clone https://github.com/maasouza/minvertexcover.git

    • Para gerar um grafo

        cd minvertexcover/data
  make
  ./new --v nVertices --d densidade --path ../path/to/new_graph.dat

    • Visualizar o grafo

        O grafo pode ser visualizado localmente.
  Basta abrir o arquivo index.html (Firefox only).
  Exemplo https://maasouza.github.io/MinVertexCover/site/