Diagrama de Hasse

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

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

Los diagramas llevan el nombre de Helmut Hasse (1898-1979); según Garrett Birkhoff  ( 1948 ), se denominan así por el uso eficaz que Hasse hizo de ellos. Sin embargo, Hasse no fue el primero en utilizar estos diagramas. Un ejemplo anterior a Hasse se puede encontrar en Henri Gustav Vogt ( 1895 ). 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 . ^[1]

La frase "diagrama de Hasse" también puede referirse a la reducción transitiva como un gráfico acíclico dirigido abstracto , independientemente de cualquier dibujo de ese gráfico, pero este uso se evita aquí. ^{[2] [3] [4]}

Un diagrama de Hasse "bueno"

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

El siguiente ejemplo demuestra el problema. Considere el conjunto de potencias de un conjunto de 4 elementos ordenados por inclusión${\displaystyle \subseteq }$. A continuación se muestran cuatro diagramas de Hasse diferentes para este pedido 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 en claro que el conjunto de potencias es un poset graduado . El segundo diagrama tiene la misma estructura graduada, pero al hacer algunos bordes más largos que otros, 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 ) también fusiona dos triángulos ( 2-politopos abstractos ). El tercer diagrama muestra parte de la simetría interna de la estructura. En el cuarto diagrama, los vértices están dispuestos como los elementos de una matriz de 4 × 4 .

Planaridad ascendente

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

Si se puede dibujar un orden parcial como un diagrama de Hasse en el que no se cruzan dos bordes, se dice que su gráfico de cobertura es plano hacia arriba . Se conocen varios resultados sobre la planaridad hacia arriba y sobre la construcción del diagrama de Hasse sin cruces:

• Si el orden parcial que se dibujará es una celosía , entonces se puede dibujar sin cruces si y solo si tiene una dimensión de orden como máximo dos. ^[5] En este caso, se puede encontrar un dibujo que no se cruza derivando las coordenadas cartesianas de los elementos a partir de sus posiciones en los dos órdenes lineales, obteniendo la dimensión del orden, y luego girando el dibujo en sentido antihorario en un ángulo de 45 grados.
• Si el orden parcial tiene como máximo un elemento mínimo , o tiene como máximo un elemento máximo , entonces se puede probar en tiempo lineal si tiene un diagrama de Hasse que no se cruza. ^[6]
• Es NP-completo para determinar si un pedido parcial con múltiples fuentes y sumideros se puede dibujar como un diagrama de Hasse sin cruces. ^[7] Sin embargo, encontrar un diagrama de Hasse sin cruces es manejable con parámetros fijos cuando se parametriza por el número de puntos de articulación y componentes triconectados de la reducción transitiva del orden parcial. ^[8]
• Si se especifican las coordenadas y de los elementos de un orden parcial, entonces se puede encontrar un diagrama de Hasse sin cruces que respete esas asignaciones de coordenadas en tiempo lineal, si tal diagrama existe. ^[9] En particular, si el poset de entrada es un poset graduado , es posible determinar en tiempo lineal si existe un diagrama de Hasse sin cruces en el que la altura de cada vértice es proporcional a su rango.

Notación UML

Expresando el ejemplo mediante conectores de herencia UML estándar. Cada conjunto es un objeto distinto (las cajas UML estándar son rectangulares).

El diagrama estándar para una cadena de inclusiones es la clase UML , que conecta conjuntos por la relación de herencia. La ilustración muestra una colección de conjuntos anidada , C :

B = {♠, ♥, ♦, ♣};     B ₁ = {♠, ♥};   B ₂ = {♦, ♣};   B ₃ = {♣};
C = { B , B ₁ , B ₂ , B ₃ }.

Notas

1. Por ejemplo, véase Di Battista & Tamassia (1988) y Freese (2004) .
2. Christofides, Nicos (1975), Teoría de grafos: un enfoque algorítmico , Academic Press, págs. 170-174.
3. Thulasiraman, K .; Swamy, MNS (1992), "5.7 Gráficos dirigidos acíclicos", Gráficos: teoría y algoritmos , John Wiley and Son, p. 118, ISBN 978-0-471-51356-8.
4. Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs", Digraphs: Theory, Algorithms and Applications , Springer Monographs in Mathematics (2da ed.), Springer-Verlag, pp. 32-34, ISBN 978-1-84800-997-4.
5. Garg y Tamassia (1995a) , Teorema 9, p. 118; Baker, Fishburn y Roberts (1971) , teorema 4.1, página 18.
6. Garg y Tamassia (1995a) , Teorema 15, p. 125; Bertolazzi y col. (1993) .
7. Garg y Tamassia (1995a) , Corolario 1, p. 132; Garg y Tamassia (1995b) .
8. Chan (2004) .
9. Jünger y Leipert (1999) .

Referencias

• Baker, Kirby A .; Fishburn, Peter C .; Roberts, Fred S. (1971), "Órdenes parciales de dimensión 2", Networks , 2 (1): 11-28, doi : 10.1002 / net.3230020103.
• Bertolazzi, R; Di Battista, G .; Mannino, C .; Tamassia, R. (1993), "Prueba de planaridad ascendente óptima de dígrafos de fuente única" (PDF) , Proc. 1er Simposio Europeo sobre Algoritmos (ESA '93) , Lecture Notes in Computer Science , 726 , Springer-Verlag, págs. 37–48, doi : 10.1007 / 3-540-57273-2_42 , ISBN 978-3-540-57273-2.
• Birkhoff, Garrett (1948), Lattice Theory (edición revisada), American Mathematical Society .
• Chan, Hubert (2004), "Un algoritmo parametrizado para pruebas de planaridad ascendente", Proc. 12º Simposio Europeo de Algoritmos (ESA '04) , Lecture Notes in Computer Science, 3221 , Springer-Verlag, págs. 157-168, doi : 10.1007 / 978-3-540-30140-0_16.
• Di Battista, G .; Tamassia, R. (1988), "Algoritmos para la representación plana de dígrafos acíclicos", Informática teórica , 61 (2-3): 175-178, doi : 10.1016 / 0304-3975 (88) 90123-5.
• Freese, Ralph (2004), "Dibujo de celosía automatizado", Concept Lattices , Lecture Notes in Computer Science, 2961 , Springer-Verlag, págs. 589–590. Una preimpresión ampliada está disponible en línea: [1] .
• Garg, Ashim; Tamassia, Roberto (1995a), "Prueba de planaridad ascendente", Orden , 12 (2): 109-133, doi : 10.1007 / BF01108622 , S2CID  14183717.
• Garg, Ashim; Tamassia, Roberto (1995b), "Sobre la complejidad computacional de las pruebas de planaridad ascendente y rectilínea", Graph Drawing (Proc. GD '94) , LectureNotes in Computer Science, 894 , Springer-Verlag, págs. 286-297, doi : 10.1007 / 3-540-58950-3_384 , ISBN 978-3-540-58950-1.
• Jünger, Michael; Leipert, Sebastian (1999), "Incrustación planar de nivel en tiempo lineal", Dibujo de gráficos (Proc. GD '99) , Lecture Notes in Computer Science, 1731 , págs. 72–81, doi : 10.1007 / 3-540-46648- 7_7 , ISBN 978-3-540-66904-3.
• Vogt, Henri Gustav (1895), Leçons sur la résolution algébrique des équations , Nony, p. 91.

enlaces externos

• Medios relacionados en Wikimedia Commons:
  • Diagrama de Hasse (Galería)
  • Diagramas de Hasse (Categoría)
• Weisstein, Eric W. "Diagrama de Hasse" . MathWorld .