Как строится диаграмма хассе конечного упорядоченного множества

Вопрос №18. Диаграммы Хассе

Любое частично-упорядоченное мн-во можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости. Если элемент у покрывает элемент х, то х и у соединяются отрезком, причем точка х располагается ниже точки у. Такие схемы называют диаграммами Хассе.

Элемент у покрывает элемент х:

Пусть А ≠ ∅ и card A < ∞. Пусть p (подмножество А 2 ) — отношение порядка. Элемент у покрывает элемент х, если у ≤ х и не существует u ∈ A (x < u < y).

Примеры применения и свойства.

Пример первый.

Возьмём некоторое множество A = <3;6;4>и построим отношение ƿ, где ƿ: P(A) x P(A). P(A) – множество всех подмножеств, его можно представить в таком виде: Ø, <3>, <6>, <4>, <3;6>, <6;4>, <3;4>, <3;6;4>>. Построим диаграмму Хассе данного отношения. На Рис. 1, представлена эта диаграмма.

Рис.1 Диаграмма Хассе для первого отношения

Отметим, что в этой диаграмме один элемент “Покрывает” другой, то есть, если мы берём два случайных элемента, то они не равны друг – другу и одни из этих элементов предшествует другому. К примеру, возьмём из диаграммы элемент Ø и <3>, они не равны друг – другу и один предшествует другому.

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

Пример второй.

Построим диаграмму Хассе для отношения Ω, где Ω: быть делителем. Возьмём множество A = <1;2;4;5;10>. Построенная диаграмма показана на Рис. 2.

Рис.2 Диаграмма Хассе для второго

Введём новые понятия для данного вида диаграмм. Наибольший (Величайший) и Наименьший элемент. Наименьший элемент диаграммы является тем элементом, который начинает диаграмму, а наибольшим (величайшим), тем элементом, который её заканчивает. Причём если наибольших (величайших) или наименьших элементов несколько, то в ответ будет записываться, что наибольшего или наименьшего элемента нет. Другими словами, наибольший (величайший) и наименьший элемент на диаграмме Хассе — только один.

Возвращаясь к первому примеру, там сразу видно, что наименьшим элементом у нас будет Ø, а наибольшим (величайшим) <3;6;4>. Во втором примере наименьшим элементом будет 1, а наибольшего (величайшего) элемента не будет, т.к. наибольшими (величайшим) элементами могут быть сразу 4 и 10, следовательно, наибольшего (величайшего) элемента во втором примере нет.

Максимальные элементы — это те, которые не заменяются другим элементом. Минимальные элементы — это те, которым не предшествует другой элемент.

Вопрос №19. Изоморфные, частично упорядоченные множества

Бинарное отношение R ⊆ A 2 на множестве A называется отношением частичного порядка на множестве A, если оно

1) антисимметрично, т.е. ∀x , y ∈ A из R(x , y) и R(y , x) следует x = y (совпадение элементов);

2) транзитивно, т.е. ∀x , y , z ∈ A из R(x , y) и R(y , z) следует R(x , z).

Если отношение при этом рефлексивно, то это отношение нестрогого частичного порядка. Если же отношение антирефлексивно, то это отношение строгого частичного порядка.

Если a, b ∈ A и a ≤ b, то говорят, что элемент a предшествует или равен элементу b, или элемент b следует или равен элементу a.

Пусть R ⊆ A2 – отношение частичного порядка на множестве A. Если для элементов a, b ∈ A верно R(a, b) или верно R(b, a), то элементы a и b называются сравнимыми.

Элементы a, b ∈ A, не являющиеся сравнимыми, называются несравнимыми.

Если все пары элементов множества A сравнимы относительно порядка R , то порядок R называется линейным.

Множество A с заданным на нем частичным порядком R называется частично упорядоченным множеством (ЧУМ) и обозначается (A;R).

Если частичный порядок R является линейным, то ЧУМ (A;R) называется линейно упорядоченным множеством.

Изоморфизмы

Два частично упорядоченных множества называются изоморфными, если между ними существует изоморфизм, то есть взаимно однозначное соответствие, сохраняющее порядок. (Естественно, что в этом случае они равномощны как множества.) Можно сказать так: биекция называется изоморфизмом частично упорядоченных множеств и , если

для любых элементов (слева знак обозначает порядок в множестве , справа — в множестве ).

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

Диаграмма Хассе — Hasse diagram

В теории порядка , A Диаграмма Хассе ( / ч æ с ə / ; Немецкий: [hasə] ) представляет собой тип математической диаграммы используется для представления конечного частично упорядоченное множество , в виде рисунка ее переходной сокращения . Конкретно, для частично упорядоченного множества (S, ≤) каждый элемент S представляет собой вершину на плоскости и рисует линейный сегмент или кривую, идущую вверх от x до y всякий раз, когда y покрывает x (то есть, когда x ≤ y и не существует z такого, что x ≤ z ≤ y ). Эти кривые могут пересекать друг друга, но не должны касаться каких-либо вершин, кроме своих конечных точек. Такая диаграмма с помеченными вершинами однозначно определяет ее частичный порядок.

