Gráficas isomorfas

Gráficas Isomorfas Concepto: Las Graficas G1 y G2 son isomorfas si existe una función uno a uno y sobre f de los vértices de G1 a G2 y una función uno a uno y sobre g de las aristas de G1 a las aristas de G2 de modo que una arista e es incidente en v y w en G1 si y solo si la arista g(e) es incidente en f(v) y f(w).Las funciones f y g son un isomorfismo de G1 sobre G2.

Gráficas Isomorfas.

Teorema

Sean G1 y G2 gráficas simples. Las siguientes afirmaciones son equivalentes:

a) G1 y G2 son isomorfas b) Existe una función uno a uno y sobre f , del conjunto de vértices de G1 al conjunto de vértices de G2 que satisface la siguiente condición: Los vértices de v y w son adyacentes en G1 si y solo si los vértices f(v) y f(w) son adyacentes en G2.

Demostración

Definamos una función g, de las aristas de G1 a las aristas de G2 mediante la regla
g((v,w)) = (f(v),f(w))

Como G1 y G2 son gráficas simples, ninguna de ellas tiene aristas paralelas, de modo que la notación (v’,w’) designa sin ambigüedades una arista. Observe que el rango de g es un subconjunto de las aristas de G2, pues si (v,w) es una arista en G1, v y w son adyacentes, lo cual implica que f(v) y f(w) son adyacentes; es decir que (f(v),f(w)) es una arista en G2

Fuentes

• Johnsonbaugh, Richard. Matemáticas Discretas. Volumen II,cuarta edición.Editorial Felix Varela, La Habana, 2006. Pág 350.
• Información ofrecida por MSc. José Ramón Ávila Cruz (JC Puerto Padre V)