Apresentação: Problema do isomorfismo em grafos
Transcrição
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
Documentos relacionados
faculdade norte capixaba de sâo mateus análise e desenvolvimento
Padrões algorítmicos que foram criados para fins parecidos também foram abordados, assim como a teoria dos grafos (onde foram apresentados apenas os conceitos básicos, acreditando-se dar um bom sup...
Leia mais