UNIVERSIDAD FERMÍN TORO

DEPARTAMENTO DE MATEMÁTICAS
ING. MSC. ADRIANA BARRETO

DIGRAFOS

Dígrafos (Grafo Orientado o Dirigido).

Grafo direccionado o dirigido es un grafo con direcciones asignadas a sus aristas. A

es un conjunto de pares de vértices denominados arcos.

Considere un grafo definido por:

Una relación definida por A no es simétrica pues si [v es padre / madre

de w], no se cumple que [w es padre / madre de v]. Por tanto, es una
dirección.

Luego:

Un dígrafo es una terna D = [V, A, f] constituida por:

a) Un conjunto no vacío cuyos elementos se denominan vértices,

b) un conjunto A cuyos elementos son llamados arcos, y

c) una aplicación f: A V x V que le asocia a cada elemento

de A un único par ordenado de vértices (u,v); f es llamada
aplicación de incidencias.

Representación:
* Los elementos de V son representados por letras minúsculas o por x1, x2,
x3, ... o v1, v2, v3, ...

* Los arcos son denotados por a, b, c, ... , a1 a2, a3 , ...

pág. 1
 * Para mostrar el efecto de la aplicación sobre los arcos se escribe a = (u,
v), se dice que u es el origen o vértice inicial del arco a y que v es final o
vértice final del arco a

Ejemplo.

Dados V = { x, y, z, w } y A = { a, b, c, d, e }, la aplicación siguiente sirve

para construir un dígrafo D = [ V, A, f ].

α a b c d e

f( α ) (x,w) (y,x) (x,y) (z,w) (z,z)

Representación gráfica de tipo “sagital”:

x
c
e
z d w
a b
y

Observación.

En la definición de dígrafo, el conjunto de vértices V no puede ser nulo;

pero el conjunto de arcos A sí puede ser vacío. En el primer caso, el dígrafo
que resulta es llamado “dígrafo nulo”; en caso de ser finito se representa
sagitalmente con vértices aislados.

Dígrafo Nulo Dígrafo Nulo Dígrafo Nulo

Un vértice con un vértice Dos vértices con dos vértices Tres Vértices . . .
con tres vértices

Definición de multiplicidad, lazo, arcos paralelos y opuestos, y dígrafo finito.

Sea D = [ V, A, f ] un dígrafo:

a) Para v1, v2 ∈ V, la multiplicidad del par (v1, v2) es el número entero positivo
m(v1, v2) := card { a ∈ A / f( a ) = (v1, v2) }

pág. 2
b) Un lazo en D es un arco que tiene vértice inicial = vértice final.
c) Dos arcos a1 y a2 son paralelos sii f(a1) = f(a2).
(osea, “origen de a1 = origen de a2 “ y “final de a1 = final de a2” )
d) Dos arcos b1 y b2 son opuestos sii “vértice inicial de b1 = vértice final
de b2” y “vértice final de b1 = vértice inicial de b2”
e) El dígrafo D es finito sii son finitos los dos conjuntos A y V.

Ejemplo.

En la figura anexa se encuentra la representación sagital de un dígrafo finito D,

que tiene 5 vértices y arcos. v1
a1 a2
D v5 a8 a9
a7
El arco a1 es un lazo. a5 a6 v2

Los arcos a7 y a8 son paralelos: también son paralelos

v4 a3 v3
A7 y a9 (a4 y a7 también son paralelos)
Además, con esos 3 arcos vemos que m( v1 , v2 ) = 3 pero m( v2 , v1 ) = 0

Otras multiplicidades son: m( v5 , v5 ) = 1, m( v5 , v4 ) = 1

m( v3 , v2 ) = 0, m( v2 , v5 ) = 0
m( v2 , v4 ) = 1, m( v4 , v2 ) = 1

En el dígrafo D hay apenas una pareja de arcos opuestos, a saber a6 y a3

Matriz de conexión.

