demostracion de isomorfismos grafos petersen

Isomorfismos en Grafos de Petersen

Rosa E. Padilla TorresPresentación para la clase de Teoría de Grafos

MATH 6200Dr. Álvaro Lecompte21 de junio de 2011

Isomorfismos entre Grafos

• Los grafos simples G1 = (V1,E1) y G2 = (V2,E2) son isomorfos si hay una función biyectiva f desde V1 a V2 con la propiedad que a y b son adyacentes en G1 si y solo si f (a) y f (b) son adyacentes en G2, para todo a y b en V1.

Grafos de Petersen

Grafo 1

Grafo 2 Grafo 3

Isomorfismos entre grafosCaso #1: Grafos 1 y 2

• Primero: Vamos a identificar los vértices de los dos grafos a comparar.

a

b

cd

e

f

g

hi

j

1

2

38

9

10

4

56

7

Isomorfismos entre grafosCaso #1: Grafos 1 y 2

• Segundo: Buscamos una función que sea biyectiva entre ambos grafos.

• Aquí encontramos que:

F(x) xf(a) 1f(b) 2f(c) 3f(d) 8f(e) 9

F(x) x

f(f) 10f(g) 6f(h) 4f(i) 7f(j) 5

Son isomorfos

Isomorfismos entre grafosCaso #2: Grafos 1 y 3

• Primero: Vamos a identificar los vértices de los dos grafos a comparar.

a

b

cd

e

f

g

hi

j

1 2

38

9

10

45

67

Isomorfismos entre grafosCaso #2: Grafos 1 y 3

• Segundo: Buscamos una función que sea biyectiva entre ambos grafos.

• Aquí encontramos que:

F(x) xf(a) 6f(b) 1f(c) 2f(d) 8f(e) 5

F(x) x

f(f) 10f(g) 7f(h) 3f(i) 9f(j) 4

Son isomorfos

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

Isomorfismos entre grafos

Bibliografía

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

Gracias por su atención

• Busca la presentación en: Http:/rosaepadilla.blogspot.com