Verificação de Isomorfismo de Grafos Via Formas Normais Primárias

Abstract

O problema de isomorfismo entre grafos é um dos problemas cuja complexidade computacional ainda não foi definida [Skiena 2008], portanto, a investigação de sua classe de complexidade e de algoritmos eficientes ainda está em aberto. Desta forma, o objetivo deste trabalho foi produzir um método algorítmico para detecção de isomorfismo entre dois grafos. Através de uma modelagem dos grafos em teorias proposicionais na forma normal conjuntiva, e então, aplicar um algoritmo de transformação dual para encontrar uma teoria equivalente de tamanho reduzido na forma normal disjuntiva, composta apenas por implicantes primários. Com o conjunto de implicantes primários, o próximo passo foi contar a quantidade de modelos desta nova teoria reduzida, cujo objetivo é categorizar as teorias em famílias. Estas teorias foram categorizadas no trabalho de [Polya 1940] e de [Bittencourt, Marchi e Padilha 2003], e concluem que se duas teorias pertencem a mesma famílias, logo elas são congruentes. A motivação deste trabalho vem desta propriedade de congruência entre as teorias. O resultado obtido foi o desenvolvimento de um algoritmo que é capaz de identificar o isomorfismo entre dois grafos. Entretanto, durante as análises alguns casos de não-isomorfismo foram identificados erroneamente como isomorfos. Estes grafos aparentemente possuem uma característica em comum, tornando os resultados, mesmo que incorretos, promissores. Com isto conclui-se que este trabalho cumpriu com os objetivos definidos, entretanto, há a necessidade de investigar se o método de fato só falha para o conjunto de grafos com a característica identificada.

The Graph Isomorphism Problem is one of the problems whose the computational complexity was not defined yet [Skiena 2008], so, an investigation of its complexity, and efficient algorithms, is still open. Thus, the objective of this study was to produce an algorithmic method to detect isomorphism between two graphs. Through modeling the graphs in propositional theories in the normal conjunctive form, and then applying a dual-transform algorithm to find an equivalent theory of reduced size in the normal disjunctive form, composed only of prime implicants. With the set of prime implicants, the next step was to count the number of models of this new reduced theory, whose objective is to categorize theories in families. These theories were categorized in the work of [Polya 1940] and [Bittencourt, Marchi e Padilha 2003], and both conclued that if two theories belong to the same families, they are therefore congruent. The motivation for this study comes from this property of congruence between theories. The result obtained was the development of an algorithm that is able to identify the isomorphism between two graphs. However, during the analysis some cases of non-isomorphism were mistakenly identified as isomorphs. These graphs apparently have a common characteristic, making the results, even if incorrect, promising. Therewith it is concluded that this work fulfilled the defined objectives, however, there is a need to investigate if the method in fact only fails for the set of graphs with the identified characteristic.