Para cualquier dígrafo finito D = [ V, A, f ] que tenga conjunto de vértices

V = { v1 , v2 , . .. , v3 ] se denomina matriz de conexión a la matriz nxn que se
construye con las multiplicidades de todos los pares en la forma siguiente:

m( v1 , v1 ) m( v1 , v2 ) m( v1 , v3 ) . . . m( v1 , vn )
McD = m( v2 , v1 ) m( v2 , v2 ) m( v2 , v3 ) . . . m( v2 , vn )
.
.
.
m( vn , v1 ) m( vn , v2 ) m( v2 , v3 ) . . . m( vn , vn )

pág. 3
Ejemplo.

Para el dígrafo finito D del ejemplo anterior, la matriz de conexión es:

0 3 0 0 1
0 0 0 1 0
McD = 0 0 1 0 0
0 1 0 0 0
0 0 0 1 1

Dígrafo simple.

Sea D = [ V, A, f ] un dígrafo. Diremos que D es simple sii en D no hay lazos ni

arcos paralelos. Es decir, D es un dígrafo simple sii ∀ u, v ∈ V se cumple que:

M(u, v) = 0 si u = v
M(u, v) ≤ 1 si u ≠ v

Ejemplos.

1. El dígrafo del ejemplo anterior no es simple.

2. Consideremos el dígrafo anterior, el dígrafo simple asociado a D es:
v1
v5 a2
a4
D*
a6
a5 v2

v4 a9
v3

Se realizó un proceso de simplificación en dos pasos:

1. eliminar en D todos los lazos,

2. eliminar los “manojos” de arcos paralelos, dejando apenas uno de ellos.

Al culminar el proceso, el dígrafo D resultante es el dígrafo simple D*, presentado

anteriormente.

pág. 4
 La matriz de conexión de D es:

0 1 0 0 1
0 0 0 1 0
McD = 0 0 0 0 0
0 1 0 0 0
0 0 0 1 0

Observación.

Cada dígrafo simple Ds tiene asociada una relación binaria ℜ, definida en los
vértices del dígrafo Ds en la forma siguiente:

u ℜ v ⇔ existe un arco a con “origen = u” y “final = v”

o sea, u ℜ v ⇔ m(u, v) = 1

Cuando un dígrafo Ds es finito, resulta que Ds y R tienen la misma representación

sagital; además, también coincide la representación matricial de la Relación ℜ y la
matriz de conexión de Ds ( Mℜ = Mc(Ds). En el ejemplo siguiente es especificada la
relación binaria R asociada al dígrafo simple Ds del ejemplo anterior.

Ejemplo.

Para el dígrafo simple Ds del ejemplo anterior, la relación binaria correspondiente

es la siguiente:
v1 ℜ v2 y v1 ℜ v5 (debido a las arcos a1 y a4 )
v2 ℜ v4 y v4 ℜ v2 (debido a los arcos a6 y a3 )
y v5 ℜ v4 (debido al arco a5 )

Potencias de R. Trayectorias.

Si en un conjunto no-vacio V tenemos dos relaciones binarias R y R, se define la

relación compuesta R o R en la forma siguiente:

u(R o R) v ⇔ ∃ x ∈ V / u R x y x R v (u,v ∈ V)

Si escogemos R = R, entonces al buscar la compuesta R o R obtenemos la

relación R o R = R2; si utilizamos R = R2, entonces la compuesta R o R en realidad
R o R2 = R3 y al continuar este proceso inductivo se forman potencias de la relación
R. Así tenemos que

∀ k ∈ N se define R1+k := R o Rk , (R1= R)

La composición de relaciones no es conmutativa; sin embargo, en algunos casos

particulares sí es válida tal propiedad.

Lema 1.1.

R O R k = Rk o R , ∀k∈N

pág. 5
 Supongamos ahora que V es un conjunto finito, de manera que la relación R
admite representación matricial MR binaria y cada una de sus potencias Rk
también tiene representación matricial binaria, MRK. Entonces tenemos el
resultado siguiente:

Lema 1.2

MRK = (MR)K

Finalmente, tenemos una manera de interpretar las potencias Rk de R en

términos de los vértices y los arcos del dígrafo, cuando R es la relación binaria
asociada a un dígrafo simple.

Teorema 1.1

Sea Ds un dígrafo simple y sea R la relación binaria asociada a Ds. Si uo , uk

son vértices del dígrafo Ds, entonces se cumple que uo Rk uk ⇔ existen vértices
u1,,u2 ,... ,uk-1 y arcos a1 a2 , ..., ak en A, tales que a1 = (uo ,, uo) , a2 =
(u1 , u2), . . ., ak = (uk-1 , uk) (k≥2)

a2
a1 u1 u2 uk-1
ak
k
u0 u0 R u k
uk

Caminos y Circuitos.

Trayectoria y ciclo.

En un dígrafo D = [ V, A, f ], llamaremos:

a) Trayectoria a cualquier secuencia finita de vértices y arcos alternados en la

