Guia 2 - Conceptos fundamentales digrafos

Vista previa del material en texto

CONCEPTOS FUNDAMENTALES DE DÍGRAFOS 
- 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
DESARROLLO 
 
 
1. Definición de Dígrafo 
 
Un Dígrafo D es una terna (V(D), A(D), f(D)) donde V(D) es un conjunto no vacío, cuyos 
elementos son llamados vértices, A(D) es otro conjunto, cuyos elementos son llamados 
aristas, f(D) es una función de incidencia que asigna a cada arista un par de vértices 
ordenados, el primer elemento de dicho par es llamado cola de la arista, el segundo es 
llamado la cabeza de la arista. Estos dos vértices son llamados los extremos de la arista. 
 
Ejemplo: Sea D=(V,A) Donde 
 V(D)= {1, 2, 3, 4, 5, 6} 
 A(D)={(1, 2),(2, 3),(3, 4),(4, 3),(1, 5),(5, 2),(1, 6),(6, 5)} 
 f(D)={(1, 2),(2, 3),(3, 4),(4, 3),(1, 5),(5, 2),(1, 6),(6, 5)} 
 
 
 
Figura 1: Digrafo D 
 
 
 
 
 
2. Representación gráfica de un Dígrafo: un dígrafo se representa gráficamente como 
un conjunto de puntos (vértices o nodos) unidos por líneas (aristas) dirigidas. 
 
2.1 Vértices: Se indica comúnmente por medio de un pequeño círculo y se les asigna 
un numero o letra. 
Ejemplo: La figura 1 se compone de los siguientes vértices 
V(D)= {1, 2, 3, 4, 5, 6} 
2.2 Arco o aristas: las aristas tienen un sentido definido, a diferencia del grafo no 
dirigido, en el cual las aristas son relaciones simétricas y no apuntan en ningún 
sentido 
 
Ejemplo: La figura 1 se compone de las siguientes aristas 
 A(D)={(1, 2),(2, 3),(3, 4),(4, 3),(1, 5),(5, 2),(1, 6),(6, 5)} 
 
 
2.3 Función de incidencia: En este caso la función de incidencia se dice dirigida. La 
función de incidencia D le hace corresponder a cada arista un PAR ORDENADO de 
vértices, al primero se lo llama EXTREMO INICIAL de la arista, y el segundo es el 
VERTICE FINAL. 
 
Ejemplo: La figura 1 se compone de la siguiente función de incidencia 
 
f(D)={(1, 2),(2, 3),(3, 4),(4, 3),(1, 5),(5, 2),(1, 6),(6, 5)} 
 
 
 
3. Algunas Situaciones Dadas En Dígrafo 
3.1. Bucle o rizo: Se forma cuando el vértice inicial y final de una arista es el mismo 
vértice 
 
Ejemplo: 
 
 
Figura 2: Bucle 
3.2. Aristas paralelas: Si dos o más aristas poseen el mismo vértice inicial y el mismo 
vértice final 
 
Ejemplo: 
 
 
Figura 3: Arista Paralela 
 
4. Tipos de Dígrafos 
4.1 Dígrafo vacío: se denomina dígrafo vacío, cuando existe un conjunto |V|=n y el 
conjunto de aristas A(G) es un conjunto vacío y se encuentra denotado por: 
 
|V|=n y A(D)= Ø 
Ejemplo: 
 
Figura 4: Dígrafo Vacío 
 
4.2 Dígrafo Trivial: es un dígrafo vacío con un solo vértice donde V(D)={v}. 
 
Ejemplo: 
 
Figura 5: Dígrafo Trivial 
 
4.3 Dígrafo simple: Un Dígrafo G es simple si no posee ni bucle, ni aristas paralelas. 
 
Ejemplo: 
 
