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 ) de la misma manera fusiona 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.
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:
Si el orden parcial que se va a dibujar es una red , entonces se puede dibujar sin cruces si y solo si tiene una dimensión de orden de como máximo dos. [6] En este caso, se puede encontrar un dibujo sin cruces derivando las coordenadas cartesianas de los elementos a partir de sus posiciones en los dos órdenes lineales que realizan la dimensión de 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 como máximo un elemento máximo , entonces se puede probar en tiempo lineal si tiene un diagrama de Hasse sin cruces. [7]
Es NP-completo determinar si un orden parcial con múltiples fuentes y sumideros puede dibujarse como un diagrama de Hasse sin cruces. [8] Sin embargo, encontrar un diagrama de Hasse sin cruces es manejable con parámetros fijos cuando se parametriza mediante el número de puntos de articulación y componentes triconectados de la reducción transitiva del orden parcial. [9]
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 existe tal diagrama. [10] 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 sea proporcional a su rango.
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
^ Birkhoff (1948).
^ Vogt (1895).
^ Rival (1985), pág. 110.
^ Por ejemplo, véase Di Battista & Tamassia (1988) y Freese (2004).
^ 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)
^ Garg y Tamassia (1995a), Teorema 9, pág. 118; Baker, Fishburn y Roberts (1971), Teorema 4.1, página 18.
^ Garg y Tamassia (1995a), Teorema 15, p. 125; Bertolazzi et al. (1993).
^ Garg y Tamassia (1995a), Corolario 1, pág. 132; Garg y Tamassia (1995b).
^ Chan (2004).
^ 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
Bang-Jensen, Jørgen (2008), "2.1 Dígrafos acíclicos", Dígrafos: teoría, algoritmos y aplicaciones , Springer Monographs in Mathematics (2.ª ed.), Springer-Verlag, págs. 32–34, ISBN 978-1-84800-997-4
Chan, Hubert (2004), "Un algoritmo parametrizado para pruebas de planaridad ascendente", Proc. 12th European Symposium on Algorithms (ESA '04) , Lecture Notes in Computer Science, vol. 3221, Springer-Verlag, págs. 157–168, doi :10.1007/978-3-540-30140-0_16
Christofides, Nicos (1975), Teoría de grafos: un enfoque algorítmico , Academic Press, págs. 170-174
Di Battista, G.; Tamassia, R. (1988), "Algoritmos para la representación plana de dígrafos acíclicos", Theoretical Computer Science , 61 (2–3): 175–178, doi :10.1016/0304-3975(88)90123-5
Freese, Ralph (2004), "Dibujo de red automatizado", Concept Lattices (PDF) , Lecture Notes in Computer Science, vol. 2961, Springer-Verlag, págs. 589–590
Garg, Ashim; Tamassia, Roberto (1995a), "Prueba de planaridad ascendente", Order , 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, vol. 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", Graph Drawing (Proc. GD '99) , Lecture Notes in Computer Science, vol. 1731, págs. 72–81, doi : 10.1007/3-540-46648-7_7 , ISBN 978-3-540-66904-3
Rival, Ivan (1985), "El diagrama", en Rival, Ivan (ed.), Gráficos y orden: el papel de los gráficos en la teoría de conjuntos ordenados y sus aplicaciones, Actas del Instituto de Estudios Avanzados de la OTAN celebradas en Banff, del 18 al 31 de mayo de 1984 , NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, vol. 147, Reidel, Dordrecht, págs. 103-133, MR 0818494
Thulasiraman, K.; Swamy, MNS (1992), "5.7 Grafos dirigidos acíclicos", Grafos: teoría y algoritmos , John Wiley and Son, pág. 118, ISBN 978-0-471-51356-8
Vogt, Henri Gustave (1895), Leçons sur la résolution algébrique des équations , Nony, p. 91
Medios relacionados en Wikimedia Commons:
