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

Диаграмма Ха́ссе, или диаграмма покрытий^[1] — вид диаграмм, используемый для представления (обычно конечного) частично упорядоченного множества в виде рисунка его транзитивного сокращения. Конкретно, для частично упорядоченного множества ${\displaystyle (S,\leqslant )}$ диаграмма представляет каждый элемент ${\displaystyle S}$ как вершины на плоскости и отрезки или кривые, идущие вверх от элемента ${\displaystyle x}$ к элементу ${\displaystyle y}$, если ${\displaystyle x\leqslant y}$ и не существует элемента ${\displaystyle z}$, для которого ${\displaystyle x<z<y}$. Эти кривые могут пересекаться, но не должны проходить через вершины, если только они не являются концами линии. Такая диаграмма с помеченными вершинами однозначно определяют частичный порядок.

Другими словами, на диаграмме Хассе решётки маленькими окружностями ○ представлены его элементы, а соединение отрезком двух элементов означает, что один элемент покрывает другой, причём покрывающий элемент рисуется выше^[2].

Диаграммы «бесконечных» решёток всегда наделяются комментариями при их описании^[2].

На диаграмме Хассе наглядно видна структура частично упорядоченного множества, а также все связи между его элементами: хорошо просматриваются максимальные и минимальные элементы, ясно представлена каждая цепь, соединяющая два данных элемента, и так далее. Один элемент меньше другого тогда и только тогда, когда на диаграмме Хассе между ними существует восходящая ломаная^[3].

Впервые систематически такого рода визуализация описана Биркгофом в 1948 году^[4], им же дано название в честь использовавшего подобные диаграммы Хельмута Хассе, однако такого рода рисунки встречаются и в более ранних трудах, например, в учебнике французского математика Анри Фохта (нем. Henri Vogt) 1895 года издания^[5].

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

Например, множество всех подмножеств множества из четырёх элементов, упорядоченного операцией включения ${\displaystyle \subseteq }$, может быть представлен любой из четырёх нижеприведённых диаграмм (каждое подмножество снабжено меткой с бинарной кодировкой, показывающей, содержится соответствующий элемент в подмножестве — 1, или нет — 0):

Диаграммы Хассе решётки множества всех подмножеств 4-элементного множества
Структура уровней	Четырёхмерный куб
Внутренняя симметрия	Матрица ${\displaystyle 4\times 4}$

Первая диаграмма демонстрирует структуру уровней. Вторая диаграмма имеет ту же структуру уровней, но на ней некоторые рёбра удлинены, чтобы подчеркнуть, что четырёхмерный куб является объединением двух трёхмерных. Третья диаграмма показывает некоторую внутреннюю симметрию. В четвёртой диаграмме вершины упорядочены подобно матрице ${\displaystyle 4\times 4}$.

Плоская диаграмма Хассе — диаграмма без пересечения линий^[2].

Оптимальная диаграмма Хассе — диаграмма, имеющая минимальное количество пересекающихся пар линий^[2].

Некоторые свойства частичных порядков относительно планарности их диаграммы Хассе.

• Если частичный порядок является решёткой, то его можно нарисовать без пересечений тогда и только тогда, когда размерность порядка не менее двух^[6][7].
• Если частичный порядок имеет по меньшей мере один минимальный или максимальный элемент, то можно за линейное время проверить, существует ли диаграмма без пересечений^[8].
• Определить, можно ли частичный порядок представить планарной диаграммой Хассе, в общем случае — NP-полная задача^[9].
• Если заданы ${\displaystyle y}$-координаты элементов частичного порядка, то за линейное время может быть найдена его диаграмма Хассе, сохраняющая заданные координаты, если только такая диаграмма существует^[10]. В частности, если частный порядок имеет уровни, можно за линейное время определить, имеется ли диаграмма Хассе без пересечений, у которой высота каждой вершины пропорциональна её рангу.

Диаграмма Хассе не является графом, потому на диаграмме что имеется фиксация уровня элементов в частично упорядоченном множестве^[3].

Модифицированная диаграмма Хассе — ориентированный граф, который получается из диаграммы Хассе ориентацией её отрезков в направлении от меньшего элемента к большему^[3].

Модифицированная диаграмма Хассе не только показывает все данные исходной диаграммы, но и представляет собой граф, дающий новые возможности для исследования особенностей представляемого частично упорядоченного множества^[11].

• Диаграммы множества всех подмножеств трёхэлементного множества
• Диаграмма Хассе
• Модифицированная диаграмма Хассе

