TEMA 2.

Análisis de problemas en redes de comunicaciones

2.1. Introducción a la teoría de grafos y redes. Conceptos básicos.
Representación matricial de un grafo. Conectividad. Redes.

2.2. Problemas de enrutamiento. Problema de la ruta más corta.

Algoritmos de Moore-Dijkstra y de Bellman-Ford. Aplicaciones a
protocolos de enrutamiento en una red.

2.3. Problemas de conexión. Conexión en árbol y en Steiner-árbol.

Algoritmo de Prim. Ejemplo: Diseño de una red digital de datos

2.4. Problemas de flujo (tráfico) en redes.

1/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. INTRODUCCIÓN A LA TEORÍA DE GRAFOS Y REDES:
La Teoría de Grafos comienza en 1736 cuando el matemático suizo Leonard Euler visita la
ciudad polaca de Koenigsberg.

A la gente de la ciudad le gustaba mucho pasear por las calles y los puentes de la misma. El
problema que se le planteó a Euler era saber si la gente podía, saliendo de un barrio cualquiera
de la ciudad, visitar todos los demás barrios pasando, como mucho una vez, por cada uno de
los siete puentes que atravesaban el río Pregel, y volviendo de nuevo al punto de partida.
Las autoridades pensaban que ello era imposible.
A
B
f g b b c
a
B f d C
D a
A g e
d e
D

C c Representación de los 7 puentes

de Königsberg
2/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. INTRODUCCIÓN A LA TEORÍA DE GRAFOS Y REDES (cont.):

Representación de una red de teléfonos en un barrio de una ciudad utilizando la

herramienta GUI (Windows Graphical User Interface).

¿Qué es un grafo?
De forma simple, un grafo representa las relaciones existentes entre los elementos de un
conjunto dado de objetos. Por su generalidad los problemas de grafos se plantean en campos
tan diversos como el diseño y análisis de redes de telecomunicaciones, la planificación de la
producción, la inteligencia artificial, el trazado de líneas férreas o la localización de servicios.
3/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. INTRODUCCIÓN A LA TEORÍA DE GRAFOS Y REDES (cont.2 y final):
VENTAJAS:
1. Se pueden expresar estructuras difíciles y profundas de un modo claro.
2. Desde un punto de vista práctico, un gráfico presenta una visión general del problema,
y esto es muy valioso para la intuición y razonamientos de cómo resolver el problema.

DESVENTAJAS:
No se puede tratar el problema de forma analítica, por tanto, siempre será necesaria una
representación formal del problema.

APLICACIONES

4/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. CONCEPTOS BÁSICOS:
Un GRAFO es un par G = (V, A), donde V es un conjunto de puntos (V = {1,
2, ..., n}), cuyos elementos se denominan VÉRTICES o NODOS, y A es un
conjunto de pares ordenados de nodos que denominamos ARCOS.

El ORDEN de un grafo G se define como el número de vértices de G.

Si a = (i, j) es un arco de un grafo G, entonces se dice que i es el NODO

INICIAL y j es el NODO FINAL. Un LAZO es un arco cuyos nodos inicial y
final coinciden.

Un p-GRAFO es un grafo con no más de p arcos entre cualesquiera dos vértices

del grafo.

2-grafo 1-grafo
5/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. CONCEPTOS BÁSICOS (cont.):

Un GRAFO DIRIGIDO es un grafo en el que los arcos tienen sentido de

recorrido. En este caso los arcos se representan con flechas. Un GRAFO NO
DIRIGIDO es un grafo en el que los arcos no tienen un sentido de recorrido
especificado (o bien se puede recorrer en ambos sentidos, o bien es irrelevante a
nivel conceptual). En este caso a los arcos se les denomina ARISTAS.

1 2 3 1 2 3

4 5 4 5

Grafo dirigido (1-grafo) Grafo no dirigido (2-grafo)

6/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. CONCEPTOS BÁSICOS (cont.2 y final):

Un grafo se dice SIMPLE si es 1-grafo y no contiene lazos. Un grafo G se dice

COMPLETO si para todo par de vértices existe un arco (arista) que los
conecta.
El SEMI-GRADO POSITIVO de un nodo i, g+(i), es el número de arcos que
tienen a i como nodo inicial. El SEMI-GRADO NEGATIVO de un nodo i, g(i),
es el número de arcos que tienen a i como nodo final. El GRADO de un nodo i,
g(i), es la suma de los semi-grados. En el caso de un grafo no dirigido sólo se
define el GRADO de un nodo i, g(i), como el número de aristas que parten de él.

1 2 3 1 2 3

4 5 4 5
g+(3) = 2, g(3) = 1, g(3) = 3 g(5) = 5
7/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. REPRESENTACIÓN MATRICIAL DE UN GRAFO:

