Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с диаграммой Гесса .
Набор мощности множества 2-элемента упорядочены по включению

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

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

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

"Хорошая" диаграмма Хассе [ править ]

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

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

Hypercubeorder binary.svg   Гиперкубики binary.svg   Hypercubestar binary.svg   Hypercubematrix binary.svg

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

Восходящая планарность [ править ]

Основная статья: восходящий плоский рисунок
Это Хассе схема решетки подгрупп в группе диэдра DIH 4 не имеет пересечения ребер.

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

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

Нотация UML [ править ]

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

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

B = {♠, ♥, ♦, ♣};     B 1 = {♠, ♥};   B 2 = {♦, ♣};   B 3 = {♣};
С = { В , В 1 , В 2 , В 3 }.

Примечания [ править ]

  1. ↑ Например, см. Di Battista & Tamassia (1988) и Freese (2004) .
  2. ↑ Кристофидес, Никос (1975), Теория графов: алгоритмический подход , Academic Press, стр. 170–174.
  3. ^ Туласираман, К .; Свами, MNS (1992), «5.7 Ациклические ориентированные графы», Графы: теория и алгоритмы , Джон Вили и сын, стр. 118, ISBN 978-0-471-51356-8.
  4. ↑ Bang-Jensen, Jørgen (2008), «2.1 Ациклические диграфы», диграфы: теория, алгоритмы и приложения , монографии Springer по математике (2-е изд.), Springer-Verlag, стр. 32–34, ISBN 978-1-84800-997-4.
  5. ^ Garg & Tamassia (1995a) , теорема 9, стр. 118; Бейкер, Фишберн и Робертс (1971) , теорема 4.1, стр. 18.
  6. ^ Garg & Tamassia (1995a) , теорема 15, стр. 125; Бертолацци и др. (1993) .
  7. ^ Garg & Tamassia (1995a) , следствие 1, стр. 132; Гарг и Тамассия (1995b) .
  8. ^ Чан (2004) .
  9. ^ Юнгер и Leipert (1999) .

Ссылки [ править ]

  • Бейкер, Кирби А .; Фишберн, Питер С .; Робертс, Фред С. (1971), «Частичные порядки измерения 2», Сети , 2 (1): 11–28, DOI : 10.1002 / net.3230020103.
  • Bertolazzi, R; Di Battista, G .; Mannino, C .; Tamassia, R. (1993), "Оптимальное тестирование восходящей планарности орграфов с одним источником" (PDF) , Proc. 1-й Европейский симпозиум по алгоритмам (ESA '93) , конспект лекций по информатике , 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 .