Programacion

Relaciones binarias y grafos
305
__________________________________________________________________________________

Capítulo 6 Relaciones binarias y grafos

En este capítulo nos centraremos en el modelo de las relaciones binarias1 entre elementos
de dos dominios A y B, donde un elemento de A está relacionado con un elemento de B si
se cumple el enunciado de la relación. Generalmente, un elementode A estará relacionado
con varios de B y viceversa; por ello, en algunos textos informáticos las relaciones binarias se
denominan relaciones m:n como abreviatura de: m elementos de A se relacionan con n de
B y viceversa.
Un ejemplo de aplicación de las relaciones binarias podría ser la gestión de la matriculación
de alumnos en una universidad. La estructura necesaria se puede considerar comouna
relación entre dos conjuntos de elementos: los alumnos y las asignaturas, por la que cada
alumno está relacionado con todas las asignaturas que cursa y cada asignatura con todos los
alumnos que se han matriculado de la misma.

Abad
Abadía
Aguilar
...

IP
x

IC
x
x

Alg
x

Fis
x
x

PM
x
x

ILo EDA
x
x

x

Fig. 6.1: representación de la relación alumnos-asignaturas
(la cruz significa que el alumnocursa la asignatura).

Dado el contexto de uso esperado, las operaciones sobre el tipo que parecen adecuadas
son: matricular un alumno de una asignatura, desmatricularlo (cuando la ha aprobado),
averiguar si un alumno cursa una asignatura concreta, y listar las asignaturas que cursa un
alumno y los alumnos que cursan una asignatura. Extrapolando estas operaciones a un
marco general, podemosformular una especificación para las relaciones y deducir
implementaciones eficientes. Concretamente, en la primera sección estudiaremos la
1

Si bien nos podríamos plantear el estudio de relaciones sobre un número arbitrario de dominios, el
caso habitual es el binario y por eso nos limitamos a éste.

© Los autores, 1998; © Edicions UPC, 1998.

3
06
Estructuras de datos. Especificación, diseño eimplementación
__________________________________________________________________________________

especificación y la implementación de las relaciones binarias en general, mientras que en el
resto del capítulo nos centraremos en el caso particular de relaciones binarias sobre un único
dominio, denominadas grafos. Sobre los grafos se definen varios algoritmos de gran interés,
cuya resolución seráampliamente comentada y en cuya implementación intervendrán
diversos TAD ya conocidos, como las colas prioritarias y las relaciones de equivalencia.

6.1 Relaciones binarias
Se quiere especificar el TAD de las relaciones binarias R AxB definidas sobre dos dominios
de datos A y B, tal que todo valor R del TAD, R ∈R AxB , es un conjunto de pares ordenados
, a ∈A y b ∈B. Dados R ∈R AxB , a ∈A y b ∈B,la signatura del tipo es:
- Crear la relación vacía: crea, devuelve Ø.
- Añadir un par a la relación: inserta(R, a, b), devuelve R ∪ {}.
- Borrar un par de la relación: borra(R, a, b), devuelve R - {}.
- Mirar si un par de elementos están relacionados: existe?(R, a, b), averigua si ∈R.
- Dos operaciones para determinar el conjunto recorrible 2 de elementos (v. fig. 4.27) queestán relacionados con uno dado: fila(R, a), devuelve el conjunto s ∈P (B), definido
como b ∈s ⇔ ∈R, y columna(R, b), que se define simétricamente.
Alternativamente, se podría considerar la relación como una función de pares de elementos
en el álgebra booleana B de valores cierto y falso, f : A x B → B , en la que f(a, b) vale cierto si
a y b están relacionados. Este modelo se adoptará en elcaso de relaciones binarias
valoradas, que se introduce más adelante.
En la figura 6.2 se presenta una especificación para las relaciones. Notemos que aparecen
diferentes parámetros formales. Por un lado, los géneros sobre los cuales se define la
relación así como sus operaciones de igualdad, imprescindibles en la especificación. Por
otro lado, y para establecer un criterio de ordenación de los...

Leer documento completo

Regístrate para leer el documento completo.