Diagramas De Hasse
Páginas: 5 (1042 palabras)
Publicado: 10 de abril de 2011
6.7. Diagramas de Hasse
Una relación R:A(B es de orden parcial o parcialmente ordenada si es reflexiva, antisimétrica y transitiva. De la misma manera que si B=A se dice que R: A(A es de orden parcial si es reflexiva, antisimétrica y transitiva y por lo tanto el conjunto A es parcialmente ordenado.
Si R es de orden parcial, es posible representar el grafo dirigido de una manera mássencilla por medio del diagrama de Hasse. Para obtener el diagrama de Hasse conviene seguir los pasos.
1.- Eliminar los lazos (aristas que salgan de un vértice y regresan a él).
2.- Eliminar la tercera arista de la transitividad. Se sabe que para que una relación R sea transitiva se debe cumplir que si aRb y bRc entonces aRc. Por lo tanto la tercera arista de la transitividad es aRc y esa esprecisamente la que se debe eliminar ya que con las dos aristas anteriores es suficiente.
3.- Se cambian todas las flechas por líneas.
Ejemplo 1:
Sean B=A={1,2,4,7,8} y sea R:A(B tal que aRb si a≥b.
a) ¿Cuáles son los elementos de R?.
b) Encontrar MR y GR.
c) Mostrar que se trata de una relación parcial, probando que R es reflexiva, antisimétrica y transitiva.
d) Si R es de ordenparcial encontrar el diagrama de Hasse.
Solución
a) Los elementos de R son:
R={(1,1),(2,1),(2,2),(4,1),(4,2),(4,4),(7,1),(7,2),(7,4),(7,7),(8,1),(8,2),(8,4),(8,7),(8,8)}
b) El grafo y la matriz de R son:
a) Se observa que es reflexiva, porque la diagonal principal de la matriz contiene solamente unos, lo cual significa que todo elemento está relacionado son él mismo. Esantisimétrica ya que se cumple que para a≠b si (a,b)(R, entonces (b,a)[pic]R. También es transitiva ya que MR= MR +MR2. Por lo tanto se trata de una relación de orden parcial.
El diagrama de Hasse es:
Recordar que eliminar la tercera arista de la transitividad significa que en aquellos casos en donde aRb y bRc se debe eliminar aRc. Por ejemplo el ejemplo anterior 8R2 y 2R1 se eliminó 8R1 que es latercera arista de la transitividad y de esa misma manera se procede en todos los casos donde aplique.
De este ejemplo se puede concluir que para A=B=Z, la relación R:A(B es de orden parcial si a≥b o a≤b pero no es una relación parcialmente ordenada si ab porque ya no sería reflexiva.
La relación parcialmente ordenada también es aplicable a conjuntos, en donde el orden se da por medio del conceptode subconjunto ([pic]).
Ejemplo 2
Sea X= {a,b,c} y sea A = B = P(X) = {(, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. La relación R:A(B es de orden parcial para la operación subconjunto ([pic]).
R = {((,(), ((,{a}), ((,{b}), ((,{c}), ((,{a,b}), ((,{a,c}), ((,{b,c}), ((,{a,b,c}), ({a},{a}), ({a},{a,b}), ({a},{a,c}), ({a},{a,b,c}), ({b},{b}), ({b},{a,b}), ({b},{b,c}), ({b},{a,b,c}),({c},{c}), ({c},{a,c}), ({c},{b,c}), ({c},{a,b,c}), ({a,b},{a,b}), ({a,b},{a,b,c}), ({a,c},{a,c}), ({a,c},{a,b,c}), ({b,c},{b,c}), ({b,c},{a,b,c}), ({a,b,c},{a,b,c})}
En esta relación el par ordenado ((,() se encuentra dentro de la relación R porque ([pic](, de la misma manera que ({a,b},{a,b,c}) es también par ordenado de R porque {a,b}[pic]{a,b,c}.
El grafo dirigido es:
El diagrama de Hassequitando los lazos y eliminando la tercera arista de la transitividad en aquellos casos en donde proceda, quedará de la siguiente manera:
Como se pudo observar en los ejemplos anteriores los diagramas de Hasse son representaciones gráficas de un conjunto finito parcialmente ordenado. Los diagramas de Hasse eliminan la necesidad de lazos ya que por definición las relaciones de orden parcial sonreflexivas, de la misma manera que es posible eliminar las terceras aristas de la transitividad considerando que el relacionamiento se mantiene con las aristas restantes. Los diagramas de Hasse tienen de esta forma la finalidad de simplificar las representaciones gráficas de las relaciones de orden parcial.
Problemas propuestos:
6.27 Sean A=B={1, 2, 3, 6, 8} y R:A(B donde aRb si y solo si...
Una relación R:A(B es de orden parcial o parcialmente ordenada si es reflexiva, antisimétrica y transitiva. De la misma manera que si B=A se dice que R: A(A es de orden parcial si es reflexiva, antisimétrica y transitiva y por lo tanto el conjunto A es parcialmente ordenado.
Si R es de orden parcial, es posible representar el grafo dirigido de una manera mássencilla por medio del diagrama de Hasse. Para obtener el diagrama de Hasse conviene seguir los pasos.
1.- Eliminar los lazos (aristas que salgan de un vértice y regresan a él).
2.- Eliminar la tercera arista de la transitividad. Se sabe que para que una relación R sea transitiva se debe cumplir que si aRb y bRc entonces aRc. Por lo tanto la tercera arista de la transitividad es aRc y esa esprecisamente la que se debe eliminar ya que con las dos aristas anteriores es suficiente.
3.- Se cambian todas las flechas por líneas.
Ejemplo 1:
Sean B=A={1,2,4,7,8} y sea R:A(B tal que aRb si a≥b.
a) ¿Cuáles son los elementos de R?.
b) Encontrar MR y GR.
c) Mostrar que se trata de una relación parcial, probando que R es reflexiva, antisimétrica y transitiva.
d) Si R es de ordenparcial encontrar el diagrama de Hasse.
Solución
a) Los elementos de R son:
R={(1,1),(2,1),(2,2),(4,1),(4,2),(4,4),(7,1),(7,2),(7,4),(7,7),(8,1),(8,2),(8,4),(8,7),(8,8)}
b) El grafo y la matriz de R son:
a) Se observa que es reflexiva, porque la diagonal principal de la matriz contiene solamente unos, lo cual significa que todo elemento está relacionado son él mismo. Esantisimétrica ya que se cumple que para a≠b si (a,b)(R, entonces (b,a)[pic]R. También es transitiva ya que MR= MR +MR2. Por lo tanto se trata de una relación de orden parcial.
El diagrama de Hasse es:
Recordar que eliminar la tercera arista de la transitividad significa que en aquellos casos en donde aRb y bRc se debe eliminar aRc. Por ejemplo el ejemplo anterior 8R2 y 2R1 se eliminó 8R1 que es latercera arista de la transitividad y de esa misma manera se procede en todos los casos donde aplique.
De este ejemplo se puede concluir que para A=B=Z, la relación R:A(B es de orden parcial si a≥b o a≤b pero no es una relación parcialmente ordenada si ab porque ya no sería reflexiva.
La relación parcialmente ordenada también es aplicable a conjuntos, en donde el orden se da por medio del conceptode subconjunto ([pic]).
Ejemplo 2
Sea X= {a,b,c} y sea A = B = P(X) = {(, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. La relación R:A(B es de orden parcial para la operación subconjunto ([pic]).
R = {((,(), ((,{a}), ((,{b}), ((,{c}), ((,{a,b}), ((,{a,c}), ((,{b,c}), ((,{a,b,c}), ({a},{a}), ({a},{a,b}), ({a},{a,c}), ({a},{a,b,c}), ({b},{b}), ({b},{a,b}), ({b},{b,c}), ({b},{a,b,c}),({c},{c}), ({c},{a,c}), ({c},{b,c}), ({c},{a,b,c}), ({a,b},{a,b}), ({a,b},{a,b,c}), ({a,c},{a,c}), ({a,c},{a,b,c}), ({b,c},{b,c}), ({b,c},{a,b,c}), ({a,b,c},{a,b,c})}
En esta relación el par ordenado ((,() se encuentra dentro de la relación R porque ([pic](, de la misma manera que ({a,b},{a,b,c}) es también par ordenado de R porque {a,b}[pic]{a,b,c}.
El grafo dirigido es:
El diagrama de Hassequitando los lazos y eliminando la tercera arista de la transitividad en aquellos casos en donde proceda, quedará de la siguiente manera:
Como se pudo observar en los ejemplos anteriores los diagramas de Hasse son representaciones gráficas de un conjunto finito parcialmente ordenado. Los diagramas de Hasse eliminan la necesidad de lazos ya que por definición las relaciones de orden parcial sonreflexivas, de la misma manera que es posible eliminar las terceras aristas de la transitividad considerando que el relacionamiento se mantiene con las aristas restantes. Los diagramas de Hasse tienen de esta forma la finalidad de simplificar las representaciones gráficas de las relaciones de orden parcial.
Problemas propuestos:
6.27 Sean A=B={1, 2, 3, 6, 8} y R:A(B donde aRb si y solo si...
Leer documento completo
Regístrate para leer el documento completo.