Guia 5 - Operaciones entre Grafos

Vista previa del material en texto

OPERACIÓN ENTRE GRAFOS 
- 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
DESARROLLO 
 
 
1. Unión: La unión de los subgrafos G, G1 y G2, es otro subgrafo G3 = (V3, A3, fG3) de G 
tal que V3 = V1 U V2, A3 = A1 U A2 y FG3 asigna a toda arista de A3 un par de vértices 
de V3. 
 
Ejemplo: Unir los subgrafos G1 y G2 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 2: G2 
Figura 1: G1 
G = (V, A, f) 
G(V) = {A, B, C, D, E} 
G(A) = {1,2,3,4,5} 
 
 FG (1) = (A, B), FG (2) = (A, C), 
FG = FG (3) = (C, D), FG (4) = (C, E), 
 FG (5) = (D, E) 
G = (V, A, f) 
G(V) = {A, B, C, D, E, F} 
G(A) = {2,3,5,6,7,8} 
 
 FG (2) = (A, C), FG (3) = (C, D), 
FG = FG (5) = (D, E), FG (6) = (A, B), 
 FG (7) = (B, F), FG (8) = (B, C) 
 
 
Figura 1: G1 U G2 
, 
 
 
 
2. Intersección: Sean V1 ∩ V2 ≠ 0 la intersección de los subgrafos G1 y G2, G1 ∩ G2, es 
otro subgrafo G4 = (V4, A4, fG4) de G, tal que V4 = V1 ∩ V2, A4 = A1 ∩ A2 y FG4 asigna 
a toda arista de A4 un par de vértices de V4. 
 
Ejemplo: Aplicar la intersección a los subgrafos G1 y G2 
 
 
 
 Figura 2: G1 
G = (V, A, f) 
G(V) = {A, B, C, D, E, F} 
G(A) = {1,2,3,4,5,6,7,8} 
 
 FG (1) = (A, B), FG (2) = (A, C), 
 FG (3) = (C, D), FG (4) = (C, E), 
FG = FG (5) = (D, E), FG (6) = (B, A), 
 FG (7) = (B, F), FG (8) = (B, C) 
 
G = (V, A, f) 
G(V) = {A, B, C, D, E} 
G(A) = {1,2,3,4,5} 
 
 FG (1) = (A, B), FG (2) = (A, C), 
FG = FG (3) = (C, D), FG (4) = (C, E), 
 FG (5) = (D, E) 
 
 
 
 
Figura 4: G1 ∩ G2 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 3: G2 
G = (V, A, f) 
G(V) = {A, B, C, D, E, F} 
G(A) = {2,3,5,6,7} 
 
 FG (2) = (A, C), FG (3) = (C, D), 
FG = FG (5) = (D, E), FG (6) = (A, B), 
 FG (7) = (B, F), FG (8) = (B, C) 
G = (V, A, f) 
G(V) = {A, B, C, D, E} 
G(A) = {2,3,5} 
 
 FG (2) = (A, C), FG (3) = (C, D), 
FG = FG (5) = (D, E) 
 
3. Suma de Anillos: La suma anillo de los subgrafos G1 y G2, es otro subgrafo G5 = (V5, A5, FG5) 
de G, tal que V5 = V1 U V2, A5 = (A1 U A2) – (A1 ∩ A2) y FG5 asigna a toda arista A5 un par de 
vértices de V5. 
 
 Sean M y N dos conjuntos. La diferencia simétrica de M y N, escrita (M U N) –(M ∩ N), 
es el conjunto de todos los elementos que pertenecen a M U N, pero que no pertenecen 
a M ∩ N. 
 
Ejemplo: Aplicar la suma de anillos a los subgrafos G1 Y G2 
 
 
 
 
 
 
 
 
 
Figura 5: G1 
Figura 6: G2 
G = (V, A, f) 
G(V) = {A, B, C, D, E, F} 
G(A) = {2,3,5,6,7,8} 
 
 FG (2) = (A, C), FG (3) = (C, D), 
FG = FG (5) = (D, E), FG (6) = (A, B), 
 FG (7) = (B, F), FG (8) = (B, C) 
G = (V, A, f) 
G(V) = {A, B, C, D, E} 
G(A) = {1,2,3,4,5} 
 
 FG (1) = (A, B), FG (2) = (A, C), 
FG = FG (3) = (C, D), FG (4) = (C, E), 
 FG (5) = (D, E) 
 
 
 
Figura 7: G1 + G2 
 
4. vértices fusionados: Un par de vértices a y b de un grafo G se dice que ha sido 
fusionados, si los vértices son remplazados por un nuevo vértice, tal que toda arista 
incidente en a o en b, o en ambos inciden en el nuevo vértice. 
 
 
 
Ejemplo: Del siguiente grafo fusionaremos los vértices V2 con V4 
 
 
 
 
 
Figura 8: Grafo sin fusionar 
G = (V, A, f) 
G(V) = {A, B, C, D, E, F} 
G(A) = {1,4,6,7,8} 
 
 FG (1) = (A, B), FG (4) = (C, E), 
FG = FG (6) = (B, A), FG (7) = (B, F), 
 FG (8) = (B, C) 
 
G = (V, A, f) 
G(V) = {A, B, C, D, E, F} 
G(A) = {2,3,5,6,7,8} 
 
 FG (2) = (A, C), FG (3) = (C, D), 
FG = FG (5) = (D, E), FG (6) = (A, B), 
 FG (7) = (B, F), FG (8) = (B, C) 
 
 
 
 
 
 
 
 
EJERCICIOS/ACTIVIDADES 
Taller 5 
 
Mediante un grafo del taller 4 aplique las operaciones entre grafos 
 
 
 
 
Figura 9: Grafo fusionado 
G = (V, A, f) 
G(V) = {A, C, G, E, F} 
G(A) = {2,3,5,6,7,8} 
 
 FG (2) = (A, C), FG (3) = (C, G), 
FG = FG (5) = (G, E), FG (6) = (A, G), 
 FG (7) = (G, F), FG (8) = (G, C) 
 
 
 
BIBLIOGRAFIA 
 
 
 Viloria, J. (s.f.). Scrib. Obtenido de Scrib: https://es.scribd.com/doc/209571060/Operaciones-
Entre-Grafos 
 Epp, S. (2012). Matemáticas discretas con aplicaciones (4a. ed.). 1st ed. México, D.F.: 
CENGAGE Learning, pp.625-641. 
 Jiménez Murillo, J. and Rodríguez Cruz, F. (2014). Matemáticas para la computación. 1st ed. 
México: Alfaomega Grupo Editor, pp.287-288. 
 Comellas Padró, F. (2002). Matemática discreta. 1st ed. México, D.F.: Alfaomega, pp.103-
105. 
 Wikiwand. (2017). Grafo | Wikiwand. [online] Available at: 
http://www.wikiwand.com/es/Grafo [Accessed 5 Jul. 2017]. 
 Wilson, R. and Garciá Camarero, E. (1983). Introducción a la teoriá de grafos. Madrid: 
Alianza, pp.20-50. 
 Ore, O. (1995). Grafos y sus aplicaciones. Madrid: DLS-EULER, pp.70-98.