Digrafos y grafos

Capítulo 6
Digrafos y grafos

Kaliningrado - Catedral de Königsberg (Rusia Noroeste) - Río Pregel 1

Matemática Discreta
Digrafos y grafos

Digrafos – Problema inicial

En 1736 el matemático suizo Leonhard Euler plantea y
resuelve el problema de los siete puentes de Königsberg
que presentamos a continuación.

PROBLEMA: El ciclo de Euler

Dos islas que se hallan en el río Pregel en la ciudad de
Königsberg (actualmente Kaliningrado, Rusia) están
conectadas entre sí y con las márgenes del río por siete
puentes. ¿Es posible salir desde una orilla, pasear y
recorrer todos los puentes una única vez y regresar a la
misma orilla?
2
Matemática Discreta
Digrafos y grafos

Digrafos – Problema inicial

Gráficamente:

Orilla 1

Isla 1 Isla 2 Río Pregel

Orilla 2

3
Matemática Discreta
Digrafos y grafos

Digrafos
Definición:
Llamaremos grafo dirigido o digrafo a una terna
D = (V, A, ) donde V es el conjunto de vértices o nodos
de D, A denota el conjunto de arcos o flechas y  es la
función de incidencia dirigida  : A V  V, es decir, cada
elemento de A tiene asociado un par ordenado de
elementos del conjunto de vértices.

Si a  A y (a) = (v1, v2) donde v1, v2  V, entonces

decimos que v1 es el vértice o nodo inicial, fuente u
origen de a y que v2 es su vértice o nodo final o extremo.
4
Matemática Discreta
Digrafos y grafos

Digrafos

Observaciones:
1. Si A es el conjunto vacío y V no lo es, entonces D = V, es
decir el digrafo está formado por nodos o vértices
solamente y no se define la función .
2. Indicaremos con V o bien o(V) al número de nodos
de D, y conA o bien o(A) al número de arcos de D.

5
Matemática Discreta
Digrafos y grafos

Digrafos
Ejemplo de digrafo D = (V, A,  ):
V = {v1, v2, v3, v4, v5} , A = {ai, i  N, 1  i  6}.
La función de incidencia : A  V  V está definida por:
(a1) = (v1, v2); (a2) = (v2, v1); (a3) = (v2, v2);
(a4) = (v2, v3); (a5) = (v2, v4); (a6) = (v3, v1)

Otras representaciones: pictórica (o gráfica), matricial

6
Matemática Discreta
Digrafos y grafos

Adyacencia
 Dos vértices vi, vj son adyacentes si (vi, vj) o (vj, vi)
pertenecen a (A), es decir si son origen y extremo de un
mismo arco.

 Dos arcos distintos son adyacentes cuando tienen una

extremidad común.

7
Matemática Discreta
Digrafos y grafos

Incidencia de arcos en nodos

 Un arco a incide positivamente en el vértice v cuando v
es su vértice inicial u origen.
 Un arco a incide negativamente en el vértice v cuando v
es extremo final del arco a.
 Todo arco tiene incidencia positiva respecto de su vértice
inicial y negativa para su vértice final.

8
Matemática Discreta
Digrafos y grafos

Grados positivo y negativo

 Se denomina grado negativo de un vértice v al número

de arcos que inciden negativamente en él y anotaremos
como g–(v). (arcos que llegan a v)
 Análogamente, el grado positivo de un vértice v será el
número de arcos que inciden positivamente en él y lo
indicaremos como g+(v). (arcos que salen de v)

9
Matemática Discreta
Digrafos y grafos

Grados total y neto

 El grado total (o simplemente grado) de un vértice v es

la suma entre el número de arcos que parten de v y el
número de arcos que llegan a v.
g(v) = g+(v) + g–(v)

 El grado neto de un vértice v es la diferencia entre el

número de arcos que parten de v y el número de arcos que
llegan a v.
gn(v) = g+(v) – g–(v)

10
Matemática Discreta
Digrafos y grafos

Relaciones entre grados y arcos

 (v) 
g 
 (v)  o(A)
g 

vV vV

 g (v)   (v) 
g 
 (v)  2 o(A)
g 

vV vV vV

 gn (v)   (v) 
g 
 (v)  0
g 

vV vV vV

11
Matemática Discreta
Digrafos y grafos

Otra terminología
 Cuando g(v) = 0 se dice que v es un vértice aislado de D.
 Cuando g(v) = 1, v se denomina vértice pendiente.
 Dos arcos (vi, vj) y (vk, ve) son estrictamente paralelos
cuando vi = vk y vj = ve, es decir, coinciden sus respectivos
vértices iniciales y finales.

 Se denomina multidigrafo al digrafo que contiene arcos

estrictamente paralelos (no triviales).

 Dos arcos (vi, vj) y (vk, ve) son paralelos opuestos si vi = ve

y vj = vk, es decir el origen de uno es extremo final del otro.12
Matemática Discreta
Digrafos y grafos

Otra terminología
 Un rizo o bucle es un arco cuyo vértice inicial y final
