DIGRAFOS
Presentado a :
Ing. Mario Macea Anaya
INTEGRANTES
Randy Fuentes Ramos
Yinnela Cárdenas Usprung
UNIVERSIDAD DE CÓRDOBA- COLOMBIA
FACULTAD DE INGENIERÍAS
INGENIERÍA DE SISTEMAS YTELECOMUNICACIONES
DÍGRAFOS
Un grafo dirigido o dígrafo es una terna G =(V, A, F)
consta de un conjunto V de vértices con V ≠ , un
conjunto A de arcos dirigidas, y la función de
incidencia F(g)le hace corresponder a cada arco un
par ordenado de vértices, al primero se lo llama
extremo inicial de la arista, y el segundo es el
vértice final.
EJEMPLO DE DÍGRAFOS
a2
a1
a1
a4
a3a8
a7
a10
a4
a3
a5
a9
a1
a6
a5
a2
DÍGRAFOS VACÍO
Se denomina dígrafo vacío , cuando existe un
conjunto V=n y el conjunto de arcos A(D) es
un conjunto vacío y seencuentre denotado
por:
DÍGRAFO TRIVIAL
Dígrafo vacío con un solo vértice donde
DÍGRAFO SIMPLE
Un dígrafo simple D se denomina simple si
no posee ni bucles ni aristas paralelas.
BUCLESSe forma cuando el vértice inicial y final de una
arista es el mismo vértice.
ARCOS PARALELAS
Si dos o más aristas poseen el mismo vértice inicial
y el mismo vértice final
Ejemplo:
Bucles yAristas Paralelas
Aristas Paralelas
BUCLE
7
GRADO DE UN DÍGRAFO
GRADO POSITIVO DE UN VÉRTICE: g+(v): es la cantidad de aristas que
inciden positivamente en V. (flechas que salen )
GRADONEGATIVO DE UN VÉRTICE: g-(v) es la cantidad de aristas que
inciden negativamente en V (flechas que llegan).
GRADO TOTAL:
Es la suma de los grados positivo y negativo. Se denota:
EJEMPLO: GRADOEN DÍGRAFO
+flechas que Salen - flechas que llegan
a2
V2
V3
a4
a1 a3
a5
a8
V4
V1
a6
a10
1
a7
a9
2
3
V5
V6
a11
Nótese que la suma de los gradostotales de un dígrafo es igual a dos veces el
número de arco, es decir:
9
DíGRAFO NOTABLES
DÍGRAFOS SIMÉTRICO:
Un Dígrafo simple donde
para toda arista
El arco
existe en
Hay una...
Regístrate para leer el documento completo.