Tema

2

Relaciones y grafos

Relaciones

Relación `R' : Es cualquier subconjunto de A×B que cumpla la definición de la relación en concreto.

Otra def.: Sean x"A,y"A y grafo(gráfica) R / R" A×A, decimos que xRy si (x,y)"R

El nº de relaciones ó subconjuntos de A×B será

Relación n-aria : Cualquier subconjunto del producto cartesiano de A1× A2×...×An

(Una relación binaria sería una relación de A1×A2)

Propiedades que puede cumplir una relación :

1) Reflexiva, si " a"A ! aRa

2) Simétrica si " a,b / aRb ! bRa

3) Transitiva, si " a,b,c / (aRb y bRc) ! aRc

Antisimetrica, si " a,b / (aRb y bRa) ! a=b

Todo elemento cumple las tres primeras consigo mismo, respecto a la 4º cuidado!, no simetrica"antisimetrica

Respecto a esto último, ver ej. 5.11 pág 126 Grimaldi.

Matriz de una relación A×B : - filas = elementos de A, columnas = elementos de B

- 1 si (ai,bj) " R , 0 si (ai,bj)
R

Relación equivalente '~' : Es la relación binaria que verifica las propiedades reflexiva, simétrica y transitiva.

Clase de equivalencia `[x]' :

Para " x"A, se define “clase de equivalencia de x“ como el conjunto de las a"A / y~x

Se cumple : - x"a ! [x]=[y] (prop. transitiva)

- y por tanto, x no"a ! [x]"[a] = " pero solo para [x]"" porque x"[x]

Las clases de equivalencia forman una familia de subconjuntos"" y disjuntos 2 a 2, (porque por transitiva si

tuvieran un elemento en común serían iguales), cuya unión es A.

Dos clases de equivalencia son entre si, o identicas, o disjuntas.

Ver ejemplo 5.45, pag 146 Grimaldi

Congruencia modulo n : Un ejemplo de relación de equivalencia en Z

Dado un natural p>1 se dice que "a es congruente con b módulo p" y se escribe "a"b (mod p)"

si a=b+p, "Z ; es decir : [a~b] ! [a-b es múltiplo de p]

Esta relación es una equivalencia, ya que :

- es reflexiva, pues b-b es múltiplo de p para todo b " Z .

porque b-b=0 que sera múltiplo de p para =0

- es simétrica, ya que si a-b es múltiplo de p, entonces b-a= también es múltiplo de p.

porque b-a=-(a-b) y  puede ser + o - porque pertenece a Z.

- es transitiva, ya que, si a-b, b-c son múltiplos de p, entonces a-c=(a-b)+(b-c) también es múltiplo de p.

porque a-c=(a-b)+(b-c)

Seran congruentes módulo p si y solo si dan el mismo resto al dividirlos por p.

Comprobación :

!