Demostracion de isomorfismos de grafos de Petersen

1. Isomorfismos en Grafos de Petersen Rosa E. Padilla Torres Presentación para la clase de Teoría de Grafos MATH 6200 Dr. Ál varo Lecompte 21 de junio de 2011

2. Isomorfismos entre Grafos Los grafos simples G 1 = ( V 1 ,E 1) y G 2 = ( V 2 ,E 2) son isomorfos si hay una función biyectiva f desde V 1 a V 2 con la propiedad que a y b son adyacentes en G 1 si y solo si f ( a ) y f ( b ) son adyacentes en G 2, para todo a y b en V 1.

3. Grafos de Petersen Grafo 1 Grafo 2 Grafo 3

4. Isomorfismos entre grafos Caso #1: Grafos 1 y 2 Primero: Vamos a identificar los v értices de los dos grafos a comparar . a b c d e f g h i j 1 2 3 8 9 10 4 5 6 7

5. Isomorfismos entre grafos Caso #1: Grafos 1 y 2 Segundo: Buscamos una función que sea biyectiva entre ambos grafos . Aquí encontramos que : F(x) x f(a) 1 f(b) 2 f(c) 3 f(d) 8 f(e) 9 F(x) x f(f) 10 f(g) 6 f(h) 4 f(i) 7 f(j) 5 Son isomorfos

6. Isomorfismos entre grafos Caso #2: Grafos 1 y 3 Primero: Vamos a identificar los v értices de los dos grafos a comparar . a b c d e f g h i j 1 2 3 8 9 10 4 5 6 7

7. Isomorfismos entre grafos Caso #2: Grafos 1 y 3 Segundo: Buscamos una función que sea biyectiva entre ambos grafos . Aquí encontramos que : F(x) x f(a) 6 f(b) 1 f(c) 2 f(d) 8 f(e) 5 F(x) x f(f) 10 f(g) 7 f(h) 3 f(i) 9 f(j) 4 Son isomorfos

8. Isomorfismos entre grafos Como el Grafo 1 es isomorfo al Grafo 2 y el Grafo 1 también es isomorfo al Gafo 3, entonces , por la propiedad transitiva : Grafo 2 es isomorfo al grafo 3

9. Isomorfismos entre grafos

10. Bibliografía Bundy, J. A.; Murty , U. S. R.; Graph Theory; 2008; páginas 12 a 18.

11. Gracias por su atención Busca la presentación en: Http:/rosaepadilla.blogspot.com