MATEMATICA DISCRETAUNIDAD Nº 3

2º parte

RELACIONES Y DIGRAFOS TEORIA

1

Bibliografía: Estructuras de Matemáticas Discretas para Computación. Kolman y Busby. Cap IV

RELACIONES DE EQUIVALENCIA

¿Cómo se demuestran estas propiedades?

- Si A es finito, se puede analizar el grafo y/o la matriz

- Si A es infinito, se deben probar mediante una demostración, directa o

indirecta.

Definición: Sea R definida en A. Se dice que R es una relación de equivalencia

si y solo si se cumplen las siguientes propiedades:

1) Propiedad Reflexiva: xRxAx ,

2) Propiedad de Simetría: yRxxRyAyx ,,

3) Propiedad de Transitividad: xRzyRzxRyAzyx ,,,

2

Si alguna de estas propiedades no se cumple entonces la relación R no es de

equivalencia.

Se presentan distintas situaciones: R puede no ser reflexiva o no ser simétrica o

no ser transitiva. Analicemos cada caso:

- Si xRxAx , , entonces se dice que R no es reflexiva y por lo tanto no

es de equivalencia.

- Si yRxxRyAyx ,, , entonces se dice que R no es simétrica y por

lo tanto no es de equivalencia.

- Si xRzyRzxRyAzyx ,,, , entonces se dice que R no es

transitiva y por lo tanto no es de equivalencia.

3

DESCRIPCIÓN DE DIGRAFOS Y MATRICES DE RELACIONES REFLEXIVAS, SIMÉTRICAS Y TRANSITIVAS

Relaciones reflexivas: * R es reflexiva si y solo si todos los elementos tienen lazos. * R es reflexiva si y solo la matriz MR es tal que mii=1 i

Relaciones simétricas: * R es simétrica si y solo si se cumple que, si la arista (x,y) pertenece al grafo entonces también aparece la arista (y,x) en el grafo* R es simétrica si y solo si la matriz MR es tal que mij=mji i,j

Relaciones transitivas: * R es transitiva si y solo si se cumple que , si las aristas (x,y) e (y,z) pertenecen al grafo entonces también aparece la arista (x,z) en el grafo* Sean m2

ij y mij los elementos genéricos de MR2 y MR . R es transitiva si y solo si se cumple que m2

ij =1 mij =1 , i,j4

b) R2 dada por el grafo G2

G2

Son las siguientes relaciones de equivalencia? Decir que propiedades se

cumplen y cuales que no se cumplen Ejemplos 1: Son las siguientes relaciones de equivalencia?

a) R1 dada por el grafo G1

G1

Ejemplos 1: Son las siguientes relaciones de equivalencia?

a) R1 dada por el grafo G1

G1

EJERCICIOS PARA EL AULA

5

jj

mm rr

ss aa

pp

c) A = { a,b,c,d,e} y R3 dada por extensión

R3 ={(a,c),(a,d),(c,a),(d,a),(c,d),(d,c),(a,a),(b,b),(c,c),(d,d),(e,e)}

d) R4 dada por la matriz MR

10000

01111

01111

01111

01111

MR

e) R5 dada por la matriz:

1100

1111

0111

0111

5RM

f) R6 dada por la matriz:

101

110

011

6RM

d) R4 dada por la matriz MR

10000

01111

01111

01111

01111

MR

e) R5 dada por la matriz:

1100

1111

0111

0111

5RM

g) Sea R7 definida en Z por medio de a R7 b a+ b es par

Demostrar que es una relación de equivalencia. 6

PARTICIONES Y RELACIONES DE EQUIVALENCIA

a b c d

h j w k

e p t s f m

A

Sea A un conjunto. Si P es una partición de A, entonces P puede usarse para

construir una relación de equivalencia en A.

Teorema :

Sea P una partición de A. Sea la relación R en A definida como:

a R b a y b son miembros de un mismo bloque de P

Entonces R es una relación de equivalencia en A

7

Ejemplo

Ejemplo

Sea A = { a , b, c , d , e } y sea P = {{a,b},{c,d,e}} .

Entonces la relación de equivalencia determinada por P en A es

R={(a,a),(b,b),(a,b),(b,a),(c,c),(d,d),(e,e),(c,d),(d,c),(c,e),(e,c),(d,e)

,(e,d)}

Gráficamente:

d c

a

b e

EJERCICIOS PARA EL AULA

Sea A = { a , b, c , d , e } y sea P = {{a,b},{c,d,e}} .

Encontrar la relación de equivalencia determinada por P

R={(a,a),(b,b),(a,b),(b,a),(c,c),(d,d),(e,e),(c,d),(d,c),(c,e),(e,c),(d,e),(e,d)}

8

CLASES DE EQUIVALENCIA

9

Definición:Sea aA y sea R definida en A una relación de equivalencia

Se define a la “clase de equivalencia del elemento a” como el conjunto relativo

al elemento a

Simbólicamente [a] = R(a) = { x A / aRx }

Observación: Si P es una partición de A y R es la relación de equivalencia determinada por P

en A, entonces los elementos de P (subconjuntos de A), pueden ser descriptos

en términos de las clases de equivalencia

Si A1 P y a A1 entonces A1=[a]

10

EJEMPLOS

a b c d

h j w k

e p t s f m

A

A

A1=[a]

A2=[d]

A3=[s] A4=[h]

A1=[e] =[c]=[d] ={e,c,d }

A2=[a] = [b] ={a,b}

Conjunto Cociente de una relación de equivalencia

La partición P de la que habla el segundo teorema consta de todas las clases de

equivalencia y esta partición será denotada como A/R para reflejar el hecho de

que P es el conjunto cociente de A que está construido a partir de R .

Entonces la notación A/R representa a la partición P que R determina en A

Lema:

Sea R una relación de equivalencia en un conjunto A y sean a,b A.

Entonces aRb [a] = [b] Teorema :

Sea R una relación de equivalencia definida en A y sea P la colección de todos

los conjuntos distintos [a] con a A. Entonces P es una partición de A

provocada por R y recíprocamente, R es la relación de equivalencia determinada

por P

11

distintas

Definición

EJERCICIOS PARA EL AULA

12

f f

aa xx

cc

dd

bb ggff

yy

rr

sspp

qq

nn

uu

tt

mm

ss

rr

nn

tt

uupp

qq

Sabiendo que los siguientes grafos corresponden a relaciones de equivalencia, encontrar el conjunto cociente determinado por ellas

EJERCICIOS PARA EL AULA

Encontrar A/R en los siguientes casos: Sea A = N y sea R definida por: aRb a+b es

par Sea A = Z y sea R definida por aRb 3|(a-b)En ambos casos representar la partición en un

diagrama de Venn

13