Apresentação: Problema do isomorfismo em grafos

Apresentação:
Problema do isomorfismo em grafos
Renan Manola
1. Introdução
O problema do isomorfismo em grafos pode ser facilmente definido como s16endo o desafio
de que, dados dois grafos, seja possível estabelecer um mapeamento entre seus vértices de forma
que se prove que, por meio desse mapeamento, um grafo é igual ao outro.
Em todos os algoritmos pesquisados se parte do pressuposto que antes de aplicá-los, testes
rápidos que podem provar que dois grafos não são isomorfos já tenham sido feitos. Para que dois
grafos sejam isomorfos, as seguintes condições devem ser satisfeitas:
• Devem ter mesmo número de arestas
• Devem ter mesmo número de vértices
• Devem ter a mesma frequência de graus dos vértices, quando ambos ordenados
Em termos de complexidade computacional, o problema do isomorfismo pertence a classe
dos problemas P e possui complexidade polinomial [1].
2. Aplicações
Muitas áreas da ciência podem se beneficiar do estudo de isomorfismo em grafos. Na
química orgânica os nomes dos compostos são dados baseando-se na topologia das estruturas
obtidas, dessa forma, pode ocorrer de um mesmo elemento químico receba dois nomes diferentes de
forma acidental, o estudo de isomorfismo pode evitar isso. Em reconhecimento de padrões,
isomorfismo de subgrafos pode ser aplicado a reconhecimento de caracteres chineses e
reconhecimento de lacres. Aplicado a visão computacional, o isomorfismo pode ser usado para
identificar objetos inseridos em cenas 3D. O artigo [2] possui várias referências sobre essas várias
aplicações.
3. Algoritmos de Solução
Tal problema já foi extensivamente pesquisado, no entanto, até os dias de hoje algumas
questões ainda permaneciam em aberto. Todos os artigos pesquisados até a presente data (2009)
afirmavam que o problema do isomorfismo em grafos estava dentro dos problemas NP e sua
complexidade era desconhecida até então. O artigo [1] prova que trata-se de um problema P e que
possui complexidade polinomial. Também é apresentado o algoritmo prova-de-conceito usado.
Como esta referência mostrou-se ser um marco na pesquisa relativa ao problema do isomorfismo,
tal algoritmo foi escolhido para ser usado em detalhes na resolução de dois grafos possivelmente
isomorfos que serão apresentados em sala.
Para resolver o problema do isomorfismo podem ser usadas duas abordagens principais: (a)
tentando resolver efetuando operações na topologia dos grafos na tentativa de igualar os mesmos e
(b) fazendo uso de um tipo de hash, que aplicado a um grafo como todo retorne um valor único que
o descreva, dessa forma, aplicando esse “hash” nos dois grafos e posteriormente os comparando
para verificar se são ou não isomorfos.
Infelizmente, tal “hash” não é algo tão simples de ser elaborado, algoritmos que fazem uso
dessa abordagem são chamados de “Vertex Invariants”. Algoritmos desse tipo constituem uma área
de pesquisa um tanto quanto obscura ainda. Segue abaixo uma listagem desses algoritmos para
solução de isomorfismos:
• twopaths
• adjacency triangles
• k-cliques
• independent k-sets
• distances
Uma implementação que faz uso desses invariantes é o Nauty, de Brendan D. McKay [3]. O
algoritmo faz uso de vários conceitos de teoria dos grupos e possui várias etapas que são tentadas
até conseguir produzir um resultado final.
Hopcroft e Wong [4] mostraram que grafos isomorfos planares podem ser resolvidos em
tempo linear. Jaja e Kosaraju [5] estenderam tal resultado elaborando um algoritmo paralelo e,
consequentemente, mais rápido para o problema. Dadas as limitações para aplicação em tempo-real
de tal algoritmo, outros três pesquisadores [6] estenderam este ultimo implementando o mesmo em
hardware VLSI. Tais exemplos provam que mesmo que tais pesquisas não geraram contribuições
para área matemática do estudo dos grafos isomorfos, resultaram em algoritmos para resolver
problemas tipicamente práticos.
4. Referências Bibliográficas
• [1] Ashay Dharwadker und John-Tagore Tevet – The Graph Isomorphism Algorithm.
Proceedings of the Structure semiotics Research Group S.E.R.R. 2009.
• [2] Bruno T. Messmer and Horst Bunke - Efficient Subgraph Isomorphism Detection: A
Decomposition Approach. IEEE Transactions on Knowledge and data engineering. Vol. 2
NO. 2 March/April 2000.
• [3] B. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45-87, 1981.
• [4] A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms.
Addison-Wesley, Reading, 1974.
• [5] J. JaJa and S. Kosaraju. Parallel algorithms for planar graph isomorphism and realted
problems. IEEE Transactions on Circuits and Systems, 35:304{311, 1988.
• [6] D. Damarchi, G. Masera, and G. Piccinini. A VLSI processor array for graph
isomorphism. International Journal of Electronics, 76(4):655{679, 1994