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

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

Силовой набор двухэлементного набора, упорядоченного по включению

В теории порядка диаграмма Хассе ( / ˈ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]

Дизайн диаграммы

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

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

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

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

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

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

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

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

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

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

Примечания

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

Рекомендации

• Бейкер, Кирби А.; Фишберн, Питер С .; Робертс, Фред С. (1971), «Частичные порядки размерности 2», Networks , 2 (1): 11–28, doi : 10.1002/net.3230020103
• Банг-Йенсен, Йорген (2008), «2.1 Ациклические орграфы», Орграфы: теория, алгоритмы и приложения , Монографии Springer по математике (2-е изд.), Springer-Verlag, стр. 32–34, ISBN 978-1-84800-997-4
• Бертолацци, Р; Ди Баттиста, Г.; Маннино, К.; Тамассиа, Р. (1993), «Оптимальное тестирование восходящей планарности орграфов с одним источником» (PDF) , Proc. 1-й Европейский симпозиум по алгоритмам (ESA '93) , Конспекты лекций по информатике , том. 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), «Параметризованный алгоритм проверки восходящей планарности», Proc. 12-й Европейский симпозиум по алгоритмам (ESA '04) , Конспекты лекций по информатике, том. 3221, Springer-Verlag, стр. 157–168, номер документа : 10.1007/978-3-540-30140-0_16.
• Кристофидес, Никос (1975), Теория графов: алгоритмический подход , Academic Press, стр. 170–174.
• Ди Баттиста, Г.; Тамассиа, Р. (1988), «Алгоритмы плоского представления ациклических орграфов», Theoretical Computer Science , 61 (2–3): 175–178, doi : 10.1016/0304-3975(88)90123-5
• Фриз, Ральф (2004), «Автоматическое рисование решетки», Concept Lattices (PDF) , Конспекты лекций по информатике, том. 2961, Springer-Verlag, стр. 589–590.
• Гарг, Ашим; Тамассиа, Роберто (1995a), «Тестирование восходящей планарности», Order , 12 (2): 109–133, doi : 10.1007/BF01108622, S2CID  14183717
• Гарг, Ашим; Тамассиа, Роберто (1995b), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», Рисование графика (Proc. GD '94) , LectureNotes in Computer Science, vol. 894, Springer-Verlag, стр. 286–297, номер документа : 10.1007/3-540-58950-3_384 , ISBN. 978-3-540-58950-1
• Юнгер, Майкл; Лейперт, Себастьян (1999), «Вложение уровней плоскостей в линейное время», Рисование графиков (Proc. GD '99) , Конспекты лекций по информатике, том. 1731, стр. 72–81, номер документа : 10.1007/3-540-46648-7_7 , ISBN. 978-3-540-66904-3
• Ривал, Иван (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

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

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