Trabalho de Formatura Supervisionado

O problema da conexidade num grafo é amplamente conhecido. Dado um grafo, deseja-se manter a componente conexa de cada vértice. Para grafos estáticos, o problema é simples e estudado em cursos básicos de ciência da computação. Entretanto, se permitirmos atualizações, isto é, a inserção e remoção de arestas, o problema se torna muito mais difícil e requer estruturas de dados avançadas.

O problema pode ser totalmente dinâmico ou parcialmente dinâmico, no primeiro sendo pertimida ambas a adição e a remoção de arestas, enquanto no segundo é pertimida apenas a adição ou a remoção de arestas. O caso particular com apenas adição de arestas pode ser resolvido com uma estrutura de união-busca de modo eficiente e simples, porém de análise não trivial.

O trabalho pretende:

• Estudar e analisar algoritmos que resolvem o problema, tanto parcial quanto total;
• Implementá-los de forma eficiente numa linguagem de programação moderna;
• Testar sua eficiência na prática;
• Estudar suas aplicações.

Para se atingir os objetivos, me reúno com meu supervisor pelo menos uma vez por semana para o estudo da literatura. Os encontros têm se mostrado muito efetivos e estão ajudando muito na compreensão e no avanço do trabalho. Também tenho lido alguns artigos e livros sobre o assunto. As implementações virão conforme os problemas vão sendo estudados e serão publicadas aqui na página.