Isomorfia

Un isomorfismo entre dos grafos R y S es una biyección f entre los conjuntos de sus vértices F :  V(R) --> V(S) que conserva la relación de adyacencia. Quiere decir que cualquier par de vértices u y v de R son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en S. 


Esto quiere decir que dando le nombres iguales a los nodos de los dos grafos, tienen que tener la misma cantidad de nodos vecinos y los mismos nodos.

Como se muestra en la imagen, ambos nodos a y A tiene dos vecinos, los cuales son b, e y B, E y viceversa.

A pesar de su distinta apariencia, los dos grafos son isomorfos.

El análisis de si dos grafos con el mismo número de vértices n y aristas m son isomorfos o no, es conocido como el problema del isomorfismo de grafos. El problema acepta un ataque por fuerza bruta que reclama comprobar si las n! biyecciones posibles conservan la adyacencia, aunque no se conoce un algoritmo eficiente.

A continuación les mostrare un ejemplo

Imágenes tomadas de las diapositivas de la dra. Schaeffer, las características principales de estos grafos es que tiene 15 aristas y 10 nodos por igual.

A continuación la demostración isomorfa en el grafo ROJO a VERDE y viceversa.

Grafo ROJO con nombres en sus nodos (A-J).

Grafo VERDE con nombres en sus nodos (A-J).

Podemos ver que los nombres asignados están alineados de manera isomorfa en ambos grafos.

Vecinos de A = B, E, G

Vecinos de B = A, C H

Vecinos de C = B, D, I

Vecinos de D = C, E, J

Vecinos de E = A, D, F

Vecinos de F = E, H, I

Vecinos de G = A, J, I

Vecinos de H = B, F, J

Vecinos de I = C, F, G

Vecinos de J = D, G, H

Ahora la demostración isomorfa en el grafo AZUL a ROJO y viceversa.

Grafo AZUL con nombres en sus nodos (A-J).

Grafo ROJO con nombres en sus nodos (A-J).

Podemos ver que los nombres asignados están alineados de manera isomorfa en ambos grafos.

Vecinos de A = B, C, H

Vecinos de B = A, E, I

Vecinos de C = A, D, G

Vecinos de D = C, E, J

Vecinos de E = B, D, F

Vecinos de F = G, H, E

Vecinos de G = C, F, I

Vecinos de H = A, F, J

Vecinos de I = B, G, J

Vecinos de J = I, H, D

A continuación la demostración isomorfa en el grafo VERDE a AZUL y viceversa.

Grafo VERDE con nombres en sus nodos (A-J).

Grafo AZUL con nombres en sus nodos (A-J).

Podemos ver que los nombres asignados están alineados de manera isomorfa en ambos grafos.

Vecinos de A = B, C, D

Vecinos de B = G, I, A

Vecinos de C = A, J, H

Vecinos de D = A, E, F

Vecinos de E = I, D, H

Vecinos de F = G, D, J

Vecinos de G = B, F, H

Vecinos de H = G, C, E

Vecinos de I = B, E, J

Vecinos de J = I, C, F

Bueno eso seria todo.

Referencias:

Grafos isomorfos
Diapositivas de la dra. Schaeffer