5.1.3 Representaciones de Relaciones

Representación De Relaciones Usando Matrices 

Un método para el estudio de las relaciones de manera algorítmica es utilizando matrices compuestas de ceros y unos.

 Sean A y B conjuntos finitos de la forma: 

Si R es una relación de A en B. La relación R puede ser representada por la matrizdonde:

La matriz MR se denomina matriz de R. En otras palabras la matriz, de ceros y unos, de R tiene un 1 en la posición  (i,j) cuando  ai está relacionado con bj y un 1 en está posición ai si  no está relacionado con bj.

Obsérvese en la definición anterior que los elementos de A y B han sido escritos en un orden particular pero arbitrario. Por lo tanto, la matriz que representa una relación.

Conjuntos

Un conjunto es una colección de objetos considerada como un objeto en sí. Los objetos de la colección pueden ser cualquier cosa: personas, números, colores, letras, figuras, etc. Cada uno de los objetos en la colección es un elemento o miembro del conjunto. Por ejemplo, el conjunto de los colores del arcoíris es:

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta}

Un conjunto suele definirse mediante una propiedad que todos sus elementos comparten. Por ejemplo, para los números naturales, si consideramos la propiedad de ser un número primo, el conjunto de los números primos es:

P = {2, 3, 5, 7, 11, 13, …}

Un conjunto queda definido únicamente por sus miembros y por nada más. En particular el orden en el que se representen estos es irrelevante. Además, cada elemento puede aparecer de manera idéntica una sola vez, esto es, no puede haber elementos totalmente idénticos repetidos. Por ejemplo:

S = {Lunes, Martes, Miércoles, Jueves, Viernes} = {Martes, Viernes, Jueves, Lunes, Miércoles}

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta} = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta, Naranja}

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binaria entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Un grafo G es un par ordenado G = (V,E), donde:

· V es un conjunto de vértices o nodos, y

· E es un conjunto de aristas o arcos, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.

Se llama orden del grafo G a su número de vértices, | V | .

El grado de un vértice o nodo V es igual al número de arcos E que se encuentran en él.

Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Diagrama de flechas

Hay otra manera de visualizar una relación y es a través de una representación gráfica, donde se destaquen los puntos en el plano que pertenecen a A y los puntos que pertenecen a B. Se trazan flechas que indican la relación que existe entre cada elemento del conjunto  A y su correspondiente en el conjunto B. A esta representación gráfica se le conoce como un diagrama de flechas.