Figura 6: Dígrafo Simple 
 
 
5. Dígrafos notables 
6.1. Dígrafo simétrico: Es un dígrafo simple D= (V(D), A(D), f(D)), donde para toda arista 
a ∈ A(D) con f(a) = (Vi, Vj) existe en A(D) la arista a´ con f(a´) = (Vj, Vi). Hay una 
correspondencia de uno a uno. 
Ejemplo: 
 
 
Figura 7: Dígrafo Simétrico 
6.2. Dígrafo Asimétrico: Es un dígrafo simple G= (V(G), A(G), f(G)), donde para toda 
arista a ∈ A(G) con f(a) = (Vi, Vj), la arista a´ con f(a´) = (Vj, Vi) no pertenece a A(G) 
Ejemplo: 
 
 
Figura 8: Dígrafo Asimétrico 
 
6.3. Dígrafo completo: Un dígrafo simple D= (V(D), A(D), f(D)), es completo si para 
todo par de vértices Vi,Vj ∈ V(D), existe al menos, una de las aristas con a con f(a) = 
(Vi, Vj) o a´ con f(a´) = (Vj, Vi). 
Ejemplo: 
 
 
Figura 9: Digrafo Completo 
6.4. Dígrafo simétrico completo: Un dígrafo simple D = (V(D), A(D), f(D)), donde si para 
todo par de vértices Vi, Vj ∈ V(D), las aristas a con f(a) = (Vi, Vj) y a´ con f(a´) = (Vj, 
Vi) pertenecen a A(D), se denota por Kij. 
Ejemplo: 
 
Figura 10: Dígrafo Simétrico Completo con 4 vértices 
6.5. Torneo: Es un dígrafo simple asimétrico completo. 
Ejemplo: 
 
Figura 11: Torneo 
6.6. Dígrafo K- Regular: Un dígrafo simple G= (V(D), A(D), f(D)), se llama K-regular, si 
para todo vértice v ∈ V(D), g+(v) = g-(v) = k 
Ejemplo: 
 
Figura 12: Dígrafo 1- regular con 4 vértices 
 
 
 
 
6. Grado de un Dígrafo: 
6.1. Función grado en un grafo: Si “a1” es un arco con f(a1) = (u, v) decimos que a1 
incide positivamente en u y negativamente en v. 
 
6.2. Grado positivo de un vértice: Cantidad de aristas que inciden positivamente en 
el vértice (son las que “Salen” del vértice). Se denota g+ (v) 
 
6.3. Grado negativo de un vértice: Cantidad de aristas que inciden negativamente en 
el vértice (son las que “Entran” al vértice). Se denota g˗(v). 
 
6.4. Grato total: Es la suma de los grados positivos y negativos. Se denota como: 
 
g(v) = g+ (v) + g- (v) 
 
Ejemplo 
 
 
De la definición anterior tenemos: 
g+ (1) = 3 g- (1) = 0 g (1) = 3 
g+ (2) = 1 g- (2) = 2 g (2) = 3 
g+ (3) = 1 g- (3) = 2 g (3) = 3 
g+ (4) = 1 g- (4) = 1 g (4) = 2 
g+ (5) = 1 g- (5) = 2 g (5) = 3 
g+ (6) = 1 g- (6) = 1 g (6) = 2 
 
En D = (V,A,f ), ∑ 𝒈+𝒗€𝑽 (V) = ∑ 𝒈
−
𝒗€𝑽 (V) = |A|; 
 
Es decir: la suma de los grados positivos de los vértices es igual a la suma de los grados 
negativos y es igual a la cantidad de aristas del dígrafo 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
EJERCICIOS/ACTIVIDADES 
Taller 2 
 
1. Dibujar el dígrafo g según lo que expresan los siguientes conjuntos: 
 V(D) = {a, b, c, d, e, f} 
 A(D) = {1, 2, 3, 4, 5, 6, 7, 8, 9} 
 f(D) = {f(1)=(a, b); f(2)=(b, c); f(3)=(c, d); f(4)=(d, e); f(5)=(e, f): 
 f(6)=(f, b); f(7)=(g, f); f(8)=(g, a); f(9)=(a,a) } 
2. Del dígrafo anterior calcule grados positivos, negativos y total. 
3. Construir 3 tipos de dígrafos de 5 vértices. 
 
 
 
BIBLIOGRAFIA 
 
 
 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.