Projeto da disciplina de Teoria dos Grafos, 2023

Elieder Damasceno Sousa
José Eduardo Bernardino Jorge

Problemas de menor caminho são recorrentes em Teoria dos Grafos. Nossa proposta é a de simular a malha rodoviária de São Paulo utilizando um grafo não direcionado, onde os vértices são as cidades e as arestas os caminhos (em linha reta) entre as mesmas. Assim, podemos verificar a distância entre cidades além de um possível percurso entre elas. Segundo dados do IBGE e do Governo Federal, há um total de 645 cidades no estado de São Paulo além de um número não contabilizado de interligações entre as cidades. Isto mostra a grandeza da cidade, além do desafio a ser enfrentado à frente. Portanto, temos como objetivo:

• Criar um banco de dados com as cidades paulistas e suas informações básicas (nome, posição geográfica, população);
• Usar o banco de dados para criar os vértices e arestas de um grafo não direcionado;
• Gerar automaticamente uma imagem do grafo após tratamento completo;
• Gerar um arquivo grafo.txt contendo informações necessárias para a manipulação, de acordo com as regras do projeto;
• Ter um projeto passível de pequenas mudanças sem alterar drasticamente a estrutura do banco de dados. Isto torna o projeto escalável, possibilitando a expansão da malha para outros estados de forma fácil, ou então, para o Brasil inteiro.

Grafo final visualizado no GraphOnline

Distância calculada entre São Paulo e Rosana: 740km. Distância real: 746 km. Fonte: https://www.rotamapas.com.br/distancia-entre-sao-paulo-e-rosana

Menu do sistema