PDF de programación - Tema 5 - Grafos - Estructuras de datos

Imágen de pdf Tema 5 - Grafos - Estructuras de datos

Tema 5 - Grafos - Estructuras de datosgráfica de visualizaciones

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ó
  • Links de descarga
http://lwp-l.com/pdf11959

Comentarios de: Tema 5 - Grafos - Estructuras de datos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad