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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Диаграмма Хассе — вид диаграмм, используемый для представления конечного частично упорядоченного множества в виде рисунка его транзитивного сокращения. Конкретно, для частично упорядоченного множества (S, \le) диаграмма представляет каждый элемент S как вершины на плоскости и отрезки или кривые, идущие вверх от элемента x к элементу y, если x \le y и не существует элемента z, для которого x \le z \le y. Эти кривые могут пересекаться, но не должны проходить через вершины, если только они не являются концами линии. Такая диаграмма с помеченными вершинами однозначно определяют частичный порядок.

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

Удобство диаграмм[править | править вики-текст]

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

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

Hypercubeorder binary.svg Hypercubecubes binary.svg Hypercubestar binary.svg Hypercubematrix binary.svg

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

Планарность[править | править вики-текст]

Диаграмма Хассе подгрупповой решётки диэдрической группы \mathrm{Dih}_4 не имеет пересекающихся рёбер.

Некоторые свойства частичных порядков относительно планарности их диаграммы Хассе (то есть возможности нарисовать её без пересечения рёбер):

  • Если частичный порядок является решёткой, то его можно нарисовать без пересечений тогда и только тогда, когда размерность порядка не менее двух[3][4].
  • Если частичный порядок имеет по меньшей мере один минимальный или максимальный элемент, то можно за линейное время проверить, существует ли диаграмма без пересечений[5].
  • Определить, можно ли частичный порядок представить планарной диаграммой Хассе, в общем случае NP-полная задача[6].
  • Если заданы y-координаты элементов частичного порядка, то за линейное время может быть найдена его диаграмма Хассе, сохраняющая заданные координаты, если только такая диаграмма существует[7]. В частности, если частный порядок имеет уровни, можно за линейное время определить, имеется ли диаграмма Хассе без пересечений, у которой высота каждой вершины пропорциональна её рангу.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • 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.

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