Bioeconomia: Diversidade e Riqueza para o Desenvolvimento Sustentável
21 a 25 de outubro de 2019
Trabalho 12911
| Instituição | Universidade Federal de Viçosa |
|---|---|
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Engenharia/Tecnologia |
| Setor | Instituto de Ciências Exatas e Tecnológicas |
| Conclusão de bolsa | Não |
| Primeiro autor | Lucas Carvalho de Oliveira |
| Orientador | MARCUS HENRIQUE SOARES MENDES |
| Título | Aplicação Didática para Visualização de Grafos |
| Resumo | A Teoria dos Grafos é um ramo das Ciências Exatas que estuda as relações dos objetos de um determinado conjunto. Para isto, utiliza uma estrutura denominada Grafo, que possui um conjunto não vazio de vértices, nos quais são representados por uma unidade gráfica, em geral, um círculo, e arestas, que são um subconjunto de pares não ordenados de vértices quando existem, e são representados graficamente por uma curva que liga os vértices relacionados. Dado um determinado uso da estrutura, para a resolução de um problema por exemplo, o grafo pode ser adaptado para que: (1) as arestas possuam direção única, (2) habilite que um vértice tenha uma aresta que parta dele e conecta em si mesmo, (3) habilite que duas arestas distintas tenham vértices de origem e destino iguais, (4) associar um peso à aresta em forma de valor numérico, (5) nomear os vértices, entre outras adaptações que podem mudar a forma como visualiza-se a relação entre os objetos de um conjunto. Muitos problemas práticos, em diversas áreas do conhecimento, podem ser modelados por meio de grafos. Dentre os problemas mais usuais que envolvem a Teoria de Grafos estão: (1) o problema do caminho mínimo, onde procura-se o menor caminho de um vértice a outro, (2) o problema do fluxo máximo em redes, onde procura-se o caminho que faça o melhor uso das capacidades de uma rede, (3) os problemas de roteamento, aonde o objetivo é encontrar a melhor rota para um determinado problema – tais quais: problema do caixeiro viajante, problema do ladrão viajante, problema das pontes de Königsberg, problema do Carteiro Chinês, entre outros problemas de complexidade algorítmica NP-difícil ou NP-completo. A aplicação de algoritmos sobre grafos é um tema de relevância ímpar para a Ciência da computação e possui até hoje problemas em aberto que não se sabe serem solucionáveis em tempo polinomial e muito menos a classe de complexidade que algoritmos para resolver estes problemas poderiam se encaixar. Um exemplo clássico é o Problema do Isomorfismo em grafos. A visualização gráfica dos Grafos pode revelar informações importantes sobre a estrutura e fornece uma ferramenta lúdica para a interpretação dessas informações. Neste trabalho, desenvolveu-se uma ferramenta de acesso universal para a visualização de grafos, aonde um estudante pode construir o grafo e ainda o modificá-lo como achar necessário para que ele possa entender quais as características daquele grafo. Além disso, o usuário pode salvar e abrir um grafo salvo, configurá-lo como orientado ou ponderado, e verificar algumas propriedades, como por exemplo, se o grafo é simples, o número de vértices, o número de arestas, a multiplicidade entre as arestas, se é ponderado ou orientado, mostra o maior e menor grau, matrizes de adjacência e incidência e o Número de Wiener. Em trabalhos futuros, a estrutura de visualização gráfica deste trabalho, será utilizada para executar algoritmos passo-a-passo sobre os grafos criados pelo usuário. |
| Palavras-chave | visualização, grafos, didática |
| Apresentações |
|