PDF de programación - Apuntes de Grafos

I.T. INFORMÁTICA DE GESTIÓN, CURSO 2005/06



ESTRUCTURAS DE DATOS



Apuntes de Grafos

Un grafo es una entidad matemática introducida por Euler en 1736 para representar entidades (vértices)
que pueden relacionarse libremente entre sí, mediante el concepto de arista. Se puede definir un TAD
Grafo basado en estas ideas, el cual contiene elementos sobre los que esta definida una relación de
vecindad o adyacencia. Un vértice puede relacionarse con cualquier otro vértice y establecer cualquier
número de relaciones.
Hay muchas situaciones en las cuales el modelado más conveniente de los datos de una aplicación es
mediante grafos, por ejemplo la representación de una red de carreteras, calles, telecomunicaciones,
electrificación, internet, planificación de tareas, etapas de un proceso industrial, etc.

1. Definiciones

Un grafo G = (V, A) se define por:

• Un conjunto de n vértices, V, a los cuales se hace referencia por sus índices 1…n.
• Un conjunto de m aristas, A, que conectan vértices entre sí. Una arista es un par de vértices,

indicados de la forma 〈i, j〉. Si 〈i, j〉 ∈ A significa que el vértice i está conectado con el vértice j.

• No existen aristas de la forma 〈i, i〉 (que conecten un vértice consigo mismo).
Un subgrafo de G es cualquier grafo G’ = (V, A’) donde A’ sea un subconjunto de A
Dependiendo de si el orden de los vértices en las aristas importa o no tenemos:

• Grafo dirigido: El orden importa, 〈i, j〉 ≠ 〈j, i〉. El que el vértice i esté conectado con el vértice j no

implica que el vértice j esté conectado con el vértice i.

• Grafo no dirigido: El orden no importa, 〈i, j〉 ≡ 〈j, i〉 . 〈i, j〉 ∈ A ⇔ 〈j, i〉 ∈ A.

Ejemplos de grafos y su representación:


4

2

3

1

Fig. 1: Grafo no dirigido

7



5

6



7



5

6

4

2

3

1

Fig.2: Grafo dirigido


El grafo de la figura 1 se define por: V = [1..7], A = { 〈1,2〉 , 〈1,3〉 , 〈2,1〉 , 〈2,3〉 , 〈2,4〉 , 〈3,1〉 , 〈3,2〉 , 〈3,4〉 ,
〈3,5〉 , 〈4,2〉 , 〈4,3〉 , 〈5,3〉 , 〈5,6〉 , 〈5,7〉 , 〈6,5〉 , 〈7,5〉 }.
El grafo de la figura 2 se define por: V = [1..7], A = { 〈1,3〉 , 〈2,3〉 , 〈2,4〉 , 〈3,2〉 , 〈3,5〉 , 〈5,6〉 , 〈5,7〉 }.

PÁG. 1 de 10



I.T. INFORMÁTICA DE GESTIÓN, CURSO 2005/06
ESTRUCTURAS DE DATOS
En muchas aplicaciones de los grafos las aristas llevan asociada información adicional. En ese caso
hablaremos de grafos etiquetados. Si esa información es numérica y tiene el significado del coste
necesario para recorrer esa arista, entonces usaremos el nombre de grafo ponderado o red.
Red: Grafo en el que cada arista lleva asociado un coste (de aquí en adelante lo llamaremos longitud)
Definiremos la función longitud entre los vértices i y j de una red como:

long

