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.

2.    Tipos de Grafos

Existen muchos tipos de grafos veremos las m´as importantes.

2.1.    Grafos Simples

Un grafo G=(V,E) consta de V, un conjunto no vacio de v´ertices, y de E, un conjunto de pares no ordenados de elementos distintos de V. A estos pares se les llama aristas.

2.2.    Multigrafos

Un grafo G=(V,E) consta de un conjunto V de v´ertices, un conjunto E de aristas y una funci´on f de E en

{{u, v}/u, v ∈ V, u Ç v}.Se dice que las aristas e1  y e2  son aristas mu´ltiples o paralelas si f (e1 ) = f (e2 ).

2.3.    Pseudografo

Un grafo G=(V,E) consta de una conjunto V de v´ertices, un conjunto E de aristas y una funci´on f y de E

en {{u, v}/u, v ∈ V }.U na arista e es un bucle, o lazo, si f (e) = {u, u} = {u} para algu´n u ∈ V.

2.4.    Grafo Dirigido

Un grafo dirigido(V,E)  que consta de un conjunto de V de v´ertices y de un conjunto E de aristas, que son pares ordenados de elementos de V. Utilizamos una flecha apuntando desde u hacia v para indicar la direcci´on de la arista (u,v).

2.5.    Multigrafo Dirifido

Un mult´ıgrafo dirigido G=(V,E) consta de un conjunto de V de v´ertices, un conjunto E de aristas y una funci´on f de E en {{u, v}/u, v ∈ V }.Se dice que lasaristas e1  y e2  son aristas mu´ltiples si f (e1 ) = f (e2 ).

3.         FAMILIAS DISTINGUIDAS DE  GRAFOS SIMPLES

...