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ás sencilla 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 es precisamente 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 orden
parcial 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:
c) 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. Es anti simétrica
ya que se cumple que para a≠b si (a,b)ÎR,
entonces (b,a)ÏR.
También es transitiva ya que MR= MR +MR 2 . Por lo tanto se trata de una
relación de orden parcial.
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 la tercera 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 concepto de
subconjunto (Í ).
En matemáticas, un diagrama de Hasse es una
representación gráfica simplificada de un conjunto parcialmente ordenado finito. Esto se
consigue eliminando información redundante. Para ello se dibuja una arista
ascendente entre dos elementos solo si uno sigue a otro sin haber otros
elementos intermedios.
En un diagrama de Hasse
se elimina la necesidad de representar:
·
ciclos
de un elemento, puesto que se entiende que una relación de orden parcial
es reflexiva.
·
aristas
que se deducen de la transitividad de la relación.
DEFINICION:
·
De
dos miembros x e y de un conjunto parcialmente ordenado S que «y
sigue a x» si x ≤ y y no hay elemento de S entre x e y.
El orden parcial es
entonces precisamente la clausura transitiva de
la relación de seguir.
·
El diagrama
de Hasse de S se define como el conjunto de todos los pares
ordenados (x, y) tales que y sigue a x, es decir, el
diagrama de Hasse se puede identificar con la relación de seguir.
EJEMPLO:
Concretamente, uno
representa a cada miembro de S como un punto negro en la página y
dibuja una línea que vaya hacia arriba de x a y si y sigue
a x.
Por ejemplo, sea el
conjunto A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} (todos los
divisores de 60). Este conjunto está ordenado parcialmente por la relación
de divisibilidad. Su diagrama de Hasse
puede ser representado como sigue:
Por ejemplo, en el
diagrama de Hasse del poset de
todos los divisores de un número n, ordenados parcialmente por divisibilidad, n mismo
está en el tope del diagrama, el número 1 estaría en el
fondo, y los divisores más pequeños (primos) seguirían al elemento
inferior.
DIFICULTAD DE DIAGRAMA DE HASSE:
Las relaciones «seguir a» queda definida de modo único a partir de la
relación de orden inicial. Esto hace que las aristas del diagrama de Hasse y
los puntos que conectan queden determinados también de forma única. Pero existe
un problema adicional: encontrar una ubicación adecuada para los vértices que
pueda reflejar alguna de las simetrías subyacentes. En este sentido, encontrar
un buen diagrama es difícil.
Se han propuesto varios algoritmos para
dibujo de «buenos» diagramas, pero hoy en día su construcción sigue basándose
en una fuerte intervención humana. De hecho, incluso un humano necesita
bastante práctica para elaborarlos.
Los siguientes ejemplos corresponden a diagramas de Hasse de una misma
relación de orden:
|
|
|
|
|
|
1.
Escribir la relación como conjunto de
pares ordenados.
2. Consideremos el
conjunto A={1,2,3,4} con
la relación de orden ≤ usual.
3.
Dibujar el correspondiente diagrama
de Hasse.
4.
En el
conjunto A={a,b,c,d} se considera la
relación:≤={(a,a),(a,b),(b,b),(b,d),(a,c),(c,c),(c,d),(a,d),(d,d)}.
(2) Dibujar el diagrama de Hasse de la relación.
(3) Analizar si ≤ es un orden total.
(4) Determinar, si existen, los elementos máximo y mínimo.
6.
En el
conjunto A={a,b,c,d,e,f} se considera la relación de orden dada por
el diagrama de Hasse:
1.
(1) Analizar la existencia de máximo
y mínimo.
(2) Determinar los elementos maximales y minimales.
(3) Determinar los subconjuntos de A totalmente ordenados y con tres
elementos.
Solución
1.
Los pares (x,y) de la
relación, es decir los que satisfacen x≤y son:≤={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,d),(b,e),(c,c),(c,d),(c,e),(d,d),(e,e)}.
2.
Claramente es
3.
(1) Se comprueba de forma sencilla
que se verifican las propiedades, reflexiva, antisimétrica y transitiva.
(2) El diagrama de Hasse de ≤ es
(3) No es relación de orden total pues c≰b y b≰c.
(4) Para todo x∈A se verifica a≤x y x≤d, por tanto a es elemento mínimo y d máximo.
4.
(1) No existe elemento
de A mayor o igual que todos los demás, ni existe elemento
de A menor o igual que todos los demás, por tanto no existe ni máximo
ni mínimo.
(2) Los elementos maximales
de A son d, e y f pues son aquellos para los
que no hay ninguno mayor y los minimales son a y b pues son
aquellos para los que no hay ninguno menor.
(3) De acuerdo con la definición de orden total, los subconjuntos
de A con tres elementos y totalmente ordenados son
\{a,c,f\},\;\{a,c,e\},\;\{a,c,d\},\;\{b,c,f\},\;\{b,c,e\},\;\{b,c,d\}.
