Problema do isomorfismo de subgrafos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo.

Definição[editar | editar código-fonte]

Isomofismo de Subgrafos (G_1, G_2)
Entrada: Dois grafos \,G_1 e \,G_2.
Pergunta: \,G_1 é isomórfico (há um isomorfismo de grafos) a um subgrafo de \,G_2?

Ou, informalmente: tome dois grafos não dirigidos \,G_1 e \,G_2 e verifique se \,G_1 é subgrafo de \,G_2 (a menos de um isomorfismo) ou não. Em outras palavras, o problema verifica se há ou não uma função \,f que mapeie os vértices de \,G_1 nos vértices de \,G_2 de forma tal que haja uma aresta \,\{u, v\} em \,G_1 exatamente quando \,\{f(u), f(v)\} está em \,G_2.

Algumas vezes o nome casamento de subgrafos é usado para o mesmo problema. Este nome dá ênfase à busca de um tal subgrafo, em contraste ao mero problema de decisão.

Classe de Complexidade[editar | editar código-fonte]

A demonstração de que o problema do isomorfismo de subgrafos é NP-completo é simples e baseada na redução ao problema do clique (que se sabe ser NP-completo), mostrando que CLIQUE \leq p isomorfismo de subgrafos. Se o isomorfismo de subgrafos fosse polinomial, poder-se-ia usá-lo para resolver o problema do clique em tempo polinomial. Tome n como o número de arestas em \,G: poder-se-ia então rodar o isomorfismo de subgrafos n-2 vezes (com \,G_1 sendo um clique de tamanho 3 até n, e \,G_2 sendo \,G) para encontrar o maior clique em \,G.

O isomorfismo de subgrafos é uma generalização do problema potencialmente mais fácil do isomorfismo de grafos; se o problema do isomorfismo de grafos fosse NP-completo, a hierarquia polinomial colapsaria, então suspeita-se que ele não o seja.

Áreas de aplicação[editar | editar código-fonte]

Na área de quimioinformática freqüentemente o termo pesquisa de subestruturas é usado. Tipicamente uma estrutura de consulta é definida como SMARTS, uma extensão de SMILES.

É também de grande importância para gramáticas de grafos.

Referências[editar | editar código-fonte]

  • J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
  • Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. [S.l.]: W.H. Freeman, 1979. ISBN 0-7167-1045-5. A1.4: GT48, pg.202.