Si consideramos un árbol como un conjunto ordenado parcial, se convierte en un caso especial de un entramado de unión. Para un semilattice de unión, queremos poder calcular el límite superior mínimo (único) de dos elementos (más o menos) de manera eficiente. En el caso de un árbol, una estructura de datos que permitiría esto sería almacenar para cada elemento en el nodo correspondiente un puntero al padre y una medida de distancia a la raíz. (En realidad, un etiquetado basado en el tipo topológico generalmente usado para "una medida de distancia a la raíz", efectivamente, todo lo que se necesita es un orden parcial compatible que pueda evaluarse eficientemente).
Cada entramado de unión finita se puede representar como un conjunto de subconjuntos de un conjunto finito con contención como orden de modo que el límite superior mínimo esté dado por la unión de los conjuntos. Por lo tanto, representar cada elemento por un número finito de etiquetas y calcular el límite superior mínimo por la unión de las etiquetas correspondientes sería una posible estructura de datos. (Al observar el complemento, uno ve que también sería posible definir el límite superior mínimo como la intersección de las etiquetas correspondientes). Una estructura de datos mucho más común es simplemente usar una matriz para almacenar todos los resultados de "a <= b "o incluso todos los resultados de" join (a, b) ".
Sin embargo, usar esa estructura de datos para representar un árbol sería algo extraño. ¿Existen más estructuras de datos en forma de árbol para semilattices de unión, que aún permiten un cálculo (más o menos) eficiente del límite superior (único) menos mínimo de dos elementos? (¿Quizás algún tipo de gráfico acíclico dirigido con información adicional en los nodos similar a la medida de distancia a la raíz del árbol?)
fuente
Respuestas:
Esta publicación de blog sobre teoría de celosía tiene una sección de referencia útil, que contiene entre otras "Teoría de celosía con aplicaciones" de Vijay K. Garg. El Capítulo 2 "Representación de Posets" describe algunas estructuras de datos para representar posets, y discute cómo calcular la unión (x, y) utilizando dicha estructura de datos.
Las dos primeras estructuras de datos discutidas son la representación de la lista de adyacencia del gráfico de reducción transitiva (= diagrama de Hasse / relación de cobertura) y el gráfico de cierre transitivo (= relación poset). Una observación sobre las ventajas de usar un tipo topológico para etiquetar los nodos precede a esa discusión. Tenga en cuenta que las etiquetas de tipo topológico serían lo suficientemente buenas como "una medida de distancia a la raíz", que era una parte de la estructura de datos para un árbol en la pregunta.
Las otras representaciones discutidas son "Representación esquelética", "Representación matricial" y "Representación basada en dimensiones". La "Representación esquelética" es interesante y útil, pero se basa en una descomposición en cadena (= cualquiera) del poset. La "Representación matricial" puede parecer trivial, pero probablemente sea la mejor representación para la mayoría de los problemas prácticos. La "Representación basada en dimensiones" representa el poset como el subconjunto del producto cartesiano de órdenes lineales, pero calcular la representación mínima de este tipo es NP-hard.
En conclusión, la representación más realista de estos es la representación de la lista de adyacencia de la reducción transitiva junto con un etiquetado de los nodos por un tipo topológico (en lugar de "una medida de distancia a la raíz"). Esta es en realidad una de las representaciones utilizadas por Sage (la otra es la "Representación matricial").
fuente