stringtranslate.com

Diagrama de Hasse

El conjunto potencia de un conjunto de 2 elementos ordenado por inclusión

En teoría del orden , un diagrama de Hasse (/ˈhæsə / ; alemán : [ ˈhasə ] ) es un tipo de diagrama matemático utilizado para representar un conjunto parcialmente ordenado finito , en forma de un dibujo de su reducción transitiva . Concretamente, para un conjunto parcialmente ordenado se representa cada elemento de como un vértice en el plano y se dibuja un segmento de línea o curva que va hacia arriba desde un vértice a otro vértice siempre que cubra (es decir, siempre que , y no haya ningún distinto de y con ). Estas curvas pueden cruzarse entre sí, pero no deben tocar ningún vértice que no sean sus puntos finales. Un diagrama de este tipo, con vértices etiquetados, determina de forma única su orden parcial.

Los diagramas de Hasse reciben su nombre de Helmut Hasse (1898-1979); según Garrett Birkhoff , se llaman así debido al uso efectivo que Hasse hizo de ellos. [1] Sin embargo, Hasse no fue el primero en utilizar estos diagramas. Un ejemplo anterior a Hasse se puede encontrar en una obra de 1895 de Henri Gustave Vogt. [2] [3] Aunque los diagramas de Hasse se idearon originalmente como una técnica para hacer dibujos de conjuntos parcialmente ordenados a mano, más recientemente se han creado automáticamente utilizando técnicas de dibujo de gráficos . [4]

En algunas fuentes, la frase "diagrama de Hasse" tiene un significado diferente: el gráfico acíclico dirigido obtenido a partir de la relación de cobertura de un conjunto parcialmente ordenado, independientemente de cualquier dibujo de ese gráfico. [5]

Diseño de diagrama

Aunque los diagramas de Hasse son herramientas simples e intuitivas para trabajar con conjuntos finitos , resulta bastante difícil dibujar diagramas "buenos". La razón es que, en general, hay muchas formas posibles de dibujar un diagrama de Hasse para un conjunto determinado. La técnica simple de comenzar con los elementos mínimos de un orden y luego dibujar elementos mayores de manera incremental a menudo produce resultados bastante pobres: las simetrías y la estructura interna del orden se pierden fácilmente.

El siguiente ejemplo demuestra el problema. Considere el conjunto potencia de un conjunto de 4 elementos ordenados por inclusión . A continuación se muestran cuatro diagramas de Hasse diferentes para este orden parcial. Cada subconjunto tiene un nodo etiquetado con una codificación binaria que muestra si un determinado elemento está en el subconjunto (1) o no (0):

El primer diagrama deja claro que el conjunto potencia es un conjunto poset graduado . El segundo diagrama tiene la misma estructura graduada, pero al hacer que algunas aristas sean más largas que otras, enfatiza que el cubo de 4 dimensiones es una unión combinatoria de dos cubos de 3 dimensiones, y que un tetraedro ( politopo abstracto de 3 dimensiones ) fusiona de la misma manera dos triángulos ( politopos abstractos de 2 dimensiones ). El tercer diagrama muestra parte de la simetría interna de la estructura. En el cuarto diagrama, los vértices están dispuestos en una cuadrícula de 4 × 4.

Planaridad ascendente

Este diagrama de Hasse de la red de subgrupos del grupo diedro Dih 4 no tiene aristas que se crucen.

Si se puede dibujar un orden parcial como un diagrama de Hasse en el que no se cruzan dos aristas, se dice que su grafo de recubrimiento es plano ascendente . Se conocen varios resultados sobre la planaridad ascendente y sobre la construcción de diagramas de Hasse sin cruces:

Uso en notación UML

Un diagrama de clases que representa la herencia múltiple

En ingeniería de software / diseño orientado a objetos , las clases de un sistema de software y la relación de herencia entre estas clases a menudo se representan mediante un diagrama de clases , una forma de diagrama de Hasse en el que los bordes que conectan las clases se dibujan como segmentos de línea sólidos con un triángulo abierto en el extremo de la superclase.

Notas

  1. ^ Birkhoff (1948).
  2. ^ Vogt (1895).
  3. ^ Rival (1985), pág. 110.
  4. ^ Por ejemplo, véase Di Battista & Tamassia (1988) y Freese (2004).
  5. ^ Para ejemplos de este significado alternativo de los diagramas de Hasse, véase Christofides (1975, págs. 170-174); Thulasiraman y Swamy (1992); Bang-Jensen (2008)
  6. ^ Garg y Tamassia (1995a), Teorema 9, pág. 118; Baker, Fishburn y Roberts (1971), Teorema 4.1, página 18.
  7. ^ Garg y Tamassia (1995a), Teorema 15, p. 125; Bertolazzi et al. (1993).
  8. ^ Garg y Tamassia (1995a), Corolario 1, pág. 132; Garg y Tamassia (1995b).
  9. ^ Chan (2004).
  10. ^ Jünger y Leipert (1999).

Referencias

Enlaces externos