forma:
T = [wo , a1 , w1 , a2 , w2 , ... , wr-1 , ar , wr ] , r ≥ 1,
y tales que ai = (wi-1,wi) , i = 1, 2, . . . , r (el número de arcos que hay en la
trayectoria se denomina orden de la trayectoria y se denota por o(T) ).
b) Trayectoria Simple a cualquier trayectoria que no repita arcos y trayectoria
elemental a cualquier trayectoria que no repita vértices.
c) Ciclo o Circuito a cualquier trayectoria que tenga iguales el primer vértice y el
último vértice.
d) Ciclo Simple a cualquier ciclo que no repita arcos.

pág. 6
Ejemplo.
1 v1 13 v6
9
2 11 10
v2 12

6 v5
v4
4 7
v3
5

En el dígrafo de la figura anterior, una trayectoria de orden 1 es:

T1 = [ v1 , 1 , v2 ], además, T1 es simple y elemental.
Por su parte, C1 = [ v3 , 6 , v3 ] es un ciclo simple de orden 1.

Digrafo fuertemente conexo.

En un dígrafo D = [ V, A, f ] , consideremos dos vértices u, v. Diremos que:

el vértice v es accesible al vértice u sii u = v o existe una trayectoria que
comienza en el vértice u y termina en el vértice v.

Un dígrafo D se denomina fuertemente conexo cuando cada vértice v del dígrafo

D es accesible desde cada uno de los demás vértices.

Ejemplo.

En el dígrafo del ejemplo anterior, desde v1 se puede ir a los demás vértices

utilizando las trayectorias siguientes:

T1 = [ v1 , 1 , v2 ], T2 = [ v1 , 1 , v2 , 3 , v3 ], T3 = [ v1 , 1 , v2 , 3 , v3 , 4 , v4 ],
T4 = [ v1 ,13 , v6 ] y T5 = [ v1 , 13 , v6 , 9 , v5 ].

Así, cada vértice del dígrafo D es accesible desde el vértice v1 (incluso el mismo v1
)
Pero desde v6 sólo se puede ir a v5 y desde v5 sólo hay trayectorias hacia los
vértices v1 , v2 , v3 , v4 no son accesibles desde v5 . En consecuencia, el dígrafo del
ejemplo anterior no es fuertemente conexo.

Corolario 1.1

Un dígrafo D es fuertemente conexo ⇔ también es fuertemente conexo el

dígrafo simple D* asociado a D.

Matriz de accesibilidad.

Dado un dígrafo finito simple Ds con n-vértices y con matriz de conexión M =

Mc(Ds), llamaremos matriz de accesibilidad del dígrafo Ds a la matriz binaria
Acc(Ds) que se calcula según la fórmula siguiente:

pág. 7
 2 n-1
Acc(Ds) = bin[ In + M + M + ...+M ]

