La propiedad de un grafo que indica que dicho grafo puede obtenerse de otro re etiquetando sus vértices.
Matemáticamente hablando:
G= (V, E) y G'= (V', E') son isomorfos $G\cong G'$ si existe una aplicación biyectiva f entre sus respectivos conjuntos de vértices V y V' que preserva sus adyacencias:
$$\forall v,w \in V, v~w \Leftrightarrow f(v)~f(w)$$
La idea es simple, todos los vecinos que pertenecen a un vértice, también deben pertenecer al vértice del otro grafo.
Por ejemplo si el grafo G(1, 5) posee un vértice v cuyos vecinos son {a, b, c, d, e} y otro grafo M(1, 5) posee un vértice x cuyos vecinos también son {a, b, c, d, e}, entonces el vértice v es el mismo que el vértice x y los grafos G y M son los mismos a excepción por su ubicación en el espacio. Eso es isomorfismo, pero es mas claro verlo con un ejemplo:
En la imagen las posiciones de los vértices cambian al igual que algunas aristas, sin embargo todos los vértices conservan los mismos vecinos, entonces ambos grafos son isomorfos.
Fuentes
http://mate.cucei.udg.mx/matdis/5gra/5gra6.htm
http://web.udl.es/usuaris/p4088280/teaching/terminologia.pdf
http://mathworld.wolfram.com/GraphIsomorphismComplete.html
Entradas
Se otorga un punto extra por esta entrada al blog.
ResponderEliminarG y M son la misma figura, tan solo visto 90 grados a la izquierda o a la derecha, q tiene eso de Isomorfismo. Podría explicarme?
ResponderEliminar