Диаграммы названы в честь Хельмута Хассе (1898–1979); согласно Гаррету Биркоффу ( 1948 ), они получили такое название из-за того, что Хассе эффективно их использовал. Однако Хассе не был первым, кто использовал эти диаграммы. Один пример, предшествующий Хассе, можно найти у Анри Густава Фогта ( 1895 г. ). Хотя диаграммы Хассе изначально создавались как метод рисования частично упорядоченных наборов вручную, в последнее время они были созданы автоматически с использованием методов рисования графиков .

Фраза «диаграмма Хассе» может также относиться к транзитивной редукции как к абстрактному ориентированному ациклическому графу , независимо от любого рисунка этого графа, но это использование здесь избегается.

СОДЕРЖАНИЕ

Схема дизайна

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

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

Первая диаграмма ясно показывает, что набор мощности — это градуированный набор . Вторая диаграмма имеет ту же градуированную структуру, но, сделав одни ребра длиннее других, она подчеркивает, что 4-мерный куб представляет собой комбинаторное объединение двух 3-мерных кубов и что тетраэдр ( абстрактный 3-многогранник ) также объединяет два треугольники ( абстрактные 2-многогранники ). Третья диаграмма показывает некоторую внутреннюю симметрию конструкции. На четвертой диаграмме вершины расположены как элементы матрицы 4 × 4 .

Восходящая планарность

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

Если частичный порядок, который нужно нарисовать, представляет собой решетку , то ее можно нарисовать без пересечений тогда и только тогда, когда она имеет размерность порядка не более двух. В этом случае непересекающийся чертеж может быть найден путем получения декартовых координат для элементов из их положений в двух линейных порядках, реализующих размер порядка, а затем поворота чертежа против часовой стрелки на угол 45 градусов.
Если частичный порядок имеет не более одного минимального элемента или он имеет не более одного максимального элемента , то можно проверить за линейное время , имеет ли он непересекающуюся диаграмму Хассе.
Это NP-полный, чтобы определить, может ли частичный порядок с несколькими источниками и стоками быть нарисован как диаграмма Хассе без перекрестков. Однако нахождение диаграммы Хассе без перекрестков является управляемым с фиксированным параметром, если параметризовано количеством точек сочленения и трехсвязными компонентами транзитивной редукции частичного порядка.
Если y -координаты элементов частичного порядка заданы, то диаграмма Хассе без перекрестков, учитывающая эти назначения координат, может быть найдена за линейное время, если такая диаграмма существует. В частности, если входной poset является градуированным poset , можно определить за линейное время, существует ли диаграмма Хассе без перекрестков, в которой высота каждой вершины пропорциональна ее рангу.

Нотация UML

Стандартная диаграмма для цепочки включений — это класс UML , связывающий множества отношением наследования. На рисунке показан вложенный набор сбора , C :

Диаграмма Хассе с примерами кратко

Сразу хочу сказать, что здесь никакой воды про диаграмма хассе, и только нужная информация. Для того чтобы лучше понимать что такое диаграмма хассе , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

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

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

Определение диаграммы Хассе.

Элемент у покрывает элемент х:

Отношения частичного порядка, то есть рефлексивные, антисимметричные и транзитивные, на которые накладывают ряд дополнительных свойств, изучаются в рамках раздела математики с экзотическим названием ТЕОРИЯ РЕШЕТОК. Это название пугает, поэтому в нашей стране первоначально слово lattice переводили как "структура". Но когда в математике все шире стал употребляться термин structure, то пришлось ему отдать русское слово структура, а решетки стали и у нас в стране решетками.
Можно предположить, что название "решетки" возникло в связи с использованием так называемых диаграмм Хассе3, которые напоминают экстравагантные решетки для окон.
Начнем с примеров решеток.
Возьмем слова: о, ор, вор, ворот, кол, олово, коловорот — и упорядочим их по вхождению одних слов в другие (не забывая, что каждое слово входит само в себя) . Об этом говорит сайт https://intellect.icu . Это будет наша первая решетка.
Можно убедиться, что здесь выполняются все свойства частичного порядка. А о дополнительных свойствах поговорим позже.
Числа: 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением «делить нацело» так же образуют решетку.
Обычные действительные числа с отношением "больше или равно" дают одну из самых распространенных решеток. Хотя для нас она менее экзотическая. Можно сказать, простая как бревно.
Множество всех подмножеств какого-то множества с отношением включения дает решетку, причем, с рядом замечательных свойств.

Отношения, похожие на отношения порядка, но не обладающие свойством транзитивности, называют отношениями ТОЛЕРАНТНОСТИ.
Хорошей иллюстрацией этого отношения служат многие известные картинки Эшера, где, например, птицы плавно превращаются в рыб и т.п.

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

Удобство диаграмм

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

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

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

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

Планарность

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

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

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