En esta fórmula, In es la matriz identidad nxn; las sumas indicadas se realizan en

forma usual y bin significa que la matriz resultante de la suma In + M + M 2+...+ M
n-1
debe ser transformada de acuerdo con las normas siguientes:

componente que sea igual a 0, permanece como 0

componente que sea diferente de 0, convertirla a 1.

Para un dígrafo no-simple y finito D que tenga dígrafo simple asociado D*, se
def.:
Acc(D) = Acc(D*)

Corolario 1.2

Un dígrafo finito D es fuertemente conexo ⇔ la matriz Acc(D) no tiene

componentes nulas.

Ejemplo.

La figura muestra un dígrafo finito no-simple D.

v1

v3
v2
v4

v5 v7

v6

La matriz de conexión de este dígrafo es:

0 2 0 0 0 0 0
1 0 0 1 2 0 0
2 0 2 1 0 0 2
Mc(D) = 0 1 1 0 0 0 2
0 0 0 2 0 1 0
0 0 0 0 0 1 1
0 0 0 0 0 0 1

La matriz de conexión M del dígrafo simple D* asociado a D es la siguiente:

pág. 8
 0 1 0 0 0 0 0
1 0 0 1 1 0 0
1 0 0 1 0 0 1
M = Mc(D*) = 0 1 1 0 0 0 1
0 0 0 1 0 1 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

Y sus potencias se muestran a continuación, hasta M4.

1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 0 1

0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1

0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 1 0 1 1

M2 = 1 0 0 1 1 0 1 M3 = 0 1 1 1 0 1 1 M4 = 1 1 1 1 1 0 1

0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 1 0 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 Resuelva las potencias M5 y M6.

Finalmente: Acc(D) = Acc(D*) = bin [I7 + M + M2 + M3 + M4 + M5 + M6 ]

5 5 4 5 4 3 4
5 6 5 6 5 4 5
4 4 5 5 3 2 6
Acc(D) = bin 4 5 5 6 4 3 6
3 4 4 5 4 3 5
0 0 0 0 0 1 1
0 0 0 0 0 0 1

1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
= 1 1 1 1 1 1 1
1 1 1 1 1 1 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1

Como la matriz de accesibilidad del dígrafo Acc(D) tiene componentes nulos (ceros)
entonces se puede afirmar que el dígrafo NO es fuertemente conexo.

pág. 9
Digrafos ponderados. Trayectorias óptimas.

Definición: Una ponderación de un dígrafo D es una función p: A -> R > 0, que le

asocia a cada arista un único número real positivo.

Definición: Dado un grafo ponderado G= (V, A) (dirigido o no) y un camino w1, w2, ...,
wq en G, la ponderación del camino (trayectoria o cadena) será la suma de los costos
asociados a las aristas (w1, w2), ..., (wq-1, wq).

• Si el grafo es no ponderado, normalmente el costo se asocia con la longitud del

camino.

Definición: Sea D=[V, A, f] un dígrafo y sea p: A -> R > 0 una ponderación para D,
para cualesquiera vértices u, v є V se define la distancia de u a v en la siguiente
forma:

0 si u = v

Dist (u, v) = ∞ si u ≠ v y T(u, v) es vacío

P (To) si u ≠ v y T(u, v) ≠ vacío y To es una trayectoria

(camino) óptimo de u a v

Ejemplo:

Dado el siguiente dígrafo, calcular la distancia de v1 a v5 y de v3 a v4

v1 a1-> 2 v2 a2-> 3 v3

3 1 4
a3-> a4-> a5-> a6-> a7->
2 3
v4
4 a8-> v5

Caminos de v1 a v5

V1, a1->, v2, a6->, v5

Ponderación = 2 + 4 = 6 <- camino o trayectoria óptima

V1, a3->, v4, a5->, v2, a6->, v5

Ponderación = 2 + 1 + 4 = 7

V1, a3->, v4, a4->, v1, a1->, v2, a6->, v5