coinciden.
 Un camino es una sucesión de arcos de tal manera que
el nodo terminal de cada arco del camino es el nodo inicial
del próximo arco del camino, si lo hubiera. Un sólo vértice
es un camino.
 La longitud de un camino  es el número de arcos que lo
componen y la indicamos con l().
 Un circuito es un camino cerrado, donde el vértice
inicial coincide con el vértice final.
13
Matemática Discreta
Digrafos y grafos

Otra terminología

 Digrafo parcial (suprime arcos)

 Subdigrafo (suprime nodos)
 Subdigrafo parcial (suprime arcos y nodos)

14
Matemática Discreta
Digrafos y grafos

Matriz de adyacencia

Definición:
Sea D = (V, A, ) un digrafo donde los nodos están
ordenados desde v1 hasta vn. Se define una matriz
M = (pij) de tamaño nxn donde pij representa el número
de arcos que van desde vi hasta vj,  i, j: 1, ...., n. Si no
existen arcos desde vi hasta vj entonces pij = 0. La matriz
cuadrada M = (pij) se denomina matriz asociada al
digrafo o matriz de adyacencia de vértices.

15
Matemática Discreta
Digrafos y grafos

Potencias de la matriz de adyacencia

Sea D = (V, A, ) un digrafo de n vértices y M su matriz

asociada. Cada elemento qij de la matriz Mp = M  M  …
 M (p veces) es igual al número de caminos distintos de
longitud p que van de vi a vj.

Ejemplo: ¿Cuántos caminos de longitud 2 hay de v1 a v3

sobre el digrafo D?
1 0 1 0
 
1 1 0 1
M(D) = 
0 0 1 0
 
0 0 0 1 
 16
Matemática Discreta
Digrafos y grafos

Propiedades de los digrafos

Sea D = (V, A, ) un digrafo donde los nodos están ordenados

desde v1 hasta vn y sea M = (pij) su matriz asociada. Cada
elemento qij de la matriz M2 se representa con el número de
caminos distintos de longitud 2 que van de vi a vj.
Se verifica que:
D es reflexivo  I  M
D es simétrico  M = Mt
D es transitivo   1  i  n, 1  j  n, si qij  0 entonces pij  0.
D es antisimétrico   1  i  n, 1  j  n, i  j, si pij  0
entonces pji = 0.
17
Matemática Discreta
Digrafos y grafos

Propiedades de los digrafos

Ejemplo: El siguiente digrafo es reflexivo y antisimétrico

v1 v2 1 0 1 0
 
M(D) = 
1 1 0 1
0 0 1 0
D  
0 0 0 1 
v3 v4 

18
Matemática Discreta
Digrafos y grafos

Grafos
Definición:
Llamaremos grafo o grafo no dirigido a una terna G = (V,
A, ) donde V es el conjunto de vértices o nodos de G, A
denota el conjunto de aristas o lados y  es una función
de incidencia no dirigida que asocia a cada elemento de A
un par no ordenado de elementos de V, es decir que a
cada elemento de A le queda asociado un subconjunto de
dos elementos (que pueden ser iguales) de V.

19
Matemática Discreta
Digrafos y grafos

Grafos
Ejemplo de grafo G = (V, A,  ):
V = {v1, v2, v3, v4, v5} , A = {ai, i  N, 1  i  6}.
La función de incidencia : A  V  V está definida por:
(a1) = {v1, v2} = (a2); (a3) = {v2, v2} = {v2};
(a4) = {v2, v3}; (a5) = {v2, v4}; (a6) = {v3, v1}

20
Matemática Discreta
Digrafos y grafos

Grafos – Nueva terminología

 vértices o nodos
 aristas o lado
 nodos adyacentes
 aristas adyacentes
 aristas paralelas
 incidencia
 lazos
 grado o valencia de un nodo
 nodos aislados y pendientes
 cadenas, longitud de una cadena, ciclo 21
Matemática Discreta
Digrafos y grafos

Grafos – Nueva terminología

 La suma de los grados de todos los nodos es el doble
del número de aristas.
 g (v)  2 o(A)
vV

 Matriz de adyacencia: es una matriz simétrica

(Observar la suma de las filas o de las columnas y
grados!!).
 Grafos conexos: Un grafo es conexo si para todo par
de vértices existe al menos una cadena que los une. Se
considera que existe una cadena de longitud cero que
une todo vértice consigo mismo. 22
Matemática Discreta
Digrafos y grafos

Problemas

• Si o(V) = n ¿Cuál es el mínimo número de aristas del

grafo para que sea conexo?
• Demostrar que en todo grafo existe un número par de
vértices de grado impar.
• En un grafo los vértices tienen respectivamente grados:
2, 2, 3, 6, 2, 3, 4, 4, 4, 2. ¿Cuántas aristas tiene el grafo?
• Determina o(V) para un grafo G de 22 aristas que tiene
todos los vértices de grado 5, excepto los catorce
vértices pendientes.

23
Matemática Discreta