Диаграмма Хассе

Визуальное изображение частично упорядоченного множества

Мощность набора из 2 элементов, упорядоченная по включению

В теории порядка диаграмма Хассе ( / ˈ h æ s ə / ; нем. [ˈhasə] ) — это тип математической диаграммы, используемой для представления конечного частично упорядоченного множества в виде рисунка его транзитивного сокращения . Конкретно, для частично упорядоченного множества каждый элемент из представляется как вершина на плоскости и рисуется отрезок прямой или кривая, которая идет вверх от одной вершины к другой вершине всякий раз, когда покрывает (то есть всякий раз , когда , и нет отличий от и с ). Эти кривые могут пересекать друг друга, но не должны касаться никаких вершин, кроме своих конечных точек. Такая диаграмма с помеченными вершинами однозначно определяет свой частичный порядок. ${\displaystyle (S,\leq )}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x\neq y}$ ${\displaystyle x\leq y}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\leq z\leq y}$

Диаграммы Хассе названы в честь Хельмута Хассе (1898–1979); по словам Гаррета Биркгофа , они так называются из-за эффективного использования их Хассе. ^[1] Однако Хассе не был первым, кто использовал эти диаграммы. Один пример, который предшествовал Хассе, можно найти в работе 1895 года Анри Гюстава Фогта. ^{[2] [3]} Хотя диаграммы Хассе изначально были разработаны как метод для создания рисунков частично упорядоченных множеств вручную, в последнее время они создаются автоматически с использованием методов рисования графов . ^[4]

В некоторых источниках фраза «диаграмма Хассе» имеет иное значение: направленный ациклический граф, полученный из отношения покрытия частично упорядоченного множества, независимо от какого-либо рисунка этого графа. ^[5]

Проектирование диаграммы

Хотя диаграммы Хассе являются простыми и интуитивно понятными инструментами для работы с конечными частично упорядоченными множествами , оказывается, что рисовать «хорошие» диаграммы довольно сложно. Причина в том, что, в общем, существует много различных возможных способов нарисовать диаграмму Хассе для заданного частично упорядоченного множества. Простая техника, когда просто начинаешь с минимальных элементов порядка, а затем постепенно рисуешь все большие элементы, часто дает довольно плохие результаты: симметрии и внутренняя структура порядка легко теряются.

Следующий пример демонстрирует проблему. Рассмотрим набор мощности 4-элементного набора, упорядоченного включением . Ниже приведены четыре различные диаграммы Хассе для этого частичного порядка. Каждое подмножество имеет узел, помеченный двоичным кодом, который показывает, находится ли определенный элемент в подмножестве (1) или нет (0): ${\displaystyle \subseteq }$

Первая диаграмма ясно показывает, что набор степеней является градуированным посетом . Вторая диаграмма имеет ту же градуированную структуру, но делая некоторые ребра длиннее других, она подчеркивает, что 4-мерный куб является комбинаторным объединением двух 3-мерных кубов, и что тетраэдр ( абстрактный 3-многогранник ) аналогичным образом объединяет два треугольника ( абстрактные 2-многогранники ). Третья диаграмма показывает часть внутренней симметрии структуры. На четвертой диаграмме вершины расположены в сетке 4×4.

Восходящая плоскостность

Эта диаграмма Хассе решетки подгрупп диэдральной группы Dih ₄ не имеет пересекающихся ребер.

Если частичный порядок можно изобразить как диаграмму Хассе, в которой никакие два ребра не пересекаются, то его покрывающий граф называется восходящим планарным . Известен ряд результатов по восходящей планарности и по построению диаграмм Хассе без пересечений:

• Если частичный порядок, который нужно нарисовать, представляет собой решетку , то его можно нарисовать без пересечений тогда и только тогда, когда его размерность порядка не превышает двух. ^[6] В этом случае рисунок без пересечений можно найти, выведя декартовы координаты для элементов из их положений в двух линейных порядках, реализующих размерность порядка, а затем повернув рисунок против часовой стрелки на угол 45 градусов.
• Если частичный порядок имеет не более одного минимального элемента , или не более одного максимального элемента , то можно за линейное время проверить , имеет ли он непересекающуюся диаграмму Хассе. ^[7]
• Определение того, можно ли нарисовать частичный порядок с несколькими источниками и стоками в виде диаграммы Хассе без пересечений, является NP-полной задачей . ^[8] Однако нахождение диаграммы Хассе без пересечений является фиксированно-параметрической задачей , если параметризовано числом точек сочленения и трехсвязных компонентов транзитивной редукции частичного порядка. ^[9]
• Если указаны y -координаты элементов частичного порядка, то диаграмму Хассе без пересечений, соответствующую этим координатным назначениям, можно найти за линейное время, если такая диаграмма существует. ^[10] В частности, если входное частично упорядоченное множество является градуированным частично упорядоченным множеством , можно определить за линейное время, существует ли диаграмма Хассе без пересечений, в которой высота каждой вершины пропорциональна ее рангу.

Использование в нотации UML

