Relaciones matematicas

Matemáticas Discretas

Unidad III: Relaciones y Funciones

Relaciones
Sean A y B conjuntos no vacíos. Una relación ℜ de A a B es un subconjunto de A x B.

Notación:  Si (a,b) ∈ a ℜ, entonces lo denotamos a R b  Si (a,b) ∉ a ℜ, entonces lo denotamos a ℝ b

Si A es igual a B, se dice que ℜ es una relación sobre A.

Relaciones
Ejemplo: Sea A = B = {1, 2, 3, 6, 7} a R b si y sólo si a+ b < 9. Entonces: ℜ = {(1, 1), (1,2), (1,3), (1,6), (1,7), (2,1), (2,2), (2,3), (2,6), (3,1), (3,2), (3,3), (6,1), (7,1)} Dominio de ℜ = {1, 2, 3, 6, 7} Rango de ℜ = {1, 2, 3, 6, 7}
3 Matemáticas Discretas -Semestre B-2006

Representación de las Relaciones
Dada una relación ℜ existen varias formas de representarla usando:
   

Sistema cartesiano Representación sagitaria Matrizbooleana de adyacencia Dígrafo

4 Matemáticas Discretas -Semestre B-2006

Representación de las Relaciones
Diagrama Cartesiano: Sea A = B = {1, 2, 3, 6, 7} a R b si y sólo si a + b < 9.

7 6 3 2 1 1 2 3 6 7

ℜ = {(1, 1), (1,2), (1,3), (1,6), (1,7), (2,1), (2,2), (2,3), (2,6), (3,1), (3,2), (3,3), (6,1), (7,1)}

5

Matemáticas Discretas -Semestre B-2006

Representación de las RelacionesRepresentación Sagitaria: Sea A = B = {1, 2, 3, 6, 7} a R b si y sólo si a + b < 9.


A
1 2 3 6 7

B
1 2 3 6 7
6 Matemáticas Discretas -Semestre B-2006

ℜ = {(1, 1), (1,2), (1,3), (1,6), (1,7), (2,1), (2,2), (2,3), (2,6), (3,1), (3,2), (3,3), (6,1), (7,1)}

Representación de las Relaciones
Matriz de una relación: Dados dos conjuntos finitos A = {a1, a2, ..., am} y B = {b1, b2,..., bn} que contienen m y n elementos respectivamente y R una relación de A a B, la matriz booleana de adyacencia de la relación, MR , se define por:


mij = 1 si (ai, bj) ∈ ℜ 0 si (ai, bj) ∉ ℜ
7 Matemáticas Discretas -Semestre B-2006

Representación de las Relaciones


Matriz de una relación:

Para el ejemplo: A = B = {1, 2, 3, 6, 7} y  ℜ = {(1, 1), (1,2), (1,3), (1,6), (1,7), (2,1),(2,2), (2,3), (2,6), (3,1), (3,2), (3,3), (6,1), (7,1)}

MR =

1 1 1 1 1

1 1 1 0 0

1 1 1 0 0

1 1 0 0 0

1 0 0 0 0
8

Matemáticas Discretas -Semestre B-2006

Representación de las Relaciones


Dígrafo (gráfica dirigida):

Si A es un conjunto finito y R es una relación sobre A. R también puede representarse gráficamente a través de vértices y arcos, de la siguiente manera: Dibuje

un vértice para cada elemento de A y márquelo con su valor correspondiente. ai R aj trace un arco del vértice ai al vértice aj.
Matemáticas Discretas -Semestre B-2006

 Si

9

Representación de las Relaciones


Dígrafo: Para el ejemplo: A = {1, 2, 3, 6, 7} y 

ℜ = {(1, 1), (1,2), (1,3), (1,6), (1,7), (2,1), (2,2), (2,3), (2,6), (3,1), (3,2), (3,3), (6,1), (7,1)}
1• Grado Interno: Número de arcos que terminan en el vértice.
3

2

• Grado Externo: Número de arcos que salen del vértice.

6

7
10 Matemáticas Discretas -Semestre B-2006

Representación de las Relaciones


Trayectorias en relaciones y dígrafos:

Sea R una relación sobre un conjunto A. Una trayectoria de longitud n en R de “a” a “b” es una secuencia finita π: a, x1, x2, ... ,xn-1,b que comienza con “a” y termina con “b”, tal que a R x1, x1R x2, ... ,xn-1 R b
11 Matemáticas Discretas -Semestre B-2006

Representación de las Relaciones


Trayectorias en relaciones y dígrafos:
 La

longitud de una trayectoria viene dada por el número de arcos que hay en la misma, cuyos vértices no necesitan ser todos diferentes. trayectoria de longitud “n” involucra “n + 1”elementos de A, aunque no sean distintos. la trayectoria comienza y termina en el mismo vértice se llama “ciclo”. 12
Matemáticas Discretas -Semestre B-2006

 Una

 Si

Propiedades de la Relaciones


Reflexiva:

Una relación R sobre un conjunto A es reflexiva si (a,a) ∈ R para todas las a ∈ A. Es decir, todos elementos de A consigo mismo. Como reconocerlas:  Matriz de R: diagonal...