Formato Guia 2 conceptos fundamentales digrafos PDF

Preview

Summary

Conceptos fundamentales de digrafos...

Description

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+ (2) = 1 g+ (3) = 1 g+ (4) = 1 g+ (5) = 1 g+ (6) = 1

g- (1) = 0 g- (2) = 2 g- (3) = 2 g- (4) = 1 g- (5) = 2 g- (6) = 1

g (1) = 3 g (2) = 3 g (3) = 3 g (4) = 2 g (5) = 3 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 Padro , F. (2002). Matemática discreta. 1st ed. México, D.F.: Alfaomega, pp.103105. Wikiwand. (2017). Grafo | Wikiwand. [online] Available at: http://www.wikiwand.com/es/Grafo [Accessed 5 Jul. 2017]. Wilson, R. and Garci a Camarero, E. (1983). Introduccion a la teori a de grafos. Madrid: Alianza, pp.20-50. Ore, O. (1995). Grafos y sus aplicaciones. Madrid: DLS-EULER, pp.70-98....