Para estudiar un grafo será necesaria no sólo la representación gráfica del

mismo, sino que debemos expresarlo de forma que sea manejable desde un
punto de vista analítico. En este sentido, un grafo puede ser representado por una
MATRIZ. Distinguiremos dos tipos de representaciones matriciales de un grafo,
dependiendo de cómo se formen las entradas de la matriz:

A) MATRIZ DE INCIDENCIA (las entradas de la matriz indican si un nodo

forma parte o no de un arco/arista)

B) MATRIZ DE ADYACENCIA (las entradas de la matriz indican si existe un

arco/arista entre dos nodos)

La forma de llevar a cabo estas representaciones matriciales de un grafo

dependerán, en general, de si éste es dirigido o no dirigido.

8/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. REPRESENTACIÓN MATRICIAL DE UN GRAFO (cont.):
MATRIZ DE INCIDENCIA VÉRTICE-ARCO:
Dado un grafo dirigido G = (V, A), se define la matriz de incidencia vértice-arco
MI(G) de la siguiente forma:
M I (G )  mia  iV
aA

donde para cada arco a = (i, j) se tiene que mia= 1, mja= -1, mka= 0 k  i, j.
EJEMPLO:
1 a1 2
a 1 a 2 a 3,1 a 3,2 a 4 a 5 a 6
a6 a5 a2 1 1 0 0 0 0 1 1
a3 2 1 1 0 0 0 0 0
4 a4 3
M I (G ) 
3 0 1 1 1 1 0 0
1 a1 2
3' 0 0 1 1 0 0 0
a6 a5 a2 a3,1 4 0 0 0 0 1 1 1
4 a4 3 3’
a3,2
9/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. REPRESENTACIÓN MATRICIAL DE UN GRAFO (cont.2):
MATRIZ DE INCIDENCIA VÉRTICE-ARISTA:
Dado un grafo NO dirigido G = (V, A), se define la matriz de incidencia vértice-
arista MI(G) de la siguiente forma:
M I (G )  mia  iV
aA

donde para cada arista a = (i, j) se tiene que mia= mja= 1, mka= 0 k  i, j.

EJEMPLO:
a1 a2 a3 a4 a5 a6
1 a1 2 1 1 0 0 0 1 1
a6 a5 a2 M I (G )  2 1 1 0 0 0 0
a3 3 0 1 1 1 0 0
4 a4 3
4 0 0 0 1 1 1

10/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. REPRESENTACIÓN MATRICIAL DE UN GRAFO (cont.3 y final):
MATRIZ DE ADYACENCIA O VÉRTICE-VÉRTICE:
Dado un 1-grafo, con a lo sumo un lazo por vértice, G = (V, A), se define la
matriz de adyacencia MA(G) de la siguiente forma:
jV
M A (G )   mij 
iV
donde para cada arco a = (i, j) se tiene que mij= 1 sí, sólo si, (i, j)A, en otro caso
mij= 0.
1 a1 2 1 a1 2
EJEMPLO:
NOTA: En el caso a5 a2 a a a2
6 5
de un grafo no
dirigido se tiene que a3 a3
4 a4 3 4 a4 3
(i, j) = (j, i).
1 2 3 4 1 2 3 4
1 0 1 0 1 1 0 1 0 1
M A (G )  2 1 0 1 0 M A (G )  2 0 0 1 0
3 0 1 1 1 3 0 0 1 0
4 1 0 1 0 4 1 0 1 0
11/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. CONECTIVIDAD:
Una CADENA de longitud q es una secuencia de q arcos/aristas, {a1, a2, ..., aq},
tal que el arco/arista ar tiene un nodo en común con el arco/arista ar1 (ar  ar1) y
un segundo nodo en común con el arco/arista ar+1 (ar  ar+1). Al nodo de a1 que
no es adyacente a a2 y al nodo de aq que no es adyacente a aq1, se les denomina
los NODOS EXTREMOS de la cadena.

Un CICLO es una cadena cuyos nodos extremos coinciden.

Un CAMINO de longitud q es una secuencia de q arcos, {a1, a2, ..., aq}, con la
siguiente relación:
a1  (i0 , i1 ), a2  (i1 , i2 ), a3  (i2 , i3 ), , aq 1  (iq  2 , iq 1 ), aq  (iq 1 , iq )

El nodo i0 es denominado el NODO INICIAL del camino y el nodo iq es el

NODO FINAL del camino.

Un CIRCUITO es un camino en el que el nodo inicial y final coinciden.

12/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. CONECTIVIDAD (cont.):

1 a1 2
{a1, a2, a4} cadena de longitud 3
a6 a5 a2 {a6, a1, a2} camino de longitud 3
{a6, a1, a2, a4} ciclo
a3
4 a4 3 {a5, a6} circuito

DOS OBSERVACIONES:

