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 finito parcialmente ordenado , 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 recta o curva que va hacia arriba de un vértice a otro siempre que cubre (es decir, siempre que , y no hay diferencia 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 llevan el nombre de Helmut Hasse (1898-1979); Según Garrett Birkhoff , se llaman así por el uso eficaz 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 Henri Gustave Vogt (1895). [2] Aunque los diagramas de Hasse se idearon originalmente como una técnica para hacer dibujos a mano de conjuntos parcialmente ordenados, más recientemente se han creado automáticamente utilizando técnicas de dibujo de gráficos . [3]
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í. [4]
Diseño de diagramas
Aunque los diagramas de Hasse son herramientas simples e intuitivas para trabajar con posets 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 poset determinado. La simple técnica de comenzar con los elementos mínimos de un orden y luego dibujar elementos mayores de forma 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 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 claro que el conjunto potencia 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 ( 3 politopo abstracto ) 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 en una cuadrícula de 4×4.
Si un orden parcial se puede dibujar como un diagrama de Hasse en el que no se cruzan dos aristas, se dice que su gráfico de cobertura es plano hacia arriba . Se conocen varios resultados sobre la planaridad ascendente y la construcción del diagrama de Hasse sin cruces:
Si el orden parcial que se va a dibujar es una red , entonces se puede dibujar sin cruces si y sólo si tiene una dimensión de orden como máximo dos. [5] En este caso, se puede encontrar un dibujo que no se cruce derivando las coordenadas cartesianas de los elementos a partir de sus posiciones en los dos órdenes lineales realizando 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 determinar si un orden 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 en tiempo lineal un diagrama de Hasse sin cruces que respete esas asignaciones de coordenadas, 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.
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ólida con una línea abierta. triángulo al final de la superclase.
Notas
^ Birkhoff (1948).
^ 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. 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. 132; Garg y Tamassia (1995b).
^ Chan (2004).
^ Jünger y Leipert (1999).
Referencias
Panadero, Kirby A.; Fishburn, Peter C .; Roberts, Fred S. (1971), "Órdenes parciales de dimensión 2", Redes , 2 (1): 11–28, doi :10.1002/net.3230020103
Bang-Jensen, Jørgen (2008), "2.1 Dígrafos acíclicos", Digrafos: 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. 12º Simposio Europeo sobre Algoritmos (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.
Di Battista, G.; Tamassia, R. (1988), "Algoritmos para la representación plana de dígrafos acíclicos", Ciencias de la Computación 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 (PDF) , Lecture Notes in Computer Science, vol. 2961, Springer-Verlag, págs. 589–590
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 rectilínea y ascendente", 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 plana de nivel en tiempo lineal", Dibujo de gráficos (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), "The diagrama", en Rival, Ivan (ed.), Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications, Actas del Instituto de Estudios Avanzados de la OTAN celebrada en Banff, 18 al 31 de mayo de 1984 , Serie C de Institutos de Ciencias Avanzadas de la OTAN: Ciencias físicas y matemáticas, vol. 147, Reidel, Dordrecht, págs. 103-133, SEÑOR 0818494
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
Vogt, Henri Gustave (1895), Leçons sur la résolution algébrique des équations , Nony, p. 91
Medios relacionados en Wikimedia Commons:
