Diagrama de hasse

Un diagrama de Hasse  es un tipo de diagrama utilizado para representar un conjunto parcialmente ordenado finito como un dibujo de su contracción transitiva . Específicamente, para un conjunto parcialmente ordenado , el diagrama representa cada elemento como vértices en el plano y segmentos o curvas que suben de elemento a elemento si y no hay ningún elemento para el cual . Estas curvas pueden intersecarse, pero no deben pasar por vértices a menos que sean extremos de línea. Tal diagrama con vértices etiquetados define de manera única un orden parcial.

Por primera vez sistemáticamente, este tipo de visualización fue descrito por Birkhoff en 1948 [1] , también le dio el nombre en honor a Helmut Hasse , quien usó diagramas similares , sin embargo, tales dibujos también se encuentran en trabajos anteriores, por ejemplo, en el libro de texto del matemático francés Henri Vogt ( alemán:  Henri Vogt ) edición de 1895 [2] .

Conveniencia de diagramas

Aunque los diagramas de Hasse son una herramienta simple e intuitiva para trabajar con un conjunto finito parcialmente ordenado , es muy difícil dibujar un diagrama "bueno" y visualmente conveniente para un conjunto bastante no trivial debido a la gran cantidad de opciones de visualización posibles. La técnica simple de comenzar con los elementos más pequeños y dibujar los elementos superpuestos secuencialmente a menudo da malos resultados: las simetrías y las estructuras internas son fáciles de perder.

Por ejemplo, un booleano de un conjunto de cuatro elementos, ordenados por la operación de inclusión , se puede representar mediante cualquiera de los cuatro diagramas siguientes (cada subconjunto se proporciona con una etiqueta codificada en binario que indica si el elemento correspondiente está contenido en el subconjunto: 1, o no - 0):

El primer diagrama muestra la estructura de niveles. El segundo diagrama tiene la misma estructura de niveles, pero algunos de los bordes se alargan para enfatizar que el cubo 4D es la unión de dos cubos 3D. El tercer diagrama muestra cierta simetría interna. En el cuarto diagrama, los vértices están ordenados como una matriz de 4×4.

Planaridad

Algunas propiedades de las órdenes parciales con respecto a la planaridad de su diagrama de Hasse (es decir, la capacidad de dibujarlo sin cruce de bordes):

• Si un orden parcial es una red , entonces se puede dibujar sin intersecciones si y solo si la dimensión del orden es al menos dos [3] [4] .
• Si un orden parcial tiene al menos un elemento mínimo o máximo, entonces es posible verificar en tiempo lineal si existe un diagrama sin intersecciones [5] .
• Determinar si un orden parcial se puede representar mediante un diagrama de Hasse planar, en el caso general, un problema NP-completo [6] .
• Si se dan coordenadas de elementos de un orden parcial, entonces su diagrama de Hasse se puede encontrar en tiempo lineal , conservando las coordenadas dadas, si solo existe tal diagrama [7] . En particular, si el orden parcial tiene niveles, es posible determinar en tiempo lineal si existe un diagrama de Hasse sin intersecciones, en el que la altura de cada vértice es proporcional a su rango.

Notas

1. ↑ Birkhoff, 1948 .
2. ↑ Focht, 1895 .
3. ↑ Garg, Tamassia, 1995 , Teorema 9, p. 118.
4. ↑ Baker, Fishburne, Roberts 1971 , Teorema 4.1, p. Dieciocho.
5. ↑ Garg, Tamassia, 1995 , Teorema 15, p. 125.
6. ↑ Garg, Tamassia, 1995 , Corolario 1, p. 132.
7. ↑ Junger, Lipert, 1999 .

Literatura

• KA Baker, P. Fishburn, FS Roberts. Órdenes parciales de dimensión 2 // Redes. - 1971. - V. 2 , N º 1 . — P. 11–28 . -doi : 10.1002/ net.3230020103 . .
• G. Birkhoff. Teoría de la red. — 2do. — Sociedad Matemática Estadounidense , 1948. Traducción al ruso: G. Birkhoff . Teoría de estructuras / Per. M. I. Graeva. - 2ª ed. - M. : Literatura Extranjera, 1952. - 408 p.
• A. Garg, R. Tamassia. Prueba de planaridad ascendente // Orden. - 1995. - T. 12 , N º 2 . — S. 109–133 . -doi : 10.1007/ BF01108622 . .
• R. Freese. Dibujo de celosía automatizado  // Concept Lattice. - Springer-Verlag, 2004. - T. 2961 . — S. 589–590 . .
• M. Junger, S. Leipert. Incrustación planar de nivel en tiempo lineal // Proc. del Simposio Internacional de Dibujo Gráfico GD '99. - 1999. - T. 1731 . — S. 72–81 . — ISBN 978-3-540-66904-3 . -doi : 10.1007/ 3-540-46648-7_7 .
• HG Vogt. Lecons sur la resolution algebrique des équations. - Nony, 1895. - S. 91.

Enlaces

• Weisstein, Eric W. Hasse Diagram  (inglés) en el sitio web de Wolfram MathWorld .