matemática discreta - universidad de castilla - la mancha · pdf filerm está...

1Matemática discreta. Relaciones binarias

Relaciones binarias

Matemática discreta


Relación binaria en A

• Dados dos conjuntos A y B, una relación R binaria es cualquier subconjunto de AxB

• Dados a∈A y b∈B, a está relacionado con b por R si (a,b)∈R, aRb. Si a no estárelacionado con b, es decir, (a,b)∉R, escribimos aRb.

• Si B=A, R es una relación binaria en A.


Representación de una relación

• Formal: aRb si a y b cumplen una cierta propiedad P.

• Diagrama sagital: aRb• Matriz de adyacencia: aRb y aRc

a b

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

....

....

.01.

.... b c

a


Diagrama sagital• Representación gráfica con flechas.

– a∈A • a– aRb

ejemplo: A={a,b,c,d}R={(a,c),(a,d),(b,a),(b,b),(b,d),(c,a),(d,c)}

a • • b

a • • b

c • • d


Matriz de adyacencia• Matriz booleana MR=(mij)• A={a1, ..., an} mij=1 si aiRaj

mij=0 si aiRaj

ejemplo: A={a,b,c,d}R={(a,c),(a,d),(b,a),(b,b),(b,d),(c,a),(d,c)}

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

=

0100000110111100

MRSuponemos un orden en los elementos de A, en este caso el alfabético.


Operaciones con relaciones 1

Dadas R1 y R2 sobre A• Unión:

R1∪ R2={(a,b) ∈AxA / aR1b ó aR2b}• Composición o producto:

R1°R2={(a,b) ∈AxA / ∃c∈A aR1c y cR2b}– En general, R1°R2 ≠ R2°R1

– La composición es asociativa: Rn+1=Rn ° R


Operaciones con relaciones 2• M(R1∪ R2)=MR1 ⊕ MR2

• M(R1°R2)=MR1 ⊗ MR2

– ⊕ suma booleana– ⊗ producto booleano

⊕ 0 10 0 11 1 1

⊗ 0 10 0 01 0 1


Operaciones con relaciones 3

Dada R sobre A={a1,..,an} y MR su matriz de adyacencia:

• MR = OR ⇔ R=∅ (matriz nula de orden n)

• MR = 1R ⇔ R=AxA (matriz de unos de orden n)

• MRm = (MR )m, m ∈Z+ (m-ésima potencia booleana)

Rm está formada por los pares de elementos que se pueden conectar mediante un camino de longitud m.


ejemplo

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

=

0000100001000010

RMa •

• cd •

• bR={(a,b),(b,c),(c,d)}

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

=

0000000010000100

2RM

a •

• cd •

• b

a •

• cd •

• b

R2={(a,c),(b,d)}

R3={(a,d)}⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

=

0000000000001000

3RM


PropiedadesR definida sobre A, con matriz de adyacencia M y

Card(A)=n• Reflexiva: [∀x∈A xRx] ⇔ In⊕M=M

• Simétrica: [∀x,y∈A xRy ⇒ yRx] ⇔ M=Mt

• Transitiva: [∀x,y,z∈A xRy, yRz ⇒ xRz] ⇔M⊕M2=M

• Antisimétrica: [∀x,y∈A xRy , yRx ⇒ x=y] ⇔ en M+Mt no aparece ningún 2 salvo, a lo sumo en la diagonal.


Cierre de relaciones 1• Cierre reflexivo: CR(R) menor relación reflexiva que

contiene a R.– R ⊂ CR(R). − CR(R) es reflexiva– Si S es reflexiva y tal que R⊂S, entonces CR(R) ⊂ S.

• Cierre simétrico: CS(R) menor relación simétrica que contiene a R.– R ⊂ CS(R). − CS(R) es simétrica– Si S es simétrica y tal que R⊂S, entonces CS(R) ⊂ S.

• Cierre transitivo: CT(R) menor relación transitiva que contiene a R.– R ⊂ CT(R). − CT(R) es transitiva– Si S es transitiva y tal que R⊂S, entonces CT(R) ⊂ S.


Cierre de relaciones 2R definida sobre A={a1,..,an}, con matriz de

adyacencia MR .• MCR(R) = MR ⊕ In

• MCS(R) = MR ⊕ MtR

• MCTR(R) = MR ⊕ M2R ⊕ M3

R ⊕...⊕ MnR


Relaciones de orden

Relaciones de orden• Dada una relación binaria R definida sobre

A, se dice que R es una relación de ordenen A si verifica las propiedades:– reflexiva– antisimétrica– transitiva

Se dice entonces que a está ordenado por R o que el par (A,R) es un conjunto ordenado.


Relaciones de orden

NotaciónUtilizaremos el símbolo ≤ para las relaciones

de orden.aRb a ≤ b

Se lee a es anterior a b (menor o igual) o bien b es posterior a a (mayor o igual)

• Distintas relaciones sobre un mismo conjunto, dan lugar a distintos conjuntos ordenados.

