Isomorfismo de grafos

En teoría de grafos, un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices $f:V(G)\rightarrow V(H)$ que preserva la relación de adyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H.

La determinación de si dos grafos son isomorfos o no se conoce como el problema del isomorfismo de grafos. Este problema es una curiosidad en teoría de complejidad computacional ya que es uno de los pocos problemas citados por Garey Johnson en 1979 pertenecientes a NP, de los que se desconoce si es resoluble en tiempo polinómico o si es NP-completo.

Los dos grafos que se muestran a continuación son isomorfos:

Grafo G	Grafo H	Un isomorfismo entre G y H
		$f(a)=1$ $f(b)=6$ $f(c)=8$ $f(d)=3$ $f(g)=5$ $f(h)=2$ $f(i)=4$ $f(j)=7$