Guillermo Enrique Junchaya Heredia
Supervisor: Cláudio Leonardo Lucchesi
Grafos cobertos por emparelhamentos são grafos conexos tais que cada uma das suas arestas pertence a algum emparelhamento perfeito desse grafo. O algoritmo mais eficiente conhecido para decidir se um grafo é coberto por emparelhamentos foi descoberto por Carvalho e Cheriyan. Esse algoritmo é baseado no algoritmo de Edmonds, um algoritmo eficiente para achar um emparelhamento máximo num grafo qualquer. Neste trabalho, apresentamos implementações do algoritmo de Edmonds e do algoritmo de Carvalho e Cheriyan. Essas implementações vêm acompanhadas de uma biblioteca gráfica, o que permite gerar animações desses algoritmos.
Matching covered graphs are connected graphs such that each of its edges belong to a perfect matching of this graph. The most efficient algorithm known for deciding if a graph is matching covered was discovered by Carvalho and Cheriyan. This algorithm is based upon the algorithm of Edmonds, an algorithm for finding a maximum matching in an arbitrary graph. In this study, we present implementations of the algorithms of Edmonds, and of Carvalho and Cheriyan. These implementations were made with a graphic library, which allows the generation of animations for these algorithms.
Na monografia, são explicados os algoritmos implementados. Também, pode encontrar na monografia uma guia de uso do software desenvolvido, assim como sua documentação.
O código fonte pode ser encontrado neste repósitorio do Github. Aí, também pode encontrar uma guia de instalação e uso do software.
Pôster exposto no IME-USP durante a semana de apresentações dos trabalhos.
