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 devecindad 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 procesoindustrial, 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: Elorden no importa, 〈i, j〉 ≡ 〈j, i〉 . 〈i, j〉 ∈ A ⇔ 〈j, i〉 ∈ A.
Ejemplos de grafos y su representación:

7

7

4

4
5

2

5
2

3

3

6

6

1

1

Fig. 1: Grafo no dirigido

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 elsignificado 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:

⎧0
⎪
long (i, j ) = ⎨∞
⎪coste( i, j
⎩

si i = j

)

si i, j ∉ Α
si i, j ∈ Α

Para un grafo que no seauna 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 figura1 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 gradointerior 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:...