Sistema de Submissão de Resumos, I Encontro de Iniciação Científica - 2011 (ENCERRADO)

Tamanho da fonte: 
studos em Teoria dos Grafos e uma Implementação do ``Rubber Band Method''
Daniel M. Martin, Álvaro Araujo Zucchi

Última alteração: 2011-09-09

Resumo


Introdução - A teoria dos grafos é uma area da matemática que faz fronteira com a ciência da computação. Alguns de seus problemas intrigaram matemáticos e todo mundo por muitos anos e alguns desses problemas ainda permanecem em aberto.
Grafos são comumente usados como um modelo de problemas complexos. A possibilidade de se obter informações rapidamente a partir da imersão de um grafo no plano é uma das vantagens de se modelar um problema por meio deles. Apesar disso, alguns grafos podem ser complicados de se compreender e achar uma imersão visualmente compreensível pode ser uma tarefa desafiadora. Alguns métodos foram desenvolvidos para remodelar o aspecto visual de um grafo sem mudar sua topologia, de modo que a nova aparência o torne mais legível. Um desses métodos é um algoritmo que simula as propriedades físicas dos elásticos nas arestas de um grafo, de modo que seus vértices sofram forças que os desloquem
no plano cartesiano. Esse método é conhecido como Método Elastico. Esse método pode servir para encontrar uma imersão planar do grafo em alguns casos.
Metodologia - Estudamos os principais conceitos básicos de teoria dos grafos e alguns resultados conhecidos, através de leitura da bibliografia e reuniões com o orientador. Desenvolvemos uma implementação do método elastico. Por fim pesquisamos na literatura grafos famosos e simétricos para a elaboração da biblioteca de testes.
Objetivos -Estudo e aprendizado dos conceitos fundamentais e de resultados clássicos da teoria dos grafos. Aprendizado e implementação do método elástico.
Resultados - Os conceitos da teoria dos grafos estudados foram bem apreendidos e vários resultados foram demonstrados no relatório final. A implementação do algoritmo proposto mostrou-se eficaz na maior parte dos casos de teste.
Conclusão - Observamos que o algoritmo de desenho de grafos baseado em forças foi capaz de tornar o aspecto visual da maioria dos grafos mais ``legível'', como havia sido proposto. Após ajuste do algoritmo, onde se incluiu também uma força de repulsão elétrica entre os vértices, resultados aceitáveis foram obtidos mesmo para os casos onde o primeiro algoritmo gerou resultados confusos.