Matematicas

Relaciones y grafos

Relación

Sean los conjuntos A1, A2, . . . , An. Una relaci´on R sobre A1 × A2 × • • • × An es cualquier subconjunto

de este producto cartesiano, es decir,

R ⊆ A1 × A2 × • • • × An

Si R = ∅, llamaremos a R, la relaci´on vac´ıa.

Si R = A1 × A2 × • • • × An, llamaremos a R la relaci´on universal.

Si Ai = A, ∀i = 1, 2, . . . , n, entonces R es una relaci´on n-aria sobre A.

Si n = 2, diremos que R es una relaci´on binaria y si n = 3, una relaci´on ternaria.

Igualdad de Relaciones

Sean R1 una relaci´on n-aria sobre A1×A2ו • •×An y R2 una relaci´on n-aria sobre B1×B2ו • •×Bm.

Entonces R1 = R2 si, y s´olo si n = m y Ai = Bi, ∀i = 1, 2, . . . , n y R1 y R2 son conjuntos de n-tuplas

ordenadas iguales.

Relaciones Binarias

La clase m´as importante de relaciones es la de las relaciones binarias. Debido a que este tipo de relaciones

son las m´as frecuentes, el t´ermino “relaci´on” denota generalmente una relaci´on binaria; adoptaremos este

criterio cuando no haya confusi´on y especificaremos las que no sean binarias con t´erminos tales como

“ternaria” o “n-aria”.

Si (a, b) ∈ R diremos que a est´a relacionado con b y lo notaremos por aRb.

Si (a, b) ∈ R, escribiremos aR b y diremos que a no est´a relacionado con b.

Ejemplo 6.1 Sea A = {huevos, leche, ma´ız} y B = {vacas, cabras, gallinas}. Escribir la relaci´on R

de A a B definida por:

(a, b) ∈ R ⇐⇒ a es producido por b

Solución

La relaci´on ser´ıa:

R = {(huevos,gallinas),(leche,vacas),(leche,cabras)}

Ejemplo

(a) Sea R la relaci´on “menor que” definida en el conjunto Z de los n´umeros enteros.

Escribiremos 3 < 5 para indicar que (3, 5) ∈ R y 5 </ 3 para indicar que (3, 5) ∈ R

(b) Sea R la relaci´on “es un m´ultiplo de” en el conjunto de los enteros positivos.

Entonces, 4R2 pero 2R 4. M´as generalmente, xRy si, y s´olo si x = ky para alg´un k ∈ Z+. As´ı

para todo x, xR1. Si p > 1, entonces p es primo si xRp implica que x = 1 ´o x = p. Un n´umero x

es impar si xR 2.

(c) Cuando un compilador traduce un programa inform´atico construye una tabla de s´ımbolos que

contiene los nombres de los s´ımbolos presentes en el programa, los atributos asociados a cada

nombre y las sentencias de programa en las que est´an presentes cada uno de los nombres. As´ı pues,

si S es el conjunto de los s´ımbolos, A es el conjunto de los posibles atributos y P es el conjunto de

las sentencias de programa, entonces la tabla de s´ımbolos incluye informaci´on representada por las

relaciones binarias de S a A y de S a P .

(d) Como dijimos anteriormente, una relaci´on binaria sobre el conjunto de los n´umeros reales puede

representarse gr´aficamente en el plano cartesiano. La figura siguiente es la gr´afica de la relaci´on

R = {(x, y) ∈ R × R : |x| + |y| = 1}

y

1

x

−1

1

−1

|x| + |y| = 1

Ejemplo Sea A = {1, 2, 3} y R = {(1, 2), (1, 3), (3, 2)}. R es una relaci´on en A ya que es un

subconjunto de A × A. Con respecto a esta relaci´on, tendremos que

1R2, 1R3, 3R2, pero 1R 1, 2R 1, 2R 2, 2R 3, 3R 1, 3R 3

Dominio e Imagen

Llamaremos dominio de una relaci´on R al conjunto formado por todos los primeros elementos de los

pares ordenados que pertenecen a R, e imagen o rango al conjunto formado por los segundos elementos.

Es decir, si R es una relaci´on de A a B, entonces

Dom (R) = {a ∈ A, ∃b : b ∈ B ∧ (a, b) ∈ R}

Img (R) = {b ∈ B, ∃a : a ∈ A ∧ (a, b) ∈ R}

As´ı en el ejemplo anterior, el dominio de R es Dom (R) = {1, 3} y la imagen Img (R) = {2, 3}

Ejemplo 6.4 Para los conjuntos U = {1, 2, 3, 4, 5}, A = {1, 2, 3}, B = {2, 4, 5}, determinar:

(a) |A × B|.

(b) El n´umero de relaciones de A a B.

(c) El n´umero de relaciones binarias en A.

(d) El n´umero de relaciones de A

...