• a,b∈A son comparables si aRb o bRa


Relaciones de orden

ejemploEn N, a ≤ b ⇔ ∃n ∈N / b=an

Es una relación de orden:– reflexiva: a=a1 ∀a∈N – antisimétrica: ∀a,b∈N si a ≤ b y b ≤ a ∃ n,m ∈N /

b=an y a=bm, entonces b= [bm]n=bm·n luego m·n=1 y como n,m ∈N m=n=1, así a=b

– transitiva: ∀a,b,c∈N si a ≤ b y b ≤ c ∃ n,m ∈N / b=an y c=bm, entonces c= [an]m=an·m luego si k = n·m, ∃ k∈N /c=ak, es decir, a ≤ c


Relaciones de orden

Diagrama Hasse 1• Dada una relación de orden R en A y R1 una

relación asociada a R tal que

aR1b ⇔ aRb y a ≠ b (a<b ⇔ a ≤ b y a ≠ b)

el diagrama Hasse de R es el diagrama sagital de la relación HR=R1-R1

2

Si Card(A)=n, matricialmente: MHR=(MR-In)-(MR-In)2


Relaciones de orden

Diagrama Hasse 2• Permite asociar a una relación de orden un

diagrama más sencillo que el diagrama sagital.• Construcción del diagrama Hasse a partir del

diagrama sagital:– eliminar los bucles– eliminar todas las flechas que puedan derivarse de

aplicar la propiedad transitiva.


Relaciones de orden

ejemplo

a •

• d

• c

b •

• e a •

• d

• c

b •

• e


Relaciones de orden

Orden total y parcial• (A, ≤) está totalmente ordenado si

cualquier par de elementos son comparables, se dice entonces que ≤ es de orden total. En otro caso, se dice que (A, ≤) está parcialmente ordenado y que ≤ es de orden parcial.

• C es una cadena de (A, ≤) si C ⊂ A y (C, ≤) está totalmente ordenado.


Relaciones de orden

Elementos notables 1Dados (A,≤) y C ⊂ A, C≠∅• a∈A es cota superior de C si ∀c∈C, c≤a.

– C está acotado superiormente– La menor de las cotas superiores es el supremo.

• a∈A es cota inferior de C si ∀c∈C, a≤c.– C está acotado sinferiormente– La mayor de las cotas inferiores es el ínfimo.

• El supremo y el ínfimo, si existen, han de ser comparables con el resto de las cotas superiores o inferiores, respectivamente.


Relaciones de orden

Elementos notables 2Dados (A,≤) y C ⊂ A, C≠∅• a∈C es elemento maximal de C si

∀c∈C, a≤c ⇒ a=c.• m∈C es máximo de C si ∀c∈C, c≤m.

– si existe, es el único elemento maximal de C• a∈C es elemento minimal de C si

∀c∈C, c≤a ⇒ a=c.• m∈C es mínimo de C si ∀c∈C, m≤c

– si existe, es el único elemento minimal de C


Relaciones de orden

Elementos notables 3• Pueden existir uno, varios o ningún elemento

maximal y minimal.• El máximo (mínimo), cuando existe, es el

único elemento maximal (minimal).• Si en C existe supremo (ínfimo) es único.• Si C tiene máximo (mínimo) coincide con el

supremo (ínfimo).


Relaciones de orden

ejemplo

a •

• d

• c

b •

• e • {a,b,e}– d es cota superior y supremo– {b,e} son elementos

maximales– no tiene máximo– a es cota inferior, ínfimo,

mínimo y el único elemento minimal.


Relaciones de equivalencia


Dada una relación binaria R definida sobre A, se dice que R es una relación de equivalenciaen A si verifica las propiedades:– reflexiva– simétrica– transitiva



Clase de equivalenciaDada R una relación de equivalencia en A y

a∈A, se define la clase de equivalencia de a como [a]={x ∈A / xRa }.

• [a] ≠∅ pues a∈[a].• [a]=[b] ⇔∀a,b∈A aRb• [a]∩[b]=∅⇔ ∀a,b∈A aRb

• ∪a∈A[a]=A• Cualquier elemento de [a] es un representante

de la clase.



Conjunto cociente• Una partición de un conjunto A es una familia de

subconjuntos no vacíos de A, {Ai} disjuntos entre síy cuya unión es A.

∀ i Ai≠∅; Aj∩Ai=∅ ∀ i≠j; ∪Ai=A• La relación de equivalencia R define en A una

partición formada por las clases de equivalencia.• Llamamos conjunto cociente de A por R a

A/R={[a]/ a∈A}.• Cada partición de A está asociada a una relación de

equivalencia definida en él.



ejemplo 1A={palabras de n bits}w(a) el número de unos que contiene a

aRb ⇔w(a) ≡ w(b) (mod 2)R es de equivalencia:

– Reflexiva: aRaw(a) ≡ w(a)(mod 2)