Ponderación = 2 + 3 + 2 + 4 =11

pág. 10
Dist (v1, v5) = 6

Como no existen caminos de v3 a v2, entonces Dist (v3, v2) = ∞

Algoritmo de Dijkstra

Es un algoritmo que se utiliza para calcular las distancias de un vértice inicial a los
demás vértices en un dígrafo finito y ponderado.

Algoritmo de Dijkstra

función Dijkstra ( L [ 1..n , 1..n ] ) : vector

C := { 2 , 3 , ... , n } ;
para i := 2 hasta n hacer
D [ i ] := L [ 1 , i ] ; {1}
{ bucle voraz : }
repetir n-2 veces:
v := nodo de C que minimiza D [ v ] ;
C := C \ { v } ;
para cada w en C hacer
D [ w ] := min ( D [ w ] , D [ v ] + L [ v , w ] ) {2}
devolver D
fin función

{1} D [ i ] := L [ 1 , i ] ; P [ i ] := 1
{2} si D [ w ] > D [ v ] + L [ v , w ] entonces
D [ w ] := D [ v ] + L [ v , w ] ;
P [ w ] := v

En el desarrollo de este algoritmo se utiliza una función auxiliar que no debe ser
confundida con la distancia; esta función se define de la forma siguiente:

0 si u = v

δ (u, v) = ∞ si u ≠ v y no hay aristas de u a v

min {p(a)} si u ≠ v y existen aristas de u a v, se

selecciona la de menor ponderación

La tabla siguiente describe el algoritmo que se utiliza para calcular las distancias de un
vértice inicial v0 a los demás vértices del dígrafo. Los valores iniciales son:

u0* = v0
d0(u0*) = 0

pág. 11
d0(v) = ∞ para todo v ≠ v0

DATOS PARA
PASO VÉRTICES EL PASO A CÁLCULO DE di+1 SELECCIÓN DE
UTILIZADOS DESARROLLAR u*i+1
0 Uo = {v0} u0* = v0 Para todo v que no exista en el Seleccionar el
d0(u0*) = 0 conjunto Ui calcular vértice u1* que va
d0(v) = ∞ d1(v) = min {do(v); δ(uo*, v)} a ser aquel vértice
si v ≠ v0 donde d1(v) es el
mínimo entre todos
los d1 calculados en
este paso
1 U1 = {v0, u1*, Para todo v que no exista en el Seleccionar el
u1*} d1(u1*), conjunto Ui calcular vértice u2* que va
d1(v) para todo d2(v) = min {d1(v); d1(u1*) + a ser aquel vértice
v que no se δ(u1*, v)} donde d2(v) es el
encuentre en el mínimo entre todos
conjunto Ui los d2 calculados en
este paso
2 U2 = {v0, u2*, Para todo v que no exista en el Seleccionar el
u1*, u2*} d2(u2*), conjunto Ui calcular vértice u3* que va
d2(v) para todo d3(v) = min {d2(v); d2(u2*) + a ser aquel vértice
v que no se δ(u2*, v)} donde d3(v) es el
encuentre en el mínimo entre todos
conjunto Ui los d3 calculados en
este paso
. . . . .

. . . . .

. . . . .

i Ui = {v0, u1*, ui*, Para todo v que no exista en el Seleccionar el

u2*, …, ui*} di(ui*), conjunto Ui calcular vértice ui+1* que
di(v) para todo di+1(v) = min {di(v); di(ui*) + va a ser aquel
v que no se δ(ui*, v)} vértice donde
encuentre en el di+1(v) es el
conjunto Ui mínimo entre todos
los d3 calculados en
este paso

Este proceso finaliza cuando el conjunto Ui es igual al conjunto de los vértices del
dígrafo (V), es decir, que contiene todos los vértices del dígrafo.

Lea las distancias encontradas con los números mínimos di+1(ui+1*)

