Pontifícia Universidade Católica do Paraná

Bacharelado em Ciência da Computação

Prof. Fabrício Enembreck

Grupo:

Eduardo Klein Nakatani

Marco Aurélio Silva de Souza Júnior

Rafael Vitagliano Tannenbaum Nuñez

---

Título do Projeto: Definição e Construção de uma Aplicação de Grafos de Alta Dimensionalidade

Características do Projeto:

• Valor: 100% da nota do RA4 para a disciplina de Resolução de Problemas com Grafos;

• Equipe: Máximo em 4;

• Linguagem: JAVA ou Python e

• Data da Entrega: 16/11/2021.

Requisitos de entrega:

• Entregar código-fonte em arquivo;

• Entregar código-fonte impresso; e

• Realizar teste de autoria.

---

Objetivo do Projeto: O presente trabalho tem como objetivo explorar os conhecimentos sobre as várias estruturas de dados estudadas no contexto do programa de aprendizagem “Resolução de Problemas com Grafos”. Tal atividade deverá confrontar o aluno a problemas relacionados à aplicação de grafos e à complexidade algorítmica. Esta última deverá ser evidenciada por meio de um conjunto de algoritmos aplicados a um grande volume de dados.

Requisitos de implementação:

• (0,5 Ponto) Módulo de gravação de Grafo, ponderado e rotulado em Arquivo (Formato Pajek em anexo);
• (0,5 Ponto) Módulo de carregamento de Grafo de Arquivo (Formato Pajek em anexo);
• (0,5 Ponto) Função que verifica se o grafo é conexo ou não;
• (0,5 Ponto) Função que verifica se o grafo é Euleriano ou não;
• (1,0 Ponto) Função que verifica se o grafo é Cíclico ou não;
• (1,0 Ponto) Função que calcula a Centralidade de Proximidade de cada nó (considere a distância do melhor caminho);
• (1,0 Ponto) Função que calcula a Centralidade de Intermediação de cada nó (considere a distância do melhor caminho);
• (1,0 Ponto) Gerador de grafo aleatório que recebe as seguintes entradas:
  • N. de nós;
  • N. de arestas;
  • Se conexo ou não
• (4,0 pontos) Modelar um problema com grafo à sua escolha com as seguintes características:
  • Mínimo de 5.000 (cinco mil nós)
  • Mínimo de 20.000 (vinte mil) arestas

A implementação das questões anteriores deve suportar a aplicação que você escolheu.

O problema deve ser modelado pela equipe e cópias de grafos ou códigos, mesmo que parciais, prontas da Internet ou outras fontes acarretará nota 0 a todas as equipes envolvidas.

---

Formato Pajek:

*Vertices  8
1 "Actor 1"
2 "Actor 2"
3 "Actor 3"
4 "Event 1"
5 "Event 2"
6 "Event 3"
7 "Event 4"
8 "Event 5"
*Edges // para não direcionado ou *Arcs para direcionado
1 4 10
1 5 4
2 4 3
2 5 5
2 6 8
2 8 12
3 4 11
3 7 2
3 8 7