Если рассматривать дерево как частичное упорядоченное множество, оно становится частным случаем полурешетки соединения. Для полурешетки соединения мы хотим иметь возможность эффективно вычислять (уникальную) наименьшую верхнюю границу двух элементов (более или менее). В случае дерева структура данных, которая позволила бы это, должна была бы хранить для каждого элемента в соответствующем узле указатель на родительский элемент и меру расстояния до корня. (На самом деле, маркировка, основанная на топологической сортировке, обычно используется для «измерения расстояния до корня», фактически все, что требуется, - это совместимый частичный порядок, который можно эффективно оценить).
Каждую конечную полурешетку соединения можно представить в виде набора подмножеств конечного множества с порядком включения в таком порядке, чтобы наименьшая верхняя граница определялась объединением множеств. Следовательно, представление каждого элемента с помощью конечного числа тегов и вычисление наименьшей верхней границы путем объединения соответствующих тегов будет одной из возможных структур данных. (Глядя на дополнение, можно увидеть, что определение наименьшей верхней границы в качестве пересечения соответствующих тегов также возможно.) Гораздо более распространенная структура данных заключается в простом использовании матрицы для хранения всех результатов "a <= b "или даже все результаты" join (a, b) ".
Однако использование такой структуры данных для представления дерева было бы странно. Существуют ли более древовидные структуры данных для полурешеток соединения, которые все еще позволяют (более или менее) эффективно вычислять (уникальную) наименьшую верхнюю границу двух элементов? (Может быть, какой-то ориентированный ациклический граф с дополнительной информацией в узлах, аналогичной меру расстояния до корня дерева?)
источник
Ответы:
В этом посте по теории решеток есть полезный справочный раздел, в котором, среди прочего, содержится «Теория решеток с приложениями» Виджея К. Гарга. Глава 2 «Представление представлений» описывает некоторые структуры данных для представления представлений и обсуждает, как вычислить соединение (x, y) с использованием такой структуры данных.
Обсуждаются первые две структуры данных: представление списка смежности графа переходного сокращения (= диаграмма Хассе / отношение покрытия) и графа транзитивного замыкания (= отношение poset). Замечание о преимуществах использования топологической сортировки для обозначения узлов предшествует этому обсуждению. Обратите внимание, что метки топологической сортировки были бы достаточно хороши как «мера расстояния до корня», которая была одной из частей структуры данных для дерева в вопросе.
Другими обсуждаемыми представлениями являются «Скелетное представление», «Матричное представление» и «Представление на основе размеров». «Скелетное представление» является интересным и полезным, но основано на (= любой) цепной декомпозиции poset. «Матричное представление» может показаться тривиальным, но оно, вероятно, будет лучшим представлением для большинства практических задач. «Представление на основе измерений» представляет собой подмножество декартового произведения линейных порядков, но вычисление минимального представления такого рода является NP-трудным.
В заключение, наиболее древовидным представлением этих представлений является представление списка смежности транзитивного сокращения вместе с маркировкой узлов топологическим видом (вместо «меры расстояния до корня»). На самом деле это одно из представлений, используемых Sage (другое - «матричное представление»).
источник