a) Todo camino es una cadena, pero no toda cadena es un camino.

b) En grafos no dirigidos los conceptos de cadena y camino se solapan.

13/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. CONECTIVIDAD (cont.2):
Un grafo se dice CONECTADO o CONEXO si, para todo par de vértices i y j,
existe una cadena que los une. A cada subconjunto (maximal) de nodos del grafo
conectado o conexo se le denomina COMPONENTE CONEXA.

Un grafo se dice FUERTEMENTE CONECTADO o CONEXO si, para todo par

de vértices i y j, existe un camino que los une, con nodo inicial i y nodo final j. A
cada subconjunto (maximal) de nodos del grafo fuertemente conectado o conexo
se le denomina COMPONENTE FUERTEMENTE CONEXA.

¡En grafos no dirigidos los conceptos de conexo y fuertemente conexo

coinciden!

Un nodo se dice que es una ARTICULACIÓN o PUNTO DE RUPTURA del

grafo, si su eliminación produce un aumento en el número de componentes
(fuertemente) conexas.

Un ISTMO es una arista cuya omisión produce un aumento en el número de

componentes conexas.
14/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. CONECTIVIDAD (cont.3 y final):

Un grafo se dice k-ARISTA CONECTADO si no puede ser desconectado

suprimiendo menos de k aristas.

EJEMPLO:
1 3 Este grafo es conexo pero no es
5 fuertemente conexo.
6
Componentes fuertemente conexas:
G1 = {1, 2, 3, 4, 5}
2 4 G2 = {6, 7}
7
G3 = {8}

8 G1 G2 Articulaciones: {1, 2, 3, 4}
Grafo reducido G3 Istmos: {(1, 3), (3, 4), (4, 2)}

15/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. REDES:
Una RED es un grafo por el que circula algún tipo de flujo o hay algún tipo de
tráfico (mercancias, electricidad, información, vehículos, voz, datos, etc.).

La cantidad de flujo que circula desde un nodo i hacia un nodo j la denotaremos

por xij.

Se dice que un arco/arista está CAPACITADO si el flujo que puede circular por
él está acotado.

A los nodos desde los cuales fluye (se origina) el flujo se les denomina
FUENTES u ORÍGENES y los nodos donde muere o llega el flujo se les
denomina SUMIDEROS o DESTINOS.

En los nodos intermedios se debe cumplir el PRINCIPIO DE CONSERVACIÓN

DE KIRCHOFF, es decir, el flujo que entra en un nodo debe ser igual al flujo
que sale de él.

16/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. EJERCICIOS:
0 1 0 1 0 0 0 0
1. Dada la siguiente matriz de adyacencia, se pide:  
a) Hacer una representación gráfica de la red a la que 0 0 1 1 0 1 0 0
0 0 0 0 0 0 1 0
representa la matriz.  
1 0 0 0 0 0 1 0
b) Estudiar si el grafo es conexo o fuertemente conexo. A
0 0 1 0 0 1 0 1
c) Hallar las componentes fuertemente conexas.  
0 0 0 0 0 0 0 0
d) Determinar las articulaciones y los istmos.  
0 0 0 0 1 0 0 1
0 
0 1 0 0 1 0 0


2. Dado el siguiente grafo dirigido

Se pide:
a) Indicar el orden del grafo y el tipo de p-grafo que es.
b Calcular el semi-grado positivo, semi-grado negativo y el grado de cada uno de los
nodos.
c) Construir la matriz de incidencia y de adyacencia asociada al grafo.
d) Encontrar una cadena de longitud 4 y un circuito.
e) ¿Es este grafo conectado? ¿y fuertemente conectado? Encontrar todas las articulaciones
y todos los istmos. ¿Qué podemos concluir a la vista de los resultados obtenidos?
17/18
Tema 2. Análisis de problemas en redes de comunicaciones
2.1. EJERCICIOS (cont.):
3. Dado el siguiente grafo no dirigido

Se pide:
Ídem que en el ejercicio 2.

4. Dadas las siguientes matrices

 1  1 0 0 0 0 0 0 0 0 0 1 1 1 0 0
1 0 0 0 0 0 0   1 1 1 1  1 0 0 0 0 0 1 1 0 1 1 0
1 1 1 0 0 0 0   
  0 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1
0 1 0 1 1 0 0    
   0 0 0 0 1 0 1 1  1 0 1 1 1 0 1 0
0 0 1 1 0 1 1  0 0 0 0 0  1  1 0 0  1 0 1 0 1 0 1
0    
0 0 0 1 0 1  0 0 0 0 0 0 0  1 1 1 0 0 1 0 1 0

Se pide:
a) A qué tipo de matriz pueden corresponder ¿por qué?
b) Encontrar el grafo asociado, indicando si es posible la presencia de algún lazo.
18/18