Publicado el 18 de Junio del 2018
752 visualizaciones desde el 18 de Junio del 2018
706,9 KB
23 paginas
Creado hace 13a (02/02/2011)
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.
OVIEDO
BILBAO
445
395
MADRID
531
606
622
437
BARCELONA
538
ALICANTE
1006
SEVILLA
207
534
MELILLA
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 un conjunto 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ómetros entre 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 grafos no 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 DATOS
GRAFOS 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 el té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 entre ciudades, 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 con los 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 un vé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:
a
c
b
d
e
Grado (a) = 3
Grado (b) = 3
Grado (c) = 2
Grado (d) = 4
Grado (e) = 4
Grafo dirigido:
a
c
b
d
e
GradoE (a) = 2
GradoE (b) = 3
GradoE (c) = 0
GradoE (d) = 2
GradoE (e) = 1
GradoS (a) = 1
GradoS (b) = 0
GradoS (c) = 2
GradoS (d) = 2
GradoS (e) = 3
Figura 5.2. Grado de los vértices en un grafo no dirigido y dirigido.
5.2.3. Grafos simples y multigrafos
Un grafo simple es aquel que no tiene aristas paralelas o múltiples que unan el mismo
par de vértices. Un grafo que cuente con múltiples aristas entre dos vértices se denomina
multigrafo. La Figura 5.3 muestra un ejemplo de grafo simple y de multigrafo, donde
existen aristas paralelas incidentes a los vértices a y d, y e y d. En este caso, se dice que el
grafo tiene multiplicidad 2 (máximo de aristas paralelas entre dos vértices).
GRAFO SIMPLE:
MULTIGRAFO:
a
c
b
d
e
a
b
d
e
Figura 5.3. Grafo simple y grafo no simple
Si asumimos un grafo simple, se observan las siguientes propiedades:
Si G es un grafo no dirigido con m vértices, entonces
grado(v) = 2m.
Σ
v en G
Una arista (u, v) se cuenta dos veces en este sumatorio, uno
como vértice final u y otro como vértice final v. Entonces,
la contribución total de las aristas a los grados de los
vértices es dos veces el número de las aristas.
ESTRUCTURAS DE DATOS
GRAFOS 177
Si G es un grafo dirigido con m vértices, entonces:
grado E(v) =
grado S(v) = m
Σ
v en G
Σ
v en G
En un grafo dirigido, una arista (u,v) contribuye una unidad al grado de
salida de su origen u y una unidad al grado de entrada de su vértice final v.
Por tanto, la contribución total de las aristas al grado de salida de los
vértices es igual al número de aristas, y similar para los grados de salida.
Sea G un grafo simple con n vértices y m aristas, entonces:
Un arco (u,v) se cuenta dos veces en este sumatorio, uno como ENDPOINT
u y otro como ENDPOINT V. Entonces, la contribución total de los arcos a
los grados de los vértices es dos veces el número de los arcos.
o Si G es no dirigido: m ≤ n(n-1)/2.
o Si G es dirigido: m ≤ n(n-1).
5.2.4. Camino, bucle y ciclo
Un camino es una secuencia que alterna vértices y aristas que comienza por un
vértice y termina en vértice tal que cada arista es incidente a su vértice predecesor y
sucesor. Es decir, un camino es un sucesión de vértices de vi V: <v0, v1, v2, … vk> que
cumple que:
∊
(vi,,vi+1) ∊ A ∀ i ∊ {0 … k-1}.
Se dice que este camino tiene longitud k. Es decir, el número de aristas de un camino o
ciclo es la longitud del camino.
Un camino es simple si cada vértice en el camino es distinto, excepto posiblemente
por el primero y el último vértice. Un camino simple cumple la siguiente restricción:
vi ≠ vj ∀ i ∊ {0…k}, j ∊ {1…k-1}, i≠j
Para todo vértice x, existe el camino simple <x>, que sería el camino de longitud 0.
Un bucle es un camino de longitud 1 que comienza y termina en el mismo vértice:
<xi, xi>.
Un ciclo es un camino simple <v0, … vk> que cumple las siguientes restricciones:
v0= vk
Si es no dirigido, k = 1 (es un bucle) o k ≥ 3.
La Figura 5.4 ilustra estos conceptos para un grafo no dirigido y un grafo dirigido.
178 GRAFOS
ESTRUCTURAS DE DATOS
GRAFO NO DIRIGIDO:
a
c
b
d
e
GRAFO DIRIGIDO:
a
c
b
d
e
<a,b,e,d,c>: camino simple de longitud 4.
<a,c,d,a,b,e>: camino de longitud 5.
<a,e>: no es un camino.
<e,e>: camino, bucle y ciclo
5.2.5. Grafos conexos
Figura 5.4. Caminos, bucles y ciclos en un grafo dirigido y no dirigido.
<a,b>: camino simple de longitud 1.
<e,d,a,b>: camino de longitud 3.
<a,c,d>: no es un camino.
<e,e>: camino, bucle y ciclo
Sea G = (V, A) un grafo no dirigido, se le denomina conexo si existe un camino
entre dos vértices cualesquiera de G. Para un grafo dirigido G, su grafo asociado no
dirigido es aquel que se obtiene ignorando la dirección de las aristas. G se considera conexo
si su grafo asociado es conexo. La Figura 5.5 muestra ejemplos de grafos conexos y no
conexos.
GRAFO 1: NO DIRIGIDO CONEXO
GRAFO 2: DIRIGIDO CONEXO
a
c
b
d
e
a
c
b
d
e
GRAFO 3: NO DIRIGIDO NO CONEXO
a
c
b
d
e
GRAFO 4: DIRIGIDO NO CONEXO
a
c
b
d
e
Figura 5.5. Ejemplos de grafos conexos y no conexos
ESTRUCTURAS DE DATOS
GRAFOS 179
5.2.6. Grafos valorados y grafos etiquetados2
Un grafo valorado (o ponderado) es una terna <V, A, f> donde <V, A> es un grafo y
f es una función cualquiera, denominada función de coste, que asocia un valor o peso a
cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos
de todas las aristas atravesadas. En un grafo etiquetado, la función f tiene como imagen un
conjunto de etiquetas no numéricas.
GRAFO VALORADO
GRAFO ETIQUETADO
Museo Municipal
diseñado-por
a
3.6
c
1
b
0.5 2
2
d
2
2.8
e
5
estilo
está-en
Pedro de Ribera
churrigueresco
estilo
nacido-en
Madrid
Plaza Mayor
está-en
Salamanca
Figura 5.6. Grafo valorado y grafo etiquetado
2 En este curso no se van a tratar los grafos valorados ni etiquetados.
180 GRAFOS
ESTRUCTURAS DE DATOS
5.3. IMPLEMENTACIONES DE GRAFOS
Los dos tipos de implementación más frecuentes (independientemente del lenguaje de
programación) para la representació
Comentarios de: Tema 5 - Grafos - Estructuras de datos (0)
No hay comentarios