5.3 Representación De Relaciones (Matrices, Conjunto, Grafos, Diagrama de flechas)

Los ejemplos de relaciones que 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.

                                                

REPRESENTACION 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 matriz  donde:

La matriz  se denomina matriz de R. En otras palabras la matriz, de ceros y unos, de R tiene un 1 en la posición  cuando  está relacionado con y un 1 en está posiciónsi  no está relacionado con .

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.

 depende de los órdenes usados para A y B. Cuando A = B usamos el mismo orden para A y B.

EJEMPLO:

Sean 

Consideremos la siguiente relación de  :

Entonces la matriz de R es

Recíprocamente, dando los conjuntos A y B con m y n elementos respectivamente, una matriz de m x n formada de ceros y unos determina una relación de A en B.

REPRESENTACION DE RELACIONES USANDO 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úmero 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}

Los conjuntos pueden ser finitos o infinitos. El conjunto de los número naturales es infinito, pero el conjunto de los planetas en el sistema solar es finito (tiene ocho elementos). Además, con los conjuntos pueden combinarse mediante operaciones, de manera similar a las operaciones con números.

Los conjuntos son un concepto básico, en el sentido de que no es posible definir los en términos de nociones más elementales, por lo que su estudio puede realizarse de manera informal, apelando a la intuición y a la lógica. Por otro lado, son el concepto fundamental de la matemática: mediante ellos puede formularse el resto de objetos matemáticos, como los números y las funciones, entre otros. Su estudio detallado requiere pues la introducción de axiomas y conduce a la teoría de conjunto.

REPRESENTACION DE RELACIONES USANDO 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 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.

EJEMPLO:

·         V:={1,2,3,4,5,6}

·         E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.

En las teorías de las categorías una categoría puede ser considerada como un multígrafo dirigido, con los objetos como vértices y los morfismos como aristas dirigidas.

REPRESENTACION DE RELACIONES USANDO DIAGRAMAS 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.

5.4 Propiedades De Las Relaciones (Reflexiva, Simétrica, Asimétricas y Transitivas, etc...)

RELACIONES REFLEXIVAS E IRREFLEXIVAS

Una relación R en un conjunto A es reflexiva si (a, a) £ R para todas las a £ A, esto es, si a R e para 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 1:

(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) £ Δ para todas las a e A.

(b) Sea R = {(a, b) e A x A | a + b}, R es la relación de desigualdad en el conjunto A. Entonces R es irreflexible, ya que (a, a) £ R para todas las x € A.

(c) Sean A = {1, 2, 3}. y Jí = {(1, 1), (1, 2)}. Entonces A es reflexiva ya

(2,2) R y (.3,3) € R. Por otra parte, R no es irreflexiva, ya que (1, l) € R.

(d) Sea A un conjunto no vacio. Sea R = Ǿ A x A, la relación vacía. Enlaces R no es reflexiva, ya que (a, a) € R para todas las a € A (el conjunto vacío tiene elementos). Sin embargo, R es irreflexiva.

Relaciones Simétricas y Asimétrica      

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. Una relació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 cuando a R b y b R a, entonces a = b. Otra forma de expresar esta definición es diciendo que R es anti simétrica si cuando a ≠ b, se tiene a R b o b R a. De esto se sigue que R no es anti simétrica si se tiene a y b en A. a ≠ b, y ambas a R b y b R a.

Ejemplo Sea A «= [a, b, c, d, e} y sea R la relación simétrica dada por

R = {(a, b), (b, a), (a, c), (c, a), (b, c), (c, b), (b, e), (e, b), (e, a), (a, e), (c,a), (a,c)}

El grafo dirigido de R se muestra en la figura 2(a), mientras que en la figura

Grafo dirigido de R Grafo dirigido de R

Aparece el grado de R. Obsérvese que cada arista no dirigida corresponde a dos pares ordenados en la relación R.

A una relación simétrica R en un conjunto A se le llamará conexa si existe una trayectoria de cualquier elemento de A a cualquier otro elemento de A. Esto significa sencillamente que el grafo de R está todo en una pieza. En la figura 3 se muestran los grafos de dos relaciones simétricas. El grafo de la figura 3(a) está conectado mientras que el de la figura 3(b) no lo está.

Relaciones  Transitivas

Se dice que una relación R en un conjunto A es transitiva si cuando a R b y b R e, entonces a R c. Se sigue que R no es transitiva si y sólo si se puede encontrar elemento a, b y c en A tal que a R b y b R c, pero a R c.

Ejemplo: Sea A = Z el conjunto de los enteros y sea R la relación considerada en el ejemplo 2 Para ver si R es transitiva, se supone que a R b y b R c. Por consiguiente, a < b; b < c. Entonces se sigue que a < c, por lo cual a R c. De aquí que R sea transitiva.

Una relación R en un conjunto A es transitiva si y sólo si satisface las siguientes propiedades: Si existe una trayectoria de longitud mayor que 1 del vértice a al vértice b, hay una trayectoria de extensión 1 de a a b (esto es, a está relacionada con b). Establecido algebraicamente, R es transitiva si y sólo si Rn £ R para todas las n ≥ 1.

Es posible caracterizar la relación transitiva por su matriz MR = [mij] así:

si mij =1 y mjk = 1, entonces mik = 1

