reticulados

Unidad V. Reticulados
Teoría de grafos 2-2010
Ing. Josmary Fernández

Ordenamiento de los elementos
UNEFA Núcleo Mérida
Ing. Lucileima Rosales

Ordenación parcial
Un orden parcial es una relación binaria R sobre un conjunto X, que cumple las
propiedades:
• Reflexiva: R es reflexiva sii para todo a ∈A aRa
• Antisimétrica: R es antisimétrica sii para todo a, b ∈A, existe aRb y a!=bentonces
bRa no ∈
• Transitiva: R es transitiva sii para todo a, b, c ∈A, existe aRb y bRc entonces ∈aRc
Conjunto parcialmente ordenado
Un conjunto con un orden parcial se denomina conjunto parcialmente ordenado o poset.
Formalmente, un conjunto parcialmente ordenado (c.p.o.) es un par (X,≤) donde ≤ es un
orden parcial en X.
Usualmente se usa la notación de "≤" en lugar de "R" para el ordenparcial.
Observación:
Si (X, ≤) es un c.p.o., dos elementos x, y ∈ X son comparables si x≤y o y≤x.
Si todos los pares de elementos de X son comparables entonces se dice que ≤ es un orden
lineal (o total) y que (X, ≤) es un conjunto linealmente ordenado.
Ejemplos:
• El conjunto de los naturales con su orden usual (la relación menor o igual). Este
orden es además un orden total.
• El conjuntode los enteros con su orden usual. Este orden es también total.
• Un subconjunto finito {1, 2,..., n} de los naturales. Este orden es también total.
• El conjunto de naturales ordenado por la relación de divisibilidad.
Ejercicio:
Sea T={a,b,c,d,e,f,g} la lista de tareas para realizar un trabajo, de las que se sabe que unas
preceden inmediatamente a otras de la siguiente forma: f≤a, f≤d, e≤b,c≤f, e≤c, b≤f,
e≤g,g≤f. Hallar el orden parcial. ¿Qué tareas pueden realizarse independientemente?.
Construir un orden si el trabajo lo realiza sólo una persona.
Diagrama de Hasse
El diagrama de Hasse de un conjunto ordenado finito es una representación del mismo en la
que cada elemento se representa por un punto del plano. Si aRb se dibuja a por debajo y se
une por medio de un segmento.Finalmente se suprimen los segmentos que corresponden a
la propiedad transitiva, es decir, si aRb y bRc se suprime el segmento correspondiente a
aRc.

Unidad V. Reticulados
Teoría de grafos 2-2010
Ing. Josmary Fernández

Ordenamiento de los elementos
UNEFA Núcleo Mérida
Ing. Lucileima Rosales

Ejemplos:
1.- Consideramos el conjunto ordenado {1,2}. Entonces el diagrama de Hasse sería:Figura 1. Diagrama de Hasse para el conjunto {1,2}

2.- Diagramas de Hasse del conjunto ordenado {1,2,3}:

Figura 2. Diagrama de Hasse para el conjunto {1,2}

3.- Diagramas de Hasse del conjunto ordenado D(30).

Figura 3. Diagrama de Hasse para el conjunto D(30)

Ejercicios:
Representar el diagrama de Hasse de los siguientes conjuntos ordenados y hallar los
elementos
notables
de
lossubconjuntos
señalados:
a) (D60, | ), A={2,5,6,10,12,30} y B={2,3,6,10,15,30}
b) (D48, | ), A={2,4,6,12} y B={3,6,8,16}
c) (D40, | ), A={4,5,10} y B={2,4,8,20}
Elementos maximales y minimales
Sea (X; ≤) un conjunto ordenado:
1. Un elemento x∈X se dice que es maximal, si no existe y∈X tal que x≤y y x!=y.
2. Un elemento x∈X se dice que es minimal, si no existe y∈X tal que y≤x y x!=y.Unidad V. Reticulados
Teoría de grafos 2-2010
Ing. Josmary Fernández

Ordenamiento de los elementos
UNEFA Núcleo Mérida
Ing. Lucileima Rosales

Ejemplo:
Para el diagrama de Hasse de la Figura 4, señale los elementos maximales y minimales.

Figura 4. Diagrama de Hasse para el conjunto {a,b,c,d,e,f,g,h,i,j}

Con este orden definido, se tiene que:
h≤e pues tenemos un camino h-f-e queempieza en h y termina en e.
i ≤a, pues el camino i-g-d-a que empieza en i y termina en a.
i ¬ ≤ e, pues ningún camino empieza en i y termina en e.
Se tiene además, que a y b son elementos maximales, pues no hay ningún elemento que sea
mayor que ellos. Por su parte, el elemento j es un elemento minimal.
Ejercicios:
Hallar los elementos maximales y minimales para los conjuntos con el orden...