Aplicación de las relaciones en la computacion

Aplicación de las relaciones en la computacion
CONCEPTOS BASICOS DE RELACIONES.

PAREJA ORDENADA

Se dice que unapareja ordenada es un esquema en el que un elemento x de un conjunto esta relacionado con un elemento y de otro conjunto.

Una pareja ordenada así definida se escribirá de la siguiente manera: (x, y), donde x pertenece al primer conjunto e y pertenece al segundo conjunto.A•B
A = {a, b} B= {1, 2, 3}

R = {(a, 1); (a, 3); (b, 2); (b, 3)}

5.1.1 PRODUCTO CARTESIANO.

Es la relación entre los elementos de un conjunto con los otros elementos de otro conjunto. Como los polinomios.

Ejemplo:

A = {a, b}, B= {1, 2, 3}

A•B= {(a, 1); (a, 3); (b, 2); (b, 3)}

RELACION BINARIA.

Una relación binaria R de un conjunto X es un conjunto Y es un subconjunto delproducto cartesiano XxY si el par ordenado (x, y) pertenece a la relación escribimos que elemento “x” se relaciona con el elemento “y”. Decimos que “x” está relacionada con “y”. Si (x=y), decimos que la relación binaria sobre el conjunto X.
El conjunto {x € X | (x, y) € R´ y € Y} es el dominio de R el conjunto {y € Y | (x, y) € R´ x € X} 

Si una relación se indica mediante una tabla el dominio estáformado por los miembros de la primera columna y el rango formado por los miembros de la segunda columna.
X= {2, 3, 4}, Y= {3, 4, 5, 6, 7}R= {(x, y) | X divide a Y con residuo 0}

| 3 | 4 | 5 | 6 | 7 |
2 | | (2,4) | | (2,6) | |
3 | (3,3) | | | (3,6) | |
4 | | (4,4) | | | |
x | y |
2 | 4 |
2 | 6 |
3 | 3 |
3 | 6 |
4 | 4 |

REPRESENTACION DE RELACIONES.

Los ejemplos de relacionesque más se presentan en el área de la computación son aquellas que están definidas sobre conjuntos finitos. En esta sección se trataran dos formas de representar dichas relaciones y su uso para poder identificar las propiedades vistas en la sección anterior.

Representación de relaciones usando matrices
Un método para el estudio de las relaciones de manera algorítmica es utilizando matricescompuestas 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 matriz , donde

Representación de relaciones usando grafos.

Un grafo 
es el principal objeto de estudio de la teoría de grafos.
Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos,que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto depuntos (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.

Representación de relaciones usandodiagramas de flechas.

Una forma de representar el producto cartesiano es el diagrama de flechas.
Escriba los elementos de a  y  los elementos de b en dos discos disyuntos, y luego dibuje una flecha de ” a e a “  en ” b e b”  cada vez que a este relacionado con b.

PROPIEDADES DE LAS RELACIONES.

Una relación R en un conjunto A es reflexiva si (a, a) £ R para todas las a £ A, esto es, si a R epara todas las a e A. Una relación R en un conjunto A es irreflexiva si a R a para toda a £ A.

Por consiguiente, R es reflexiva si cada elemento a e A está relacionado consigo mismo y es irreflexiva si ningún elemento está relacionado consigo mismo. Ejemplo: (a) Sea Δ = [(a, a)\ a £ A], de modo que A es la relación de igualdad en el conjunto A. Entonces A es reflexiva, ya que (a, a) £ Δ paratodas las a e A.

Una relación R en un conjunto A es simétrica si cuando a R b, entonces b R a. De esto se sigue que R no es simétrica se tiene a y b € A con a R b, pero b R a. Unarelación R en un conjunto A es asimétrica si cuando a R b, entonces b Ra. De esto se sigue que R no es simétrica si se tiene a y b e A con ambos a R b y b R a.

Una relación R en un conjunto A es asimétrica si...