Isomorfismo de grafos

UNIVERSIDAD  NACIONAL  SAN CRISTOBAL  DE HUAMANGA FACULTADAD DE INGENIERIA DE MINAS GEOLOGIA Y CIVIL

ESCUELA DE FORMACION  PROFESIONAL DE INGENIERIA DE SISTEMAS

latex/images (27).jpg [pic 1]

ISOMORFISMO DEGRAFOS

DOCENTE: ALUMNOS:

FERNANDEZ HUMAN´I,Juan LUYO QUISPE ,Diego Armando MALDONADO MARCELO,Armando MORENO HINOSTROZA,Ronald Anderson

AYACUCHO-PERU

2014

´Indice

1.  ITRUDUCCION         3

2.  Tipos de Grafos         3

2.1.  Grafos Simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        3

2.2.  Multigrafos  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        3

2.3.  Pseudografo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        3

2.4.  Grafo Dirigido    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        3

2.5.  Multigrafo Dirifido  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        3

3.  FAMILIAS DISTINGUIDAS DE  GRAFOS SIMPLES         3

3.1.  Grafos Completos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        4

3.2.  Ciclos  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        4

3.3.  Ruedas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        4

3.4.  Grafos Bipartitos  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        4

3.4.1.  Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        4

3.4.2.  Ejemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        5

3.4.3.  Ejemplo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        5

3.4.4.  Ejemplo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        5

3.4.5.  Ejemplo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        5

4.  TERMINOLOGIA  BASICA        5

4.1.  Definicion 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        5

4.2.  Definicion 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        5

4.2.1.  Ejemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        6

4.3.  TEOREMA  1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        6

4.3.1.  Teorema de los Apretones de Mano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        6

4.4.  Ejemplo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        6

4.5.  TEOREMA  2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        6

4.6.  Definicion 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        6

4.7.  Definicion 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        7

4.8.  Ejemplo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        7

4.8.1.  TEOREMA  3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        7

5.  APLICACIONES DE  TIPO ESPECIAL DE  GRAFOS         7

5.1.  Topolog´ıa de Estrella . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        8

5.2.  Topologia de Anillo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        8

5.3.  Topologia Hibrida   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        8

6.  REPRESENTACIO´ N  DE  GRAFOS E ISOMORFISMO DE  GRAFOS         8

6.1.  INTRUDUCCION  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        8

6.2.  REPRESENTACIO´ N DE GRAFOS   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        9

6.3.  Definicion  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        9

6.4.  Ejemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        9

6.5.  EJEMPLO 3  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   10

3

ISOMORFISMO DE GRAFOS

11 de octubre de 2014

1.         ITRUDUCCION

Introducci´on en esta secci´on parte del vocabulario b´asico de la teor´ıa de grafos. Utilizamos este vocabulario  para resolver muchos tipos distintos de problemas. Uno de ellos trata de determinar si un grafo se puede dibujar o no en el plano de manera que sus aristas no se corten. Otro problema  es el de decidir si hay alguna biyecci´on entre los v´ertices de dos grafos que determine una correspondencia biyectiva entre las aristas de los grafos. Tambi´en introduciremos varias familias importantes de grafos que se usan  con frecuencias en ejemplos y modelos.

...