Para ver qué significa transitividad en términos del grafo dirigido de una relación, se traducirá esta definición a términos geométricos.

Si se examinan los vértices particulares a y c, las condiciones a R b y b R c

ocurrirán si y sólo si existe una trayectoria de longitud 2 de a a c, esto es, si y sólo si a R2 c. Es posible replantear la definición de transitividad como sigue: Si a R2 c, entonces a R c, esto es, R2 £ R (como un subconjunto de A x A).

5.6 Relaciones De Equivalencia (Cerraduras, Clases De Equivalencia y Particiones)

Cerradura de una relación                  

Definición. Sea R una relación en un conjunto A. Una cerradura reflexiva ref( R ) de R en A es la “menor” relación que la incluye y que es reflexiva, con símbolos: (∀ R’ reflexiva) (A ⊆ R’ ⊆ ref( R )) ⇒ R’ = ref( R )) Una cerradura simétrica sim( R ) de R en A es la “menor” relación que la incluye y que es simétrica, con símbolos: (∀ R’ reflexiva) (A ⊆ R’ ⊆ ref( R )) ⇒ R’ = ref( R ))
Una cerradura transitiva trans( R ) de R en A es la “menor” relación que la incluye y que es transitiva, con símbolos: (∀ R’ reflexiva) (A ⊆ R’ ⊆ ref( R )) ⇒ R’ = ref( R )

La cerradura reflexiva y la cerradura simétrica de una relación es muy simple de encontrar, solamente se le agregan los pares necesarios de una forma directa. Cuando conocemos la matriz asociada a la relación, la forma de encontrar las cerraduras anteriores es muy simple.

Teorema: Sea R una relación en A y M_R su matriz asociada. La cerradura reflexiva y la cerradura simétrica de R son únicas y se pueden obtener mediante las matrices siguientes

M_ref(R) = M_R ∪ I_n, donde I_n es la matriz identidad de orden |A|.

M_sim(R) = [a _ij], donde a _ji = 1 si a _ij = 1 en M_R.

La Matriz identidad I_n de orden n es:

{$ {(1,…,0), (vdots, ddots, vdots), (0,…,1)] $}

O sea que para lograr la cerradura reflexiva debemos agregar 1′s en la diagonal, para la cerradura simétrica debemos agregar 1′s en luagres simétricos a la diagonal principal donde existan 1′s.

Cierre de equivalencia

Para calcular el cierre de equivalencia de una relación binaria R sobre un conjunto A:

Calcularemos primero su cierre reflexivo, ρ(R)

Sobre el resultado calcularemos el cierre simétrico, σ(ρ(R))

finalmente el cierre transitivo del resultado anterior, τ (σ(ρ(R)))

Clases de Equivalencia

Al conjunto de los elementos del conjunto A que están relacionados con él se llama clase de equivalencia. 

Ejemplo:

La relación a - b = 2.k (múltiplo de 2), siendo a y b números enteros es una relación de equivalencia porque cumple las propiedades: Reflexiva: a - a = 0 = 2.k (k = 0). Simétrica: a - b = b - a porque b - a  = -(a - b). Si a - b es múltiplo de 2, -(a - b) también lo será. Transitiva: a - b = 2.k1   b - c = 2.k2  Sumando queda a - c = 2.k3 Entonces a - c es múltiplo de 2. 

En el ejemplo anterior, la clase de equivalencia del número cero (uno de los elementos del conjunto de los números enteros)  C(0) = {... -4, -2, 0, 2, 4, ...}, pues 0 - (-4) es múltiplo de 2, 0 - (-2) es múltiplo de 2 ya sí sucesivamente. La clase de equivalencia del número 1 será C(1) = {... -5, -3, -1, 1, 3, 5, ...} pues la diferencia entre 1 y los números indicados es múltiplo de 2. 

Del mismo modo podríamos calcular las clases de equivalencia de más números. 

El conjunto formado por las clases de equivalencia se llama conjunto cociente.

En el ejemplo anterior el conjunto cociente Z / 2 es el conjunto formado por las clases de todos los elementos Z / 2 = {C(0), C(1), C(2), ... }.

Particiones

Sea X un conjunto. P es una partición de X si y sólo si:

 

Los conjuntos de P son disyuntos 2 a 2, es decir, si  y entonces                                                                                                              

Observe que si P es una partición de X, entonces todo elemento de X está en uno y sólo un elementouno y sólo un elemento de modo que   parte a   en conjuntos disyuntos. Por ejemplo, el conjunto de barriles propuesto al comienzo de la sección es una partición del conjunto de mangos. Otro ejemplo de una partición es de la división política de un país: El país (visto como un conjunto de personas) se parte en estados o departamentos no vacíos disyuntos entre sí.

Ejemplo

   Sea ={1, 2, 3, 4, 5, 6, 7, 8, 9}

Entonces = {{1, 9}, {2, 8}, {3, 4, 5, 6, 7}}  

Es una partición de X en tres conjuntos: elementos externos (1,9), elementos semi-externos (2, 8) y elementos internos (3, 4, 5, 6, 7). 

Note que Q = {{1, 2, 9}, {2, 8}, {3, 4, 5, 6, 7}} no es partición de X 

(¿por qué?).

Como lo habíamos insinuado, resulta que toda relación de equivalencia determina de manera natural una partición.