ISOMORFISMO DE GRAFOS

 ISOMORFISMO DE GRAFOS

Definición:

Dos grafos G1 y G2 son isomorfos si existe una función biyectiva f entre los vértices de G1 y G2, y una función biyectiva g entre lados de G1 y G2 tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en G2. Al par de funciones f y g se le denomina isomorfismo.

Ejemplo:

Sean los siguientes grafos G1 y G2

Un isomorfismo para los grafos anteriores G1 y G2 esta definido por:

f (a) = A

f (b) = B

f (c) = C

f (d) = D

f (e) = E

y g(Xi) = Yi, i = 1, ... , 5