seleccionados en los diversos pasos del procedimiento, es decir, d1(u1*) = dist (v0,
u1*), d2(u2*) = dist (v0, u2*), …

Cada una de esas distancias puede ser finita o infinita. Si es infinita significa que
no hay caminos (trayectorias) de v0 a ui*; en caso contrario significa que si hay

pág. 12
camino entre v0 y ui*, por lo tanto existe por lo menos un camino óptimo cuya
ponderación es dist (v0, ui*).

Esta trayectoria o camino óptimo puede ser encontrado con el método de

retroceso que se desarrolla sobre la misma tabla en la que fueron colocados los datos
y cálculos del algoritmo para buscar distancias.

Si dist (v0, ui*) es finita

Ejemplo:

Calcular la distancia de v2 a los demás vértices del dígrafo del siguiente digrafo
utilizando el algoritmo para calcular distancias de un vértice a los demás vértices de un
digrafo

v1 a1-> 2 v2 a2-> 3 v3

3 1 4
a3-> a4-> a5-> a6-> a7->
2 3
v4
4 a8-> v5

DATOS PARA
PASO VÉRTICES EL PASO A CÁLCULO DE di+1 SELECCIÓN DE
UTILIZADOS DESARROLLAR u*i+1
0 Uo = {v2} uo* = v2 d1(v1) = min {do(v1); δ(uo*, v1)} Seleccionamos el
do(uo*) = 0 = min {∞; ∞} = ∞ vértice u1* = v3 ya
do(v1) = ∞ d1(v3) = min {do(v3); δ(uo*, v3)} que es el mínimo
do(v3) = ∞ = min {∞; 3} = 3 entre los valores
do(v4) = ∞ d1(v4) = min {do(v4); δ(uo*, v4)} d1(v) calculados en
do(v5) = ∞ = min {∞; ∞} = ∞ este paso
d1(v5) = min {do(v5); δ(uo*, v5)}
= min {∞; 4} = 4

1 U1 = {v2, u1*=v3, d2(v1) = min {d1(v1); d1(u1*) + Seleccionamos el

u1*} d1(u1*)= 3, δ(u1*, v1)} = min {∞; 3 + ∞} = ∞ vértice u2* = v1 ya
d1(v1) = ∞ d2(v4) = min {d1(v4); d1(u1*) + que es como todos
d1(v4) = ∞ δ(u1*, v4)} = min {∞; 3 + ∞} = ∞ los valores d2(v)
d1(v5) = 4 d2(v5) = min {d1(v5); d1(u1*) + son iguales
δ(u1*, v5)} = min {∞; 3 + ∞} = ∞ podemos escoger a
cualquiera de los
vértices en este
paso
2 U2 = {v2, v3, U2*= v1, d3(v4) = min {d2(v4); d2(u2*) + Seleccionar u3* =
u2*} d2(u2*)= ∞, δ(u2*, v4)} = min {∞; ∞ + 2} = ∞ v4 ya que es como
d2(v4) = ∞ d3(v5) = min {d2(v5); d2(u2*) + todos los valores
d2(v5) = ∞ δ(u2*, v5)} = min {∞; ∞ + ∞} = ∞ d3(v) son iguales

pág. 13
 podemos escoger a
cualquiera de los
vértices en este
paso
3 U3 = {v2, v3, U3*= v4, d4(v5) = min {d3(v5); d3(u3*) + Seleccionar u4* =
v1, u3*} d3(u3*)= ∞, δ(u3*, v5)} = min {∞; ∞ + ∞} = ∞ v5 ya que el único
d3(v5) = ∞ vértice que se
puede seleccionar
en este paso
4 U4 = {v2, v3, Como en el
v1, v4, u4*} conjunto U
están todos los
vértices del
dígrafo se
termina el
algoritmo

Las distancias encontradas son:

Dist (v2, v1) = 3

Dist (v2, v3) = ∞
Dist (v2, v4) = ∞
Dist (v2, v4) = ∞

pág. 14