Trabalho de Formatura Supervisionado

Emparelhamentos em grafos é um tema muito abordado em ciência da computação, sobretudo pela sua riqueza em modelar uma grande variedade de problemas de natureza prática. Quando consideramos que cada vértice ordena os seus vizinhos segundo uma ordem de preferência, dá-se origem ao conceito de um grafo de preferências. Nesse pano de fundo, em vários problemas, emparelhamentos com a propriedade que existam dois vértices que prefiram a si próprios do que os seus parceiros são indesejáveis, já que eles seriam instáveis em um certo sentido. Assim, surge o conceito de emparelhamento estável, que é um emparelhamento que não apresenta essa propriedade. O presente trabalho consiste de um estudo de natureza algorítmica e matemática da classe dos emparelhamentos estáveis. No primeiro capítulo, nos restringimos a grafo de preferências bipartidos. Nele, descrevemos o algoritmo de Gale-Shapley que em tempo linear encontra um emparelhamento estável e, além disso, abordamos outros conceitos que julgamos essenciais. No capítulo seguinte, abordamos o algoritmo de Irving que decide, em tempo linear, a existência de um emparelhamento estável e devolve um em caso positivo.

Palavras-chave: emparelhamentos estáveis, grafos de preferências, Gale-Shapley, Irving.

No começo do ano, não tinha muita ideia de qual exatamente seria o tema que eu desenvolveria no TCC. Ao pesquisar sobre o tema, me deparei com o Problema do casamento estável. Fiquei fascinado pela simplicidade e elegância do algoritmo que resolve o problema e decidi, ainda com um pouco de receio, que trabalharia nesse tema. Ao final do trabalho, tenho a sensação que fiz a melhor escolha possível.

Embora eu já tivesse uma boa experiência em escrever textos matemáticos, o processo de escrita da monografia foi um trabalho por muitas vezes árduo. Escrever bons textos nunca foi uma tarefa fácil para mim. Em vários momentos, cheguei a passar a horas para produzir um único parágrafo. Felizmente, durante o desenvolvimento do trabalho, deparei-me com inúmeros ótimos textos bem escritos que contribuíram para que eu me desenvolvesse nesse sentido.

Como minha primeira experiência em um projeto de pesquisa, afirmo que foi muito positiva. Não consegui falar sobre tudo que gostaria, mas considero o resultado do trabalho muito satisfatório. Sempre possuí muito apreço pela pesquisa acadêmica e espero que no futuro eu consiga realizar mais contribuições.