В любом частично упорядоченном множестве элемент ${\displaystyle b}$ больше или равен элементу ${\displaystyle a}$ в том и только в том случае, если вершина ${\displaystyle b}$ графа, отвечающего данному упорядоченному множеству, достижима из вершины ${\displaystyle a}$. Другими словами, отношение порядка в частично упорядоченном множестве совпадает с отношением достижимости в графе. Графы, соответствующие частично упорядоченным множествам, не имеют контуров, даже тривиальных — двунапраленных рёбер^[11].

Но не любой бесконтурный орграф есть граф какого-нибудь частично упорядоченного множества. Ведь если в частично упорядоченном множестве элемент ${\displaystyle b}$ — верхний сосед ${\displaystyle a}$, то в орграфе, отвечающем этому множеству, от вершины ${\displaystyle a}$ до ${\displaystyle b}$ существует только один ориентированный путь — ребро ${\displaystyle (a,\,b)}$. Этим самым в таком орграфе невозможны почти контуры — графы, которые получаются из контуров путём смены ориентации одного ребра^[11].

Орграф, соответствующий двойственному частично упорядоченному множеству, можно построить из орграфа исходного частично упорядоченного множества переориентацией всех его рёбер. Тогда источники орграфа — минимальные элементы — становятся стоками — максимальными элементами, и, соответственно, наоборот.

1. ↑ Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры, 2013, 3.1. Предпорядки и порядки, с. 80.
2. ↑ ^{1 2 3 4} Гретцер Г. Общая теория решёток, 1982, Глава I. Начальные понятия. § 2. Как описывать решётки, с. 27.
3. ↑ ^{1 2 3} Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем, 1997, § 1.4. Упорядоченные множества, с. 74.
4. ↑ Биркгоф, 1948.
5. ↑ Фохт, 1895.
6. ↑ Гарг, Тамассия, 1995, Theorem 9, p. 118.
7. ↑ Бейкер, Фишбёрн, Робертс, 1971, Theorem 4.1, p. 18.
8. ↑ Гарг, Тамассия, 1995, Theorem 15, p. 125.
9. ↑ Гарг, Тамассия, 1995, Corollary 1, p. 132.
10. ↑ Юнгер, Липерт, 1999.
11. ↑ ^{1 2 3} Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем, 1997, § 1.4. Упорядоченные множества, с. 75.

• Богомолов А. М, Салий В. Н. Алгебраические основы теории дискретных систем (рус.). — М.: Наука. Физматлит, 1997. — 368 с., ил. — ISBN 5-02-015033-9.
• Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры (рус.). — 2-е изд. — М.: URSS : Книжный дом «Либроком», 2013. — 221 с., ил. — (Основы защиты информации. Секретно для пользы = Secreto ad utilitatem). — ISBN 978-5-397-03899-7.
• Гретцер Г.. Общая теория решёток = George Grätzer. General Lattice Theory (1978) (рус.) / Пер. с англ. А. Д. Больбота, В. А. Горбунова и В. И. Туманова под ред. Д. М. Смирнова. — М.: «Мир», 1982. — 452 с.: ил. — 6000 экз.
• Лекция 3. Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.
• K. A. Baker, P. Fishburn, F. S. Roberts. Partial orders of dimension 2 // Networks. — 1971. — Т. 2, № 1. — С. 11–28. — doi:10.1002/net.3230020103..
• G. Birkhoff. Lattice Theory. — 2nd. — American Mathematical Society, 1948.

  Перевод на русский: Г. Биркгоф. Теория структур / Пер. М. И. Граева. — 2-е изд.. — М.: Иностранная литература, 1952. — 408 с.

• A. Garg, R. Tamassia. Upward planarity testing // Order. — 1995. — Т. 12, № 2. — С. 109–133. — doi:10.1007/BF01108622..
• R. Freese. Automated lattice drawing // Concept Lattices. — Springer-Verlag, 2004. — Т. 2961. — С. 589–590..
• M. Jünger, S. Leipert. Level planar embedding in linear time // Proc. of International Symposium on Graph Drawing GD ’99. — 1999. — Т. 1731. — С. 72–81. — ISBN 978-3-540-66904-3. — doi:10.1007/3-540-46648-7_7.
• H. G. Vogt. Leçons sur la résolution algébrique des équations. — Nony, 1895. — С. 91.

• Weisstein, Eric W. Hasse Diagram (англ.) на сайте Wolfram MathWorld.