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 a B que contengan al (1,2) y al (1,5).

(e) El n´umero de relaciones de A a B que contengan exactamente cinco pares ordenados.

(f) El n´umero de relaciones binarias en A que contengan siete elementos como m´ınimo.

Solución

(a) |A × B| = |A| • |B| = 3 • 3 = 9

(b) Sea N el n´umero de relaciones de A a B.

Como una relaci´on es cualquier subconjunto del producto cartesiano de A por B, el n´umero de

relaciones de A a B ser´a igual al n´umero de subconjuntos que tenga A × B, es decir, el n´umero de

elementos del conjunto de las partes de este conjunto, por tanto,

N = |P(A × B)| = 2|A×B| = 29

(c) Igual que en el apartado anterior, si N es el n´umero pedido, entonces

N = |P(A × A)| = 2|A×A| = 29

(d) Si eliminamos del producto cartesiano de A y B los pares (1,2) y (1,5), quedar´an 7 pares, luego

el n´umero de posibles relaciones que pueden establecerse sin ellos ser´a 27 igual al n´umero N de

relaciones que contienen a los dos pares dados ya que bastar´ıa con anadirlos a cada una de las

relaciones que no los tienen, por tanto,

N = 27

(e) Dos subconjuntos con cinco pares del producto cartesiano de A y B, ser´an distintos s´olo si se

diferencian en alg´un par sin que el orden en que los mismos figuren en el subconjunto influya para

nada, por tanto, el n´umero de subconjuntos de A×B con cinco pares ser´a igual al de combinaciones

de nueve elementos tomados cinco a cinco, es decir, si N es el n´umero pedido, entonces

5 = 126

(f) Sea Ni el n´umero de relaciones que contienen i elementos y sea N el n´umero pedido. Entonces,

N = N7 + N8 + N9

y razonando igual que en el apartado anterior,

i

...