В теории порядка , A Диаграмма Хассе ( / ч æ с ə / ; Немецкий: [hasə] ) представляет собой тип математической диаграммы используется для представления конечного частично упорядоченное множество , в виде рисунка ее переходной сокращения . Конкретно, для частично упорядоченного набора (S, ≤) каждый элемент S представляет собой вершину на плоскости и рисует отрезок линии или кривую, идущую вверх от x до y.всякий раз, когда y покрывает x (то есть, когда x ≤ y и не существует z такого, что x ≤ z ≤ y ). Эти кривые могут пересекать друг друга, но не должны касаться каких-либо вершин, кроме своих конечных точек. Такая диаграмма с помеченными вершинами однозначно определяет ее частичный порядок.
Диаграммы названы в честь Хельмута Хассе (1898–1979); согласно Гаррету Биркоффу ( 1948 ), они получили такое название из-за того, что Хассе эффективно их использовал. Однако Хассе не был первым, кто использовал эти диаграммы. Один пример, предшествующий Хассе, можно найти у Анри Густава Фогта ( 1895 г. ). Хотя диаграммы Хассе изначально создавались как метод рисования частично упорядоченных наборов вручную, в последнее время они были созданы автоматически с использованием методов рисования графиков . [1]
Фраза «диаграмма Хассе» может также относиться к транзитивной редукции как к абстрактному ориентированному ациклическому графу , независимо от любого рисунка этого графа, но это использование здесь избегается. [2] [3] [4]
"Хорошая" диаграмма Хассе
Хотя диаграммы Хассе являются простыми и интуитивно понятными инструментами для работы с конечными позициями , оказывается довольно сложно нарисовать «хорошие» диаграммы. Причина в том, что в целом будет много возможных способов нарисовать диаграмму Хассе для данного poset. Простая техника, состоящая в том, чтобы просто начать с минимальных элементов порядка, а затем постепенно рисовать более крупные элементы, часто дает довольно плохие результаты: легко теряются симметрии и внутренняя структура порядка.
Следующий пример демонстрирует проблему. Рассмотрим набор мощности четырехэлементного множества, упорядоченный по включению. Ниже представлены четыре различных диаграммы Хассе для этого частичного порядка. Каждое подмножество имеет узел, помеченный двоичной кодировкой, которая показывает, находится ли определенный элемент в подмножестве (1) или нет (0):
Первая диаграмма ясно показывает, что набор мощности - это градуированный набор . Вторая диаграмма имеет ту же ступенчатую структуру, но, сделав одни ребра длиннее других, она подчеркивает, что четырехмерный куб представляет собой комбинаторное объединение двух трехмерных кубов и что тетраэдр ( абстрактный 3-многогранник ) также объединяет два треугольники ( абстрактные 2-многогранники ). Третья диаграмма показывает некоторую внутреннюю симметрию конструкции. На четвертой диаграмме вершины расположены как элементы матрицы 4 × 4 .
Восходящая планарность
Если частичный порядок может быть изображен как диаграмма Хассе, в которой никакие два ребра не пересекаются, его граф покрытия называется направленным вверх плоским . Известен ряд результатов о восходящей планарности и построении бескроссельной диаграммы Хассе:
- Если частичный порядок, который нужно нарисовать, представляет собой решетку , то ее можно нарисовать без пересечений тогда и только тогда, когда она имеет размерность порядка не более двух. [5] В этом случае непересекающийся чертеж может быть найден путем получения декартовых координат для элементов из их положений в двух линейных порядках, реализующих размер порядка, а затем поворота чертежа против часовой стрелки на угол 45 градусов.
- Если частичный порядок имеет не более одного минимального элемента или не более одного максимального элемента , то можно проверить за линейное время , имеет ли он непересекающуюся диаграмму Хассе. [6]
- Это NP-полный, чтобы определить, может ли частичный порядок с несколькими источниками и стоками быть нарисован как диаграмма Хассе без перекрестков. [7] Тем не менее, нахождение диаграммы Хассе без перекрестков является управляемым с фиксированным параметром, если параметризовано количеством точек сочленения и трехсвязными компонентами транзитивной редукции частичного порядка. [8]
- Если y -координаты элементов частичного порядка заданы, то диаграмма Хассе без перекрестков, учитывающая эти назначения координат, может быть найдена за линейное время, если такая диаграмма существует. [9] В частности, если входной ч.у.м. является градуированным чумом , можно определить за линейное время, существует ли диаграмма Хассе без перекрестков, в которой высота каждой вершины пропорциональна ее рангу.
Нотация UML
Стандартная диаграмма для цепочки включений - это класс UML , связывающий множества отношением наследования. На рисунке показан вложенный набор сбора , C :
- B = {♠, ♥, ♦, ♣}; B 1 = {♠, ♥}; B 2 = {♦, ♣}; B 3 = {♣};
C = { B , B 1 , B 2 , B 3 }.
Заметки
- ^ Например, см. Di Battista & Tamassia (1988) и Freese (2004) .
- ^ Кристофидес, Никос (1975), Теория графов: алгоритмический подход , Academic Press, стр. 170–174.
- ^ Thulasiraman, K .; Свами, Миннесота (1992), «5.7 Ациклические ориентированные графы», Графы: теория и алгоритмы , Джон Уайли и сын, стр. 118, ISBN 978-0-471-51356-8.
- ^ Банг-Йенсен, Йорген (2008), «2.1 Ациклические орграфы», орграфы: теория, алгоритмы и приложения , Монографии Springer по математике (2-е изд.), Springer-Verlag, стр. 32–34, ISBN 978-1-84800-997-4.
- ^ Garg & Tamassia (1995a) , теорема 9, стр. 118; Бейкер, Фишберн и Робертс (1971) , теорема 4.1, стр. 18.
- ^ Garg & Tamassia (1995a) , теорема 15, стр. 125; Бертолацци и др. (1993) .
- ^ Garg & Tamassia (1995a) , следствие 1, стр. 132; Гарг и Тамассия (1995b) .
- ^ Чан (2004) .
- ^ Юнгер и 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. Первый Европейский симпозиум по алгоритмам (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 .