Isomorfismo
Páginas: 2 (345 palabras)
Publicado: 29 de septiembre de 2010
ISOMORFISMO
Los grafos simples G1 = (V1, E1) y G2 = (V2, E2) son isomorfos si hay una función biyectiva f desde V1 a V2 con la propiedad que a y b son adyacentes en G1 si y solo si f(a) y f (b) son adyacentes en G2, para todo a y b en V1. Tal función f es llamada un isomorfismo (igual forma).
Ejercicio: Determinar si los grafos indicados son isomorfos.
Figura:ejemplo isomorfismo de grafos
Respuesta Ejercicio: Si.
Un posible isomorfismo es:
f (u1) = v1
f (u2) = v4
f (u3) = v3
f (u4) = v2
Nota: Existen otros isomorfismos.
Nota: Losmejores algoritmos conocidos para determinar si 2 grafos son isomorfos o no, tienen complejidad exponencial (en el numero de vértices de los grafos) en el peor caso.
Para mostrar que 2grafos no son isomorfos podemos mostrar que sus invariantes (propiedad que los grafos simples deben cumplir) no son iguales.
1. El numero de vértices.
2. El numero de aristas.
3. Elgrado de los vértices.
Si en alguna de esas cantidades difieren 2 grafos simples, no son isomorfos.
Nota: Si sus invariantes son los mismos, no necesariamente son isomorfos.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 queun 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 lossiguientes grafos G1 y G2
Un isomorfismo para los grafos anteriores G1 y G2 está definido por:
f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E
y g (Xi) = Yi, i = 1,..., 5
Losgrafos G1 y G2 son isomorfos si y solo si para alguna ordenación de vértices y lados sus matrices de incidencia son iguales. Veamos las matrices de incidencia de los grafos anteriores:
Los grafos simples G1 = (V1, E1) y G2 = (V2, E2) son isomorfos si hay una función biyectiva f desde V1 a V2 con la propiedad que a y b son adyacentes en G1 si y solo si f(a) y f (b) son adyacentes en G2, para todo a y b en V1. Tal función f es llamada un isomorfismo (igual forma).
Ejercicio: Determinar si los grafos indicados son isomorfos.
Figura:ejemplo isomorfismo de grafos
Respuesta Ejercicio: Si.
Un posible isomorfismo es:
f (u1) = v1
f (u2) = v4
f (u3) = v3
f (u4) = v2
Nota: Existen otros isomorfismos.
Nota: Losmejores algoritmos conocidos para determinar si 2 grafos son isomorfos o no, tienen complejidad exponencial (en el numero de vértices de los grafos) en el peor caso.
Para mostrar que 2grafos no son isomorfos podemos mostrar que sus invariantes (propiedad que los grafos simples deben cumplir) no son iguales.
1. El numero de vértices.
2. El numero de aristas.
3. Elgrado de los vértices.
Si en alguna de esas cantidades difieren 2 grafos simples, no son isomorfos.
Nota: Si sus invariantes son los mismos, no necesariamente son isomorfos.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 queun 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 lossiguientes grafos G1 y G2
Un isomorfismo para los grafos anteriores G1 y G2 está definido por:
f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E
y g (Xi) = Yi, i = 1,..., 5
Losgrafos G1 y G2 son isomorfos si y solo si para alguna ordenación de vértices y lados sus matrices de incidencia son iguales. Veamos las matrices de incidencia de los grafos anteriores:
Leer documento completo
Regístrate para leer el documento completo.