– Simétrica: aRb ⇒ bRaw(a) ≡ w(b)(mod 2) ⇒ w(b)≡w(a)(mod 2)

– Transitiva: aRb y bRc ⇒ aRcw(a)≡w(b)(mod 2) y w(b)≡w(c)(mod 2) ⇒ w(a)≡w(c)(mod 2)



ejemplo 2R define en A una partición formada por dos

clases de equivalencia, cada una con 2n-1

elementos.[0]={a∈A / a tiene un número par de unos}[1]={a∈A / a tiene un número impar de unos}Para n=3

[0]={000, 011, 101, 110}[1]={001, 010, 100, 111}


Planificación de tareas

Planificación de tareas 1

• Tareas entre las que hay relaciones de dependencia, unas han de realizarse antes que otras.

• Uno o varios equipos, simultáneamente, realizan las tareas.

• Objetivo: distribuir las tareas entre los equipos disponibles, acatando la dependencia entre tareas.

• Planificación: asignación ordenada de tareas a cada equipo.



Planificación de tareas 2• A: lista de tareas a realizar.• R relación binaria sobre A

aRb ⇔ a es previo a b, es decir, a debe realizarse antes que b.

• m∈A es minimal si ∀a∈A, aRm• Eliminar m de (A,R) consiste en suprimir todos

los pares de R en los que a parezca m.• A es realizable ⇔ R se puede extender a un orden

topológico.



Orden topológico 1

• Un orden topológico < es una extensión de un orden parcial ≤ sobre un conjunto Asi se verifica que:

si a≤b entonces a<b.



Orden topológico 21 Iniciar T=[]2 Mientras A≠∅

– si ∃ m∈A minimalIncluir m en TEliminar m de (A,R)Volver a (2)

– En otro caso, A no es realizable. Salir3 Salida T orden topológico.



Planificación correcta1 Iniciar T=[]2 Mientras A≠∅

– si ∃ m∈A minimal y primera tarea de un equipo EIncluir m en TEliminar m de (A,R) y de EVolver a (2)

– En otro caso, P no es correcta. Salir3 Salida T orden topológico.



Tiempo de realización de tareas• coste de m, w(m), es el tiempo que se necesita para

realizar la tarea m, una vez terminadas las tareas previas a m.

• t(m) tiempo que se necesita para la realización de la tarea m, incluido el tiempo de espera necesario para que se realicen las tareas previas a m.

t(m)=w(m) + max{t(ai) / aiRm}• t(R)=max{t(a) / a∈A } es el tiempo mínimo en el que

se pueden realizar las tareas de A.



Tiempo mínimo para la realización de tareas

1 Mientras existan tareas no marcadas en A– si existe m∈A minimal no marcado

Calcular t(m)=w(m)+max{t(b) / bRm}Marcar mVolver a (1)

– En otro caso, A no es realizable. Salir2 Salida t(R)=max{t(a) / a∈A}


Tiempo para la realización de planificaciones 1


• tp(m) tiempo que se necesita para la realización de la tarea m en la planificación P, incluido el tiempo de espera necesario para que se realicen las tareas previas a m y las anteriores a m en su equipo.

tp(m)=w(m) + max{tp(ai) / aiRm ó ai es anterior a m en su equipo}

• tp(R)=max{tp(a) / a∈A } es el tiempo mínimo en el que se pueden realizar las tareas de A en la planificación P.


Tiempo para la realización de planificaciones 2


1 Mientras existan tareas no marcadas en A– si existe m∈A minimal no marcado y primera

tarea no marcada de un equipo.Calcular tp(m)=w(m)+max{tp(b) / bRm ó b es el anterior a m en su equipo}Marcar mVolver a (1)

– En otro caso, P no es correcta. Salir2 Salida tp(R)=max{tp(a) / a∈A}



Optimización del número de equipos equipos 1

• W=Σw(a), a∈A• A conjunto de n tareas• Si P es una planificación con n equipos, se

verifica W≤ n·t(R) ⇒ n ≥ W/t(R). Esto nos da una cota inferior para el número de equipos necesarios para ejecutar las tareas en el menor tiempo t(R).


Optimización del número de equipos equipos 2


1 Iniciar los equipos Ei=[] y los tiempo ti=0, 1≤ i≤n

2 ∀ m∈A minimal– Encontrar el menor k / tk=0 ; xk= m ; tk= w(m) ; incluir m en Ek

3 Mientras existan tareas no marcadas en A– Si ∃ Ei / ti ≠0

∀ j / tj = min{ti /ti ≠0}, marcar xj (último elemento de Ej) ; tj’= tj ; tj=0∀a / xjRa y todos sus previos están marcados

• Encontrar el menor k / tk=0 ; xk=a ; tk= tj’+ w(a) ; incluir a en EkVolver a (3)

– R no es realizable. Salir

4 Salida P={Ei / Ei ≠[]}

matemática discreta - universidad de castilla - la mancha · pdf filerm está...

Documents