Informatika

ESTRUCTURAS DE DATOS

GRAFOS 173

TEMA 5

Grafos.
5.1. DEFINICIÓN DE GRAFO
A menudo, cuando se observa la red de rutas aéreas de un país interesa observar cómo ir de una ciudad a otra por las rutas posibles. En consecuencia, se tiene dos conjuntos de objetos distintos: ciudades y rutas. La Figura 5.1 muestra una manera de representar la relación existente entre las ciudades y las rutas,así como la distancia entre las distintas ciudades.

BILBAO OVIEDO 445 395 MADRID 531 SEVILLA 207 MELILLA

606 622 437

BARCELONA 538 ALICANTE 534 1006

221

MALAGA

Figura 5.1. Representación de las conexiones entre ciudades.

174 GRAFOS

ESTRUCTURAS DE DATOS

En general, un grafo es una manera de representar relaciones que existen entre pares de objetos. Así, un grafo es unconjunto de objetos, llamados vértices1, y relaciones entre objetos que establecen una relación entre pares de vértices, representadas por aristas. En el ejemplo anterior, el grafo de la Figura 5.1 representa las conexiones aéreas entre ciudades. Los vértices representarían las ciudades. Las aristas representan las conexiones entre ciudades y, en este caso, se almacenan la distancia en kilómetrosentre las ciudades que une. Definición 1. Un grafo se define como un par G = (V, A), donde V es un conjunto finito no vacío de vértices y A es un conjunto de pares de vértices de V, es decir, las aristas. Definición 2. Un grafo G se define como un par ordenado, G = (V, A), donde V es un conjunto finito y A es un conjunto que consta de dos elementos de V.

1

La terminología de la teoría de grafosno es estándar. El concepto de vértice también se referencia como nodo. Asimismo, aristas (edges en inglés) y arcos denotan el mismo elemento. En algunos libros, sin embargo, se establece una diferencia entre aristas (unen vértices en un grafo no dirigido) y arcos (unen vértices en grafos dirigidos). En este capítulo, se dará preferencia a los términos vértice y arista.

ESTRUCTURAS DE DATOSGRAFOS 175

5.2. TERMINOLOGÍA Y CONCEPTOS
5.2.1. Grafos dirigidos y no dirigidos Dependiendo del tipo de relación entre los vértices del grafo, se definen distintos tipos de grafos. Así se distinguen aristas dirigidas y no dirigidas: Arista dirigida: es aquella que define un par ordenado de vértices (u,v), donde el primer vértice u es el origen de la arista y el segundo vértice v es eltérmino (o vértice final). El par (u, v) ≠ (v, u). Arista no dirigida: es aquella que define un par no ordenado de vértices (u, v), donde (u, v) = (v, u). De esta forma se distinguen entre grafos dirigidos y grafos no dirigidos. Grafo dirigido: Es aquel cuyas aristas son dirigidas. Los grafos dirigidos suelen representar relaciones asimétricas como por ejemplo: relaciones de herencia, los vuelos entreciudades, etc. Grafo no dirigido: Es aquel cuyas aristas son no dirigidas. Representan relaciones simétricas como relaciones de hermandad y colaboración, conexiones de transportes, etc. 5.2.2. Incidencia, adyacencia y grado de un vértice

Sea un grafo G = (V, A), los vértices u y v pertenecientes a V; y una arista (u,v) perteneciente a A, se dice que: Incidencia: la arista (u,v) es incidente conlos vértices u y con v. Adyacencia: Dos vértices u y v son adyacentes si existe una arista cuyos vértices sean u y v: o El vértice u es adyacente a v o El vértice v es adyacente desde u Grado: El grado de un vértice u es el número de vértices adyacentes a u. Para un grafo dirigido, el grado de salida de un vértice u es el número de vértices adyacentes desde u, mientras que el grado de entrada de unvértice u es el número de vértices adyacentes a u. La Figura 5.2 muestra los grados de los vértices para un grafo no dirigido y un grafo dirigido.

176 GRAFOS

ESTRUCTURAS DE DATOS

Grafo no dirigido:

Grafo dirigido:

a

b e

a

b e

c

d

c

d

Grado (a) = 3 Grado (b) = 3 Grado (c) = 2 Grado (d) = 4 Grado (e) = 4

GradoE (a) = 2 GradoE (b) = 3 GradoE (c) = 0...