Диаграмма классов, изображающая множественное наследование

В программной инженерии / объектно-ориентированном проектировании классы программной системы и отношения наследования между этими классами часто изображаются с помощью диаграммы классов , формы диаграммы Хассе, в которой ребра, соединяющие классы, изображаются в виде сплошных отрезков линий с открытым треугольником на конце суперкласса .

Примечания

1. Биркгоф (1948).
2. Фогт (1895).
3. Rival (1985), стр. 110.
4. Например, см. Ди Баттиста и Тамассия (1988) и Фриз (2004).
5. Примеры этого альтернативного значения диаграмм Хассе см. у Christofides (1975, стр. 170–174); Thulasiraman & Swamy (1992); Bang-Jensen (2008)
6. Гарг и Тамассиа (1995a), Теорема 9, стр. 118; Бейкер, Фишберн и Робертс (1971), Теорема 4.1, стр. 18.
7. Гарг и Тамассия (1995a), Теорема 15, с. 125; Бертолацци и др. (1993).
8. Гарг и Тамассиа (1995a), Следствие 1, стр. 132; Гарг и Тамассиа (1995b).
9. Чан (2004).
10. Юнгер и Лейперт (1999).

Ссылки

• Бейкер, Кирби А.; Фишберн, Питер К .; Робертс, Фред С. (1971), «Частичные порядки размерности 2», Networks , 2 (1): 11–28, doi :10.1002/net.3230020103
• Банг-Йенсен, Йорген (2008), «2.1 Ациклические орграфы», Орграфы: теория, алгоритмы и приложения , Springer Monographs in Mathematics (2-е изд.), Springer-Verlag, стр. 32–34, ISBN 978-1-84800-997-4
• Bertolazzi, R; Di Battista, G.; Mannino, C.; Tamassia, R. (1993), "Оптимальное тестирование восходящей планарности одноисточниковых орграфов" (PDF) , Proc. 1st European Symposium on Algorithms (ESA '93) , Lecture Notes in Computer Science , т. 726, Springer-Verlag, стр. 37–48, CiteSeerX  10.1.1.43.4879 , doi :10.1007/3-540-57273-2_42, ISBN 978-3-540-57273-2
• Биркгоф, Гарретт (1948), Теория решеток (пересмотренное издание), Американское математическое общество
• Чан, Хуберт (2004), «Параметризованный алгоритм для тестирования восходящей планарности», Труды 12-го Европейского симпозиума по алгоритмам (ESA '04) , Lecture Notes in Computer Science, т. 3221, Springer-Verlag, стр. 157–168, doi :10.1007/978-3-540-30140-0_16
• Христофидес, Никос (1975), Теория графов: алгоритмический подход , Academic Press, стр. 170–174
• Ди Баттиста, Г.; Тамассиа, Р. (1988), «Алгоритмы для плоского представления ациклических орграфов», Теоретическая информатика , 61 (2–3): 175–178, doi :10.1016/0304-3975(88)90123-5
• Freese, Ralph (2004), «Автоматизированное рисование решётки», Concept Lattices (PDF) , Lecture Notes in Computer Science, т. 2961, Springer-Verlag, стр. 589–590
• Гарг, Ашим; Тамассиа, Роберто (1995a), «Тестирование восходящей планарности», Order , 12 (2): 109–133, doi :10.1007/BF01108622, S2CID  14183717
• Гарг, Ашим; Тамассиа, Роберто (1995b), «О вычислительной сложности проверки восходящей и прямолинейной планарности», Graph Drawing (Proc. GD '94) , LectureNotes in Computer Science, т. 894, Springer-Verlag, стр. 286–297, doi : 10.1007/3-540-58950-3_384 , ISBN 978-3-540-58950-1
• Юнгер, Михаэль; Лейперт, Себастьян (1999), «Уровень планарного вложения за линейное время», Graph Drawing (Proc. GD '99) , Lecture Notes in Computer Science, т. 1731, стр. 72–81, doi : 10.1007/3-540-46648-7_7 , ISBN 978-3-540-66904-3
• Rival, Ivan (1985), «Диаграмма», в Rival, Ivan (ред.), Графы и порядок: роль графов в теории упорядоченных множеств и ее приложениях, Труды Института перспективных исследований НАТО, состоявшиеся в Банфе, 18–31 мая 1984 г. , Серия C Института перспективных научных исследований НАТО: Математические и физические науки, т. 147, Рейдель, Дордрехт, стр. 103–133, MR  0818494
• Туласираман, К.; Свами, МНС (1992), "5.7 Ациклические направленные графы", Графы: Теория и алгоритмы , John Wiley and Son, стр. 118, ISBN 978-0-471-51356-8
• Фогт, Анри Гюстав (1895), Leçons sur la resolution algébrique des équations , Nony, p. 91

Внешние ссылки

• Связанные медиа на Wikimedia Commons:
  • Диаграмма Хассе (Галерея)
  • Диаграммы Хассе (Категория)
• Вайсштейн, Эрик В. , «Диаграмма Хассе», MathWorld