Diagrama de Hasse

El diagrama de Hasse es un grafo especial para la representación intuitiva de órdenes parciales. Su propósito es mostrar simplemente qué elementos están directamente relacionados en el ordenamiento.

Definición

El diagrama de Hasse de un conjunto parcialmente ordenado (A, ≤) es un grafo en el que:

• Los elementos del conjunto aparecen como vértices.
• Si a ≤ b, entonces en el grafo, el vértice a se coloca debajo de b.
• Dibujamos una arista solo si a ≤ b es verdadero, pero no hay un elemento intermedio c para el que a ≤ c y c ≤ b (es decir, hay una conexión directa entre a y b).
• Las aristas se dibujan hacia arriba de elementos inferiores a superiores.

Cómo Construir un Diagrama de Hasse

• Coloca los elementos mínimos (aquellos sin elementos más pequeños) en la parte inferior.
• Coloca los elementos máximos (aquellos sin elementos más grandes) en la parte superior.
• Dibuja aristas dirigidas (generalmente hacia arriba) solo para relaciones de cobertura (sucesores directos).
• Ordena los vértices para que el orden sea visualmente claro, sin aristas cruzadas si es posible.

Ejemplo

Sea A = {1,2,3,6}, con la relación de divisibilidad (|).

El orden parcial: 1 | 2, 1 | 3, 2 | 6, 3 | 6.

El diagrama de Hasse: 1 en la parte inferior, encima 2 y 3 (paralelos), y 6 en la parte superior conectado a ambos 2 y 3.

Propiedades

• El diagrama de Hasse es siempre un grafo acíclico dirigido (DAG).
• Las aristas reflexivas (a → a) no se representan.
• Las conexiones transitivas (si a ≤ b y b ≤ c, entonces a ≤ c) no se dibujan por separado, ya que las aristas solo muestran conexiones directas.
• El diagrama de Hasse hace visible fácilmente la jerarquía del orden parcial.

Resumen

Usando el diagrama de Hasse, podemos representar un orden parcial de manera simple y overviewable. Solo muestra conexiones directas, omitiendo aristas reflexivas y transitivas. Esto hace fácilmente visible la jerarquía de los elementos del conjunto.

Ejercicio de Práctica