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

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

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

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

«Хорошие» диаграммы Хассе[править | править исходный текст]

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

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

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

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

Планарность[править | править исходный текст]

Эта диаграмма Хассе решётки подгрупп диэдрической группы Dih4 не имеет пересекающихся ребер.

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

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

Замечания[править | править исходный текст]

  1. Di Battista, Tamassia, 1988 и Freese,2004.
  2. Garg Tamassia, 1995, Theorem 9, p. 118; Baker Fishburn Roberts 1971, theorem 4.1, page 18.
  3. Garg, Tamassia, 1995, Theorem 15, p. 125; Bertolazzi, Di Battista, Mannino, Tamassia, 1993
  4. Garg, Tamassia, 1995, Corollary 1, p. 132; Garg, Tamassia, 1995.
  5. Jünger, Leipert, 1999.

Ссылки[править | править исходный текст]