| |
| Acadêmico(a): Anderson de Borba |
| Título: FURB Graphs: uma aplicação para teoria dos grafos |
| |
| Conclusão: |
Este trabalho apresentou a continuação do desenvolvimento de um framework para a área de teoria dos grafos (ZATELLI, 2010), onde os objetivos principais foram o desenvolvimento de novas propriedades, algoritmos e uma interface visual e interativa para manipulação, criação e testes das propriedades e algoritmos. O desenvolvimento foi feito utilizando a linguagem Java, fazendo uso das bibliotecas Gson e Swing, responsáveis, respectivamente, por salvar/carregar um grafo e auxiliar na construção da interface gráfica.
Os resultados obtidos mostraram-se satisfatórios, mantendo um nível acima dos trabalhos correlatos devido à complexidade dos algoritmos implementados e pela construção da interface gráfica, que fornece os recursos para trabalhar com grafos simples e fornece um feedback para execução dos algoritmos e testes de propriedades muito bom. Com este trabalho, um aluno de computação que está estudando a matéria de grafos, conseguirá assimilar mais rapidamente o funcionamento das propriedades número cromático, hipercubo e isomorfismo, além de compreender e entender o que caracteriza um ciclo hamiltoniano e um caminho euleriano, pois, é possível reforçar os conceitos "brincando" com a manipulação do grafo com o uso interface gráfica enquanto testa as propriedades e algoritmos para os mais diversos tipos de grafos.
A maior dificuldade encontrada neste trabalho foi o desenvolvimento dos testes de propriedade e da implementação dos algoritmos, em especial, isomorfismo entre grafos. Implementações em grafos são complexas pois é necessário tomar cuidado com pensamento trivial afim de evitar problemas que não executem em tempo polinomial. É necessário muita pesquisa sobre cada algoritmo afim de saber como resolver o mesmo de maneira eficiente, caso possível. Também é necessário tomar cuidado com propriedades que são, de certa forma, fácil de compreender, porém difíceis de implementar. Por exemplo, entender o significado de um número cromático de um grafo é uma questão fácil de compreender, porém implementar a solução ótima é complicado. Outro caso percebido por este trabalho foi a implementação para o teste de isomorfismo. Apesar de ser um problema fácil de compreender e de imaginar uma solução (a solução é enumerar todas as possibilidades possíveis de combinações entre dois grafos), esta foi uma propriedade muito difícil de implementar. Apesar de ter gerado pouco código, o código produzido é enxuto e complexo e opera com vários níveis de recursão e manipulações de listas afim de manter a navegação sincronizada entre os dois grafos. Estes foram os motivos por ter sido deixado de fora deste trabalho as propriedades cordais e planar, além dos algoritmos clique máximo e emparelhamento perfeito máximo. Em especial, clique
76
máximo e grafos cordais foram deixado de fora pois o intuito deste trabalho era explorar a condição de utilizar de que grafos cordais podem resolver o problema do clique máximo (que é um problema NP-difícil) em tempo polinomial.
A principal vantagem do trabalho desenvolvido é a interface visual e interativa proposta que ajuda a assimilar e compreender algoritmos mais facilmente. Outro fator importante é a implementação das propriedades isomorfismo e hipercubo, pois carecem de exemplos de implementação na literatura. Entretanto, existem limitações do trabalho na interface visual sendo a mais perceptível que atualmente ela opera somente para grafos simples, portanto não é possível definir arestas paralelas e laços. |
| |
|