Если частичный порядок является решеткой, то его можно нарисовать без пересечений тогда и только тогда, когда размерность порядка не менее двух .
Если частичный порядок имеет по меньшей мере один минимальный или максимальный элемент, то можно за линейное время проверить, существует ли диаграмма без пересечений .
Определить, можно ли частичный порядок представить планарной диаграммой Хассе, в общем случае NP-полная задача .
Если заданы -координаты элементов частичного порядка, то за линейное время может быть найдена его диаграмма Хассе, сохраняющая заданные координаты, если только такая диаграмма существует . В частности, если частный порядок имеет уровни, можно за линейное время определить, имеется ли диаграмма Хассе без пересечений, у которой высота каждой вершины пропорциональна ее рангу.

Определения

Наибольший (Величайший) и Наименьший элемент. Наименьший элемент диаграммы является тем элементом, который начинает диаграмму, а наибольшим (величайшим), тем элементом, который ее заканчивает. Причем если наибольших (величайших) или наименьших элементов несколько, то в ответ будет записываться, что наибольшего или наименьшего элемента нет. Другими словами, наибольший (величайший) и наименьший элемент на диаграмме Хассе — только один.

Нотация UML

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

Выражение примера с помощью стандартных соединителей наследования UML. Каждый набор представляет собой отдельный объект (стандартные блоки UML имеют прямоугольную форму).

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

Примеры

пример 1

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

Рис.1 Диаграмма Хассе для второго отношения

Построим диаграмму Хассе для отношения Ω, где Ω: быть делителем.

Возьмем множество A = <1;2;4;5;10>. Построенная диаграмма показана на Рис. 1.

пример 2

Возьмем некоторое множество A = <3;6;4>и построим отношение ƿ, где ƿ: P(A) x P(A). P(A) – множество всех подмножеств, его можно представить в таком виде: < Ø, <3>, <6>, <4>, <3;6>, <6;4>, <3;4>, <3;6;4>>. Построим диаграмму Хассе данного отношения. На Рисунке 2, приведена эта диаграмма.

Отметим, что в этой диаграмме один элемент “Покрывает” другой, то есть, если мы берем два случайных элемента, то они не равны друг – другу и одни из этих элементов предшествует другому. К примеру, возьмем из диаграммы элемент Ø и <3>, они не равны друг – другу и один предшествует другому.

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

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

Рис.2 Диаграмма Хассе для отношения

См. также

Карты Карно
Окружности Вилларсо
диаграмма венна , диаграмма эйлера ,
диаграмма Венна
Теория множеств
теория решеток
отношения ПОРЯДКА
круги Эйлера
Карта Карно
Окружности Вилларсо
Диаграмма паука ( унитарная паутинная диаграмма)

Пожалуйста, пиши комментарии, если ты обнаружил что-то неправильное или если ты желаешь поделиться дополнительной информацией про диаграмма хассе Надеюсь, что теперь ты понял что такое диаграмма хассе и для чего все это нужно, а если не понял, или есть замечания, то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Как строится диаграмма хассе конечного упорядоченного множества

Чтобы нарисовать диаграмму Хассе, предоставленный набор должен быть набором.
Сета или частично упорядоченное множество A является парой, (B, ) множества B, элементы которого называются вершинами A и подчиняются следующим правилам:

Рефлексивность → р п п В
Антисимметричный → p q и q если p = q
Транзитивность → если р q и q г, то р р

Пояснение — в соответствии с приведенным выше вопросом, в первую очередь, мы должны найти точку делимости.
Пусть множество А.
А = 12), (3 24), (3 48), (3 72), (4 12), (4 24), (4 48), (4 72), (12 24), (12 48), (12 72), (24 48), (24 72)>
Итак, теперь диаграмма Хассе будет:

На приведенной выше диаграмме 3 и 4 находятся на одном уровне, потому что они не связаны друг с другом, и они меньше, чем другие элементы в наборе. Следующий последующий элемент для 3 и 4 — 12, т. Е. 12 делится на 3 и 4. Тогда 24 делится на 3, 4 и 12. Следовательно, он помещается выше 12. 24 делит и 48, и 72, а 48 — нет. разделить 72. Следовательно, 48 и 72 не объединены.
Мы можем видеть транзитивность на нашей диаграмме по мере увеличения уровня.

Пример 2: Нарисуйте диаграмму Хассе для (D , /)

Пояснение — Здесь, D означает множество положительных целых делителей 12.
Итак, Д =
Poset A = 2), (1 3), (1 4), (1 6), (1
12), (2 4), (2 6), (2 12), (3 6), (3 12), (4 12), (6 12)>
Итак, теперь диаграмма Хассе будет

На приведенной выше диаграмме 1 является единственным элементом, который делит все остальные элементы на наименьшие. Следовательно, он находится внизу. Тогда элементами в нашем наборе являются 2 и 3, которые не разделяют друг друга, следовательно, они размещаются на одном уровне отдельно, но делятся на 1 (оба соединены 1). 4 делится на 1 и 2, в то время как 6 делится на 1, 2 и 3, следовательно, 4 соединяется с 2, а 6 соединяется с 2 и 3. Следовательно, 12 делится на все элементы, следовательно, соединяются 4 и 6 не на все элементы, потому что мы уже соединили 4 и 6 с меньшими элементами соответственно.