GRAFOS ISOMORFOS

Se dirá que dos grafos G y G' son isomorfos entre sí, si: 

1. Existe una función biyectiva .
2. Si dos vértices vi, vj son adyacentes en V(G), es decir, viRvj, entonces las correspondientes imágenes de dichos vértices también son adyacentes pero en V(G'), dicho de otra forma,; y viceversa.

Ejemplo: En la siguiente figura, tenemos que G es isomorfo a G'.

Donde V(G) = {1,2,3,4} y V(G') = {A,B,C,D} y como debe cumplirse quef:V(G)  V(G') es una biyección, entonces f(1) = D, f(2) = B, f(3) = C, f(4) = A. Observar que 1R4 en G, entonces, D R A en G'.

Tenemos otra función que también define un isomorfismo entre G y G'.

f(1) = B, f(2) = D, f(3) = C y f(4) = A.

Observar, igualmente, que para este caso 1 R 4 en G, entonces, B R A en G'.

La relación de isomorfismo preserva las vecindades de cada vértice.

La relación de isomorfismo de dos grafos G y G' se denota de la siguiente manera, 

Corolario: Si , entonces:

/V(G) /= /V(G')/

/E(G) /= /E(G') /

Si tiene vi tiene "k" vértices vecinos vi1, vi2, vi3, ... , vik, entonces, f(vi) tiene los siguientes "k" vértices vecinos f(vi1), f(vi2), f(vi3), ... , f(vik).

vi y f(vi) tienen la misma valencia.

Cibergrafía:

http://teoriadegrafos.blogspot.com.co/2007/03/isomorfismo-de-grafos.html