Se puede decir que dos grafos son isomorfos si existe una correspondencia uno a uno entre los vértices de los grafos tal que para todo par de vértices que son adyacentes en un grafo si y sólo si el correspondiente par de vértices son adyacentes en el otro grafo.
Dados G=(V,E) y G´=(V´,E´), se denomina isomorfismo de G a G´ a la aplicación biyectiva f tal que para a,bÎV, {a,b}ÎE Û se cumple {f(a),f(b)}ÎE´. Es decir, la aplicación que relaciona biyectivamente pares de vértices de E con pares de vértices de E´, de modo que los vértices conectados por aristas siguen estándolo.
G y G´ se denominan isomorfos, y son matemáticamente iguales, solo varia la apariencia, o sea, que se mantienen las adyacencias, estructura, caminos y ciclos.
Los grafos G y G ‘ son isomorfos pues existe la biyección f: V ® V ‘ definida por f(a) = 2, f(b) = 1, f(c) = 3, f(d) = 4 que conserva la adyacencia..
Se mostrara un ejemplo en el siguiente video:
No hay comentarios:
Publicar un comentario