Upload
hayde-bm
View
266
Download
0
Embed Size (px)
Citation preview
11.3 Grafos isomorfosDos grafos pueden tener la misma estructura, difiriendo slo en los nombres de los vrtices, en trminos ms precisos se tiene la siguiente definicin.
Ejemplo 11.2 Considrense los grafos de la siguiente figura.
Para ver que estos grafos son isomorfos, se define
como:
Partiendo funcin
de la
definicin, en
se puede
comprobar fcilmente
que la
es un
isomorfismo de
Se sigue directamente de la definicin que si Tambin es claro que
entonces
y
.
En el siguiente teorema se establece que el isomorfismo entre grafos es una relacin de equivalencia en el conjunto de todos los grafos. Teorema 11.2 Sean a) . , y tres grafos. Entonces
b)Si c) Si
entonces y
. . definida por en s mismo. en en , entonces ,y es un isomorfismo de en en . es un para toda es
entonces
Demostracin a) La funcin claramente un isomorfismo de b) Si c) Si es un isomorfismo de es un isomorfismo de en .
es un isomorfismo de
entonces
isomorfismo de
En este captulo el objetivo es presentar las propiedades estructurales de los grafos, por lo que con frecuencia se omitirn etiquetas cuando se dibujen. Un grafo no etiquetado puede interpretarse como un representante de una clase de equivalencia de grafos isomorfos. A continuacin se presentan algunas familias importantes de grafos, las cuales aparecern con frecuencia en los ejemplos, los ejercicios y aplicaciones.
En la siguiente figura se muestra el grafo trayectoria
:
En la siguiente figura se muestra el grafo ciclo
:
En la siguiente figura se muestra un dibujo de
:
En la siguiente figura se muestra el grafo vaco con cuatro vrtices:
En la siguiente figura se muestra el grafo bipartito completo
:
Ejemplo 11.3 Un ejemplo de un grafo 3-regular es el grafo de Petersen: