Диаграмма Хассе - Hasse diagram

Набор мощности множества 2-элемента упорядочены по включению

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

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

Фраза «диаграмма Хассе» может также относиться к транзитивной редукции как к абстрактному ориентированному ациклическому графу , независимо от любого рисунка этого графа, но это использование здесь избегается.

Схема дизайна

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

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

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

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

Это Хассе схема решетки подгрупп в группе диэдра DIH ₄ не имеет пересечения ребер.

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

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

Нотация UML

Выражение примера с помощью стандартных соединителей наследования UML. Каждый набор представляет собой отдельный объект (стандартные блоки UML имеют прямоугольную форму).

Стандартная диаграмма для цепочки включений - это класс UML , связывающий множества отношением наследования. На рисунке показан вложенный набор сбора , C :

B = {♠, ♥, ♦, ♣};     B ₁ = {♠, ♥};   B ₂ = {♦, ♣};   B ₃ = {♣};
C = { B , B ₁ , B ₂ , B ₃ }.

Примечания

использованная литература

• Бейкер, Кирби А .; Фишберн, Питер К .; Робертс, Фред С. (1971), «Частичные порядки измерения 2», Сети , 2 (1): 11–28, DOI : 10.1002 / net.3230020103.
• Bertolazzi, R; Di Battista, G .; Mannino, C .; Tamassia, R. (1993), "Оптимальное тестирование восходящей планарности орграфов с одним источником" (PDF) , Proc. Первый Европейский симпозиум по алгоритмам (ESA '93) , Lecture Notes в области компьютерных наук , 726 ., Springer-Verlag, стр 37-48, 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, doi : 10.1007 / 978-3-540-30140-0_16.
• Di Battista, G .; Тамассия, Р. (1988), «Алгоритмы для плоского представления ациклических орграфов», Теоретическая информатика , 61 (2–3): 175–178, DOI : 10.1016 / 0304-3975 (88) 90123-5.
• Freese, Ralph (2004), «Автоматизированное рисование решеток», Concept Lattices , Lecture Notes in Computer Science, 2961 , Springer-Verlag, pp. 589–590. Расширенный препринт доступен на сайте: [1] .
• Гарг, Ашим; Tamassia, Роберто (1995a), "Восходящее испытание плоскостности", заказ , 12 (2): 109-133, DOI : 10.1007 / BF01108622 , S2CID  14183717.
• Гарг, Ашим; Тамассия, Роберто (1995b), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», Graph Drawing (Proc. GD '94) , LectureNotes in Computer Science, 894 , Springer-Verlag, pp. 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 , pp. 72–81, doi : 10.1007 / 3-540-46648- 7_7 , ISBN 978-3-540-66904-3.
• Фогт, Анри Густав (1895), Leçons sur la résolution algébrique des équations , Nony, p. 91.

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

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