Визуальное изображение частично упорядоченного множества.
Силовой набор двухэлементного набора, упорядоченного по включению
В теории порядка диаграмма Хассе ( / ˈh æ s ə / ; немецкий: [ ˈhasə] ) — это тип математической диаграммы , используемой для представления конечного частично упорядоченного множества в форме рисунка его транзитивной редукции . Конкретно, для частично упорядоченного множества каждый элемент представляет собой вершину на плоскости и рисует отрезок линии или кривую, идущую вверх от одной вершины к другой вершине всякий раз , когда она закрывает (то есть всякий раз, когда , и нет отличных от и с ). Эти кривые могут пересекать друг друга, но не должны касаться каких-либо вершин, кроме своих конечных точек. Такая диаграмма с помеченными вершинами однозначно определяет ее частичный порядок.
Диаграммы Хассе названы в честь Гельмута Хассе (1898–1979); по словам Гаррета Биркгоффа , они названы так из-за эффективного использования их Хассе. [1] Однако Хассе был не первым, кто использовал эти диаграммы. Один из примеров, предшествовавших Хассе, можно найти у Анри Гюстава Фогта (1895). [2] Хотя диаграммы Хассе изначально были разработаны как метод рисования частично упорядоченных множеств вручную, в последнее время они стали создаваться автоматически с использованием методов рисования графов . [3]
Фраза «диаграмма Хассе» может также относиться к транзитивной редукции как к абстрактному направленному ациклическому графу , независимо от какого-либо изображения этого графа, но здесь такое использование избегается. [4]
Дизайн диаграммы
Хотя диаграммы Хассе являются простыми и интуитивно понятными инструментами для работы с конечными частично упорядоченными множествами , нарисовать «хорошие» диаграммы оказывается довольно сложно. Причина в том, что, как правило, существует множество различных способов построения диаграммы Хассе для данного ЧУ-множества. Простой метод, заключающийся в том, что мы начинаем с минимальных элементов порядка, а затем постепенно рисуем более крупные элементы, часто дает весьма плохие результаты: симметрия и внутренняя структура порядка легко теряются.
Следующий пример демонстрирует проблему. Рассмотрим степенной набор 4-элементного набора, упорядоченного по включению . Ниже приведены четыре различные диаграммы Хассе для этого частичного порядка. Каждое подмножество имеет узел, помеченный двоичной кодировкой, которая показывает, входит ли определенный элемент в подмножество (1) или нет (0):
Первая диаграмма ясно показывает, что набор степеней является градуированным ЧУМ . Вторая диаграмма имеет такую же градуированную структуру, но, делая некоторые ребра длиннее других, она подчеркивает, что 4-мерный куб представляет собой комбинаторное объединение двух 3-мерных кубов, и что тетраэдр ( абстрактный 3-мерный многогранник ) аналогичным образом объединяет два треугольники ( абстрактные 2-многогранники ). Третья диаграмма демонстрирует некоторую внутреннюю симметрию конструкции. На четвертой диаграмме вершины расположены в сетке 4×4.
Восходящая планарность
Эта диаграмма Хассе решетки подгрупп группы диэдра Dih 4 не имеет пересекающихся ребер.
Если частичный порядок можно изобразить в виде диаграммы Хассе, в которой никакие два ребра не пересекаются, то его граф покрытия называется плоскостью вверх . Известен ряд результатов о восходящей планарности и построении беспересекающихся диаграмм Хассе:
Если рисуемый частичный порядок представляет собой решетку , то его можно нарисовать без пересечений тогда и только тогда, когда его размерность порядка не превышает двух. [5] В этом случае непересекающийся рисунок можно найти, выведя декартовы координаты элементов из их положений в двух линейных порядках, реализующих размерность порядка, а затем повернув рисунок против часовой стрелки на угол 45 градусов.
NP -полно , чтобы определить, можно ли изобразить частичный порядок с несколькими источниками и стоками в виде диаграммы Хассе без пересечений. [7] Однако найти диаграмму Хассе без пересечений с фиксированным параметром можно , если она параметризована количеством точек сочленения и трехсвязными компонентами транзитивной редукции частичного порядка. [8]
Если указаны координаты y элементов частичного порядка, то диаграмма Хассе без пересечений, учитывающая эти назначения координат, может быть найдена за линейное время, если такая диаграмма существует. [9] В частности, если входное ЧУУ является градуированным ЧУУ , можно за линейное время определить, существует ли диаграмма Хассе без пересечений, в которой высота каждой вершины пропорциональна ее рангу.
Ривал, Иван (1985), «Диаграмма», в книге Ривал, Иван (ред.), Графы и порядок: роль графов в теории упорядоченных множеств и ее приложениях, Труды Института перспективных исследований НАТО, проводимые в Банфе, 18–31 мая 1984 г. , Серия C Институтов передовых научных исследований НАТО: Математические и физические науки, том. 147, Райдель, Дордрехт, стр. 103–133, MR 0818494
Туласираман, К.; Свами, MNS (1992), «5.7 Ациклические ориентированные графы», Графы: теория и алгоритмы , Джон Вили и сын, стр. 118, ISBN 978-0-471-51356-8
Фогт, Анри Гюстав (1895), Leçons sur la resolution algébrique des équations , Nony, p. 91