34.2-1

Mostre GRAPH-ISOMORPHISM está em NP.

O certificado é um mapeamento f que leva vértices de G1 a vértices de G2.

Para verificar que trata-se realmente de um isomorfismo, deve-se confirmar a veracidade de todas as condições a seguir:

• o número de vértices de G1 é igual ao número de vértices de G2

• o número de arestas de G1 é igual ao número de arestas de G2

• o mapeamento f é injetor, ou seja, se u ≠ v então f(u) ≠ f(v)

• para cada aresta (u, v) de G1 temos que ( f(u), f(v) ) é uma aresta de G2

Como todas estas verificações podem ser feitas em tempo polinomial, GRAPH-ISOMORPHISM pode ser verificada em tempo polinomial e portanto pertence a NP.