miércoles, 12 de mayo de 2010

Proyecto #5 - Isomorfismo

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:





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


Esto es ya que en G1 “a” esta conectada a “e” y “b”, en G2 “A” esta conectada a “E” y “B”, en G1, “e” se conecta a “a” y “d” y en G2, “E” se conecta a “A” y “D”, en G1 “d” se conecta a “e” y “c”, en G2 “D” se conecta a “E” y “C”, en G1 “c” se conecta a “d” y “b”, en G2, “C” se conecta a “D” y “B” y en G1 “b” se conecta a “c” y “a”, y en G2 “C” también se conecta a “C” y “A”.


El problema del isomorfismo de grafos presenta una curiosidad en teoría de complejidad computacional al ser uno de los pocos problemas pertenecientes a NP de los que se desconoce si es resoluble en tiempo polinómico o si es NP-completo.

En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP-completo, que formalmente, se define de la siguiente manera:

Isomorfismo-de-subgrafos(G1, G2)
Entrada: Dos grafos G1 y G2.
Pregunta: Es G1 isomorfo a un subgrafo de G2?

La NP-completitud del problema se demuestra mediante la reducción de este problema al Problema de la clique. Si el Problema de isomorfismo de subgrafos fuese polinomial, podría utilizarse para resolver el Problema de la clique, también en tiempo polinomial. Sea n el número de aristas de G, se puede ejecutar el problema de isomorfismo de subgrafos n-2 veces (siendo G1 una clique de tamaño 3 a n, y G2 siendo G) para encontrar el clique más grande en G.

Este problema es una generalización del posiblemente más sencillo Problema de isomorfismo de grafos, en el sentido que si este último es NP-completo, entonces la jerarquía polinomial colapsa, así que se supone que no debería ser así.

Otro ejemplo de Isomorfismo seria el siguiente:



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


2 comentarios:

  1. Me hubiera gustado ver una explicación de un algoritmo para resolver el problema de isomorfismo, aún cuando es claro que no va a ser muy eficiente. Creo que lo más simple de explicar sería un método tipo ramificar-acotar como lo que se usa típicamente para resolver los sudoku.

    ResponderEliminar
    Respuestas
    1. esto es viejo, pero conoces algun pseudocodigo al menos de algun lugar para isomorfismo?

      Eliminar