uso de relaciones

UNIDAD 3
Maneja relaciones y
grafos en la
resolución de
problemas.

USO DE RELACIONES
 Sean

los conjuntos A1,A2, . . . ,An.
 Una relación R sobre A1×A2×· · ·×An es
cualquier subconjunto de esteproducto
cartesiano, es decir:
R ⊆ A1×A2×· · ·×An

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

Si R = Ø, llamaremos a R, la relación vacía.

RELACIONES BINARIAS
 Dados

dos conjuntos A yB, una relación
R binaria es cualquier subconjunto de
AxB
 Si (a, b) ∈ R diremos que a esta
relacionado con b y lo notaremos por
aRb.
 Si (a, b) ∉ R, escribiremos a R b y
diremos que a no estarelacionado con
b.

EJEMPLO:
 Sea



A = {huevos, leche, maiz}
B = {vacas, cabras, gallinas}

Escribir la relacion R de A a B definida por:
a es producido por b

EJERCICIO 1:
 Sea:



A = {2, 3, 4,5, 6, 7}
B = {10, 11, 12, 13, 14}

escribir los elementos de la relación R,
donde:
aRb si y solo si a divide (exactamente) a
b.

EJERCICIO 2:
 Sea:



A = {0, 1, 2, 3, 4}
B = {0, 1, 2, 3}

Donde(a, b) ∈ R si y solo si:
a=b
a+b=4
a>b
a/b

MATRIZ DE UNA RELACION
 Dados

dos conjuntos finitos, no vacios,

A = {a1, a2, . . . , am} y B = {b1,
b2, . . . , bn}
y una relación R cualquiera de A aB,
llamaremos matriz de R a la matriz
b1 b2siguiente:
… bn
booleana
a1
a2
…
am

EJEMPLO:
A = {1, 2, 3, 4} B = {1, 2, 3, 4}
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,
4)}EJERCICIO 1:
A = {2, 3, 4, 5, 6, 7}
B = {10, 11, 12, 13, 14}
R = {(2, 10), (2, 12), (2, 14), (3, 12), (4, 12), (5, 10), (6, 12),
(7, 14)}

EJERCICIO 2:
 Sea

A = B = {1, 2, 3, 6, 7}
aRb si y sólo si a + b< 9

GRAFO DIRIGIDO DE UNA
RELACION
 Un

grafo dirigido o digrafo es un par
ordenado D = (A,R) donde A es un
conjunto finito y R es una relación
binaria definida sobre A.
 Al conjunto A lollamaremos conjunto de
nodos o vertices de “D”. A los elementos
de R los llamaremos arcos o aristas del
digrafo D.



Tomaremos los elementos de A como puntos
del plano y cuando dos elementos a y b de A...