j
i
),(

=

0
⎧
⎪
∞
⎨
⎪
coste
⎩

(

i

,

j

)

j

i
si
si
si

=
i
,
i
,

j
j



Α∉
Α∈

Para un grafo que no sea una red se supone que todas las aristas tienen coste unidad.

2. Terminología

• Dos vértices i y j son adyacentes si existe una arista que los conecte (es decir, si 〈i, j〉 ∈ A)
• El grado de un vértice en un grafo no dirigido es igual al número de vértices adyacentes a él
(número de aristas donde el vértice aparece como el primer o segundo componente de la arista). Por
ejemplo, en la figura 1 el vértice 1 tiene grado 2, y el vértice 3 tiene grado 4.

• En un grafo dirigido se distingue entre grado interior de un vértice (número de aristas que llegan a
él, es decir aristas donde el vértice aparece como segundo componente) y grado exterior (número
de aristas que salen de él, aristas donde el vértice aparece como primer componente). Por ejemplo
en la figura 2 el vértice 1 tiene grado interior 0 y grado exterior 1, y el vértice 3 tiene grado interior
2 y grado exterior 2.

• Un camino entre dos vértices i y j es cualquier secuencia de vértices, v1 , … , vk , … , vp que cumpla

que v1 = i, vp = j y exista una arista entre cada par de vértices contiguos: ∀ k : 〈vk , vk +1〉 ∈ A
• Por ejemplo, en la figura 1, los siguientes serían caminos posibles entre los vértices 1 y 5:

1,3,5
1,3,4,2,3,5
1,3,4,2,3,4,2,3,5

• Un camino simple es aquel donde no hay vértices repetidos en la secuencia, salvo el primero y el
último (que pueden ser iguales o distintos). Un ciclo es un camino simple donde el vértice inicial y
el final son el mismo (i = j). Por ejemplo, 1,3,5 sería un camino simple, 1,3,2,1 también (y además
un ciclo), pero 1,3,4,2,3,5 no es camino simple.

• Un grafo se dice que es acíclico si todos sus posibles caminos son simples (no existen ciclos). Por
ejemplo el grafo de la figura 1 sería acíclico si eliminásemos los vértices 〈1,2〉 y 〈2,4〉 (se entiende
que automáticamente desaparecen 〈2,1〉 y 〈4,2〉).

• Un árbol es un grafo no dirigido y acíclico.
• Se dice que un grafo está conectado si existe como mínimo un camino entre cualquier par de
vértices distintos. Por ejemplo, el grafo de la figura 1 está conectado, pero el de la figura 2 no (no
hay camino que vaya de 3 a 1, etc.)

• Un grafo esta completamente conectado si para cada vértice existen aristas que lo conecten con los
n-1 vértices restantes. Este tipo de grafo tiene el número máximo posible de aristas, n·(n-1)/2. Por lo
tanto m ∈ O(n2)

• Si un grafo contiene ciclos, el número de posibles caminos es infinito. Si queremos enumerar el
número de posibles caminos simples, el peor caso es un grafo completamente conectado, y entonces
el número de posibles caminos simples es de n!

PÁG. 2 de 10

I.T. INFORMÁTICA DE GESTIÓN, CURSO 2005/06



ESTRUCTURAS DE DATOS

• Se define longitud/coste de un camino como suma de las longitudes de las aristas que recorre el
camino (recordar que en un grafo que no sea red las aristas tienen longitud unidad). En la figura 1 la
longitud del camino 1,3,5 sería 2.

• Se puede definir entonces la longitud de un camino por medio de la función longitud entre dos
vértices, definida anteriormente: (no confundir ambas funciones, aunque tengan el mismo nombre
sus parámetros son distintos)

(

[
v
1

long K

,

]

)

=

,

v

p

p
1
−
∑
long
k
1
=

(
kk
,

)
1



+

• Para un grafo conectado, se define ruta optima entre los vértices i y j como el camino de longitud

mínima entre los vértices i y j.

• Se denominará distancia entre los vértices i y j a la longitud de su ruta óptima.

3. Representaciones de grafos

Aunque en general al representar datos de la vida real mediante un grafo los vértices suelen llevar
asociada información, en lo que sigue supondremos que esa información se almacena en una lista
indexada y por lo tanto podemos hacer referencia a los vértices utilizando únicamente el índice donde
están almacenados en esa lista. En lo que sigue las representaciones hacen referencia únicamente a la
manera de almacenar las aristas.
Las operaciones básicas sobre grafos son las de comprobación de existencia de arista entre dos vértices (o
conocer su longitud, si el grafo es etiquetado), recorrer la lista de vértices adyacentes a uno dado, la
inserción y borrado de una arista, y la inserción y borrado (junto con las aristas asociadas) de un vértice.
En muchas aplicaciones, sin embargo, el conjunto de vértices no varía durante la ejecución.
Las dos representaciones principales de grafos son las siguientes:

• Matriz de Adyacencia (MA): Se utiliza una matriz de tamaño n × n donde las filas y las columnas
hacen referencia a los vértices para almacenar en cada casilla la longitud entre cada par de vértices
del grafo. La celda MA[i, j] almacena la longitud entre el vértice i y el vértice j. Si su valor es
infinito significa que no existe arista entre esos vértices, y MA[i, i] = 0.

• Lista de Adyacencia (LA): Se utiliza un vector de tamaño n (un elemento por cada vértice) donde
LA[i] almacena la referencia a una lista de los vértices adyacentes a i. En una red esta lista
almacenará también la longitud de la arista que va desde i al vértice adyacente.
Existen varias posibilidades a la hora de representar la lista de vértices: arrays dinámicos, listas
enlazadas o usar una lista de adyacencia aplanada: Se almacenan todas las listas de manera
contigua en un único vector, VA, de tamaño m, y en el vector LA se almacenan índices al vector
VA. La lista de adyacencia del vértice i se encuentra en VA[LA[i] .. LA[i+1]-1]. Esta
representación es útil cuando no se vaya a modificar el grafo.

La eficiencia de las operaciones básicas en cada representación es la siguiente:


Operación

Matriz de Adyacencia Lista de Adyacencia

Espacio ocupado
Longitud entre vértices / Existencia de aristas
Recorrido vértices adyacentes a i
Recorrido todas las aristas
Inserción/borrado arista
Inserción/borrado vértice

Θ(n2)
O(1)
Θ(n)
Θ(n2)
O(1)
O(n2)

Θ(m+n)

O(grado(i))
Θ(grado(i))

Θ(m)

O(grado(i))

O(n)

PÁG. 3 de 10

I.T. INFORMÁTICA DE GESTIÓN, CURSO 2005/06

Ejemplo. Dado la siguiente red no dirigida, donde se indican la longitud/coste de cada arista:



ESTRUCTURAS DE DATOS

7

3

5

9

6

2

2

8

4

5

7

5

3

1

1



Representación mediante matriz de adyacencia:



v
é
r
t
i
c
e



5

6

vértice
3
7
4
1
2

1
1 ∞ ∞ ∞ ∞
0
8
2
2 ∞ ∞ ∞
5
8
0
3
7
0
5 ∞ ∞
1
5
4 ∞
7
0 ∞ ∞ ∞
2
5 ∞ ∞
9
3
5 ∞
6 ∞ ∞ ∞ ∞
0 ∞
7 ∞ ∞ ∞ ∞
0

0
9
3 ∞


Representación mediante listas de adyacencia: En las listas se almacenan pares (vértice adyacente,
longitud de arista).

v
é
r
t
i
c
e

1
2
3
4
5
6
7



(2,8)
(1,8)
(1,1)
(2,2)
(3,5)
(5,9)
(5,3)

(3,1)
(3,5)
(4,7)
(3,7)
(7,3)



(4,2)
(2,5)



(6,9)



(5,5)



Representación mediante listas de adyac