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

Не путать с диаграммой Гесса .

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

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

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

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

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

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

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

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

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

Основная статья: Плоский рисунок вверх

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

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

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

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

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

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

Ссылки

• Бейкер, Кирби А.; Фишберн, Питер С .; Робертс, Фред С. (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), Уроки алгебраического разрешения уравнений , Нони, с. 91

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

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