Grafos de Emparelhamento de Arestas

Abstract

Neste trabalho propomos uma nova técnica para verificar se um grafo corresponde a algum emparelhamento de arestas. Para isso propomos o uso do que intitulamos grafo paralelo; um grafo onde cada aresta é dividida em duas semi-arestas orientadas. Este grafo associa uma palavra a um dado emparelhamento, de forma que operações sobre as palavras podem ser usadas para determinar a equivalência entre dois emparelhamentos. A relação entre a palavra e os vértices do emparelhamento é fornecido por um algoritmo proposto chamado chuva de vértices. Por fim, determinamos a relação entre a extensão de vértices e a palavra associada.