Remove ads
Из Википедии, свободной энциклопедии
Диаграмма Ха́ссе — вид диаграмм, используемый для представления конечного частично упорядоченного множества в виде рисунка его транзитивного сокращения. Конкретно, для частично упорядоченного множества диаграмма представляет каждый элемент как вершины на плоскости и отрезки или кривые, идущие вверх от элемента к элементу , если и не существует элемента , для которого . Эти кривые могут пересекаться, но не должны проходить через вершины, если только они не являются концами линии. Такая диаграмма с помеченными вершинами однозначно определяют частичный порядок.
Впервые систематически такого рода визуализация описана Биркгофом в 1948 году[1], им же дано название в честь использовавшего подобные диаграммы Хельмута Хассе, однако такого рода рисунки встречаются и в более ранних трудах, например, в учебнике французского математика Анри Фохта (нем. Henri Vogt) 1895 года издания[2].
Хотя диаграммы Хассе является простым и интуитивно ясным средством для работы с конечным частично упорядоченным множеством, весьма сложно нарисовать «хорошую», удобную для визуального восприятия диаграмму для достаточно нетривиального множества из-за большого количества возможных вариантов отображения. Простая техника, предполагающая начать с минимальных элементов и рисовать вышележащие элементы последовательно часто дает плохие результаты — симметрии и внутренние структуры легко потерять.
Например, булеан множества из четырёх элементов, упорядоченного операцией включения , может быть представлен любой из четырёх нижеприведённых диаграмм (каждое подмножество снабжено меткой с бинарной кодировкой, показывающей, содержится соответствующий элемент в подмножестве — 1, или нет — 0):
Первая диаграмма демонстрирует структуру уровней. Вторая диаграмма имеет ту же структуру уровней, но на ней некоторые рёбра удлинены, чтобы подчеркнуть, что четырёхмерный куб является объединением двух трёхмерных. Третья диаграмма показывает некоторую внутреннюю симметрию. В четвёртой диаграмме вершины упорядочены подобно матрице 4×4.
Некоторые свойства частичных порядков относительно планарности их диаграммы Хассе (то есть возможности нарисовать её без пересечения рёбер):
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.