MA265 Sesión 9.1 Permutaciones

UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 1 Relaciones: propiedades CONTENIDO UNIDAD N° 3: RELACIONES Y FUNCIONES 3.4 Relaciones: propiedades ▪ Reflexiva ▪ Irreflexiva ▪ Simétrica ▪ Antisimétrica ▪ Asimétrica ▪ Equivalencia UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 2 Relaciones: propiedades Una relación R en un conjunto A es: Reflexiva  [( a , a )  R,  a  A ] • Si 𝑀 𝑅 = [𝑚 𝑖𝑗 ] es la representación matricial de R , entonces: R es reflexiva  [𝑚 𝑖𝑖 = 1,  𝑖] • El dígrafo asociado a una relación reflexiva tiene bucles (lazos) en todos sus vértices. Ejemplo En 𝐴 = {1; 2; 3; 4} , la relación 𝑅 = {(𝟏; 𝟏), (1; 2), (1; 3), (1; 4), (𝟐; 𝟐), (𝟑; 𝟑), (4; 1), (𝟒; 𝟒)} es reflexiva. Note que cada elemento en la diagonal de 𝑀 𝑅 = 1 2 3 4 1 2 3 4 [ 𝟏 1 0 𝟏 1 1 0 0 0 0 1 0 𝟏 0 0 𝟏 ] es igual a 1. Además, en su dígrafo se observa que en todos sus vértices hay bucles: Irreflexiva  [( a , a )  R,  a  A ] • Si 𝑀 𝑅 = [𝑚 𝑖𝑗 ] es la representación matricial de R , entonces: R es irreflexiva  [𝑚 𝑖𝑖 = 0,  𝑖] • El dígrafo asociado a una relación irreflexiva no tiene bucles (lazos) en sus vértices. Ejemplo En 𝐴 = {1; 2; 3; 4} , la relación 𝑅 = {(1; 2), (1; 3), (1; 4), (4; 1)} es irreflexiva. Note que cada elemento en la diagonal de 𝑀 𝑅 = 1 2 3 4 1 2 3 4 [ 𝟎 1 0 𝟎 1 1 0 0 0 0 1 0 𝟎 0 0 𝟎 ] es igual a 0. UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 3 Además, en su dígrafo se observa que ningún vértice tiene bucle: Simétrica  [( a , b )  R  ( b , a )  R ] • Si 𝑀 𝑅 = [𝑚 𝑖𝑗 ] es la representación matricial de R , entonces 𝑀 𝑅 es simétrica. R es simétrica  [si 𝑚 𝑖𝑗 = 1  𝑚 𝑗𝑖 = 1 ] • Las aristas de un dígrafo asociado a una relación simétrica son bidireccionales o son bucles. • En cada vértice se cumple que el grado interno coincide con el grado externo. Ejemplo En 𝐴 = {1; 2; 3; 4} , la relación 𝑅 = {(𝟏; 𝟐), (𝟏; 𝟑), (𝟏; 𝟒), (𝟐; 𝟏), (2; 2), (𝟑; 𝟏), (𝟒; 𝟏)} es simétrica. Note que 𝑀 𝑅 = 1 2 3 4 1 2 3 4 [ 0 𝟏 𝟏 1 𝟏 𝟏 0 0 𝟏 0 𝟏 0 0 0 0 0 ] = (𝑀 𝑅 ) 𝑇 . Además, en su dígrafo se observa todos los arcos (que conectan vértices diferentes) son de ida y vuelta. Antisimétrica  [ a  b  ( a , b )  R  ( b , a )  R ] • Si 𝑀 𝑅 = [𝑚 𝑖𝑗 ] es la representación matricial de R , entonces: R es antisimétrica  [si 𝑖  𝑗  (𝑚 𝑖𝑗 = 0  𝑚 𝑗𝑖 = 0)] • El dígrafo asociado a una relación antisimétrica no tiene aristas bidireccionales. Ejemplo En 𝐴 = {1; 2; 3; 4} , la relación 𝑅 = {(1; 2), (1; 3), (2; 2), (4; 1)} es antisimétrica. Si 𝑖  𝑗, note que 𝑚 𝑖𝑗 = 1 implica que 𝑚 𝑗𝑖 = 0 en 𝑀 𝑅 = 1 2 3 4 1 2 3 4 [ 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 ] UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 4 Además, en su dígrafo se observa todos los arcos (que conectan vértices diferentes) son de ida o de vuelta. Asimétrica  [( a , b )  R  ( b , a )  R ] • Si 𝑀 𝑅 = [𝑚 𝑖𝑗 ] es la representación matricial de R , entonces: R es asimétrica  [(si 𝑚 𝑖𝑗 = 1  𝑚 𝑗𝑖 = 0)  𝑚 𝑖𝑖 = 0] • Las aristas de un dígrafo asociado a una relación asimétrica son unidireccionales y no tiene bucles. • Se cumple que R es asimétrica si y solo si R es antisimétrica e irreflexiva. Ejemplo En 𝐴 = {1; 2; 3; 4} , la relación 𝑅 = {(1; 2), (1; 3), (4; 1)} es asimétrica. N ote que 𝑚 𝑖𝑗 = 1 implica que 𝑚 𝑗𝑖 = 0 en 𝑀 𝑅 = 1 2 3 4 1 2 3 4 [ 𝟎 1 0 𝟎 1 0 0 0 0 0 1 0 𝟎 0 0 𝟎 ] y cada elemento de su diagonal es 0. Además, en su dígrafo se observa que no hay bucles y todos los arcos son o de ida o de vuelta. Transitiva  [Si ( a , b )  R  ( b , c )  R  ( a , c )  R ] • Si 𝑀 𝑅 = [𝑚 𝑖𝑗 ] es la representación matricial de R , entonces: R es transitiva  [si (𝑚 𝑖𝑗 = 1  𝑚 𝑗𝑘 = 1)  𝑚 𝑖𝑘 = 1] • Si 𝑀 𝑅 = [𝑚 𝑖𝑗 ] es la representación matricial de R , entonces todos los unos de la matriz 𝑀 𝑅 2 de la posición 𝑖𝑗 están en la matriz 𝑀 𝑅 en la…