Диаграмма Хассе частично упорядоченного множества

Напомним, что ориентированным графом называется пара (V,A), состоящая из множества V и подмножества AÍV´V. Элементы из A называются стрелками, а из V – вершинами. Для стрелки (u,v) вершина u называется началом, а из v – концом.

Пусть (X,£) – частично упорядоченное множество. Множество ]x,y[ = {vÎX: x<v<y} называется открытым интервалом с концами x и y.

Диаграммой Хассе называется ориентированный граф (V,A) с V=X и A ={ (u,v): u<v и ]u,v[ = Æ }.

Пример 1. На рис. 4. 8 показана диаграмма Хассе множества P({0,1,2}) подмножеств множества {0,1,2}, упорядоченное отношением Í.

Рис. 4.8. Диаграмма Хассе множества подмножеств

Предполагаются, что ребра направлены сверху вниз.

Пример 2. Для целого неотрицательного числа n³0 будем обозначать через [n] множество {0, 1, ∙ ∙ ∙, n}, с отношением 0 < 1< ∙ ∙ ∙ < n. Его диаграммой Хассе будет ориентированный граф

·®·®·® × × × ®·®·

Частично упорядоченные множества (X, £) и (Y, £) называются изоморфными, если существуют неубывающие отображения f: X®Y и g: Y®X такие, что f(g(y))=y и g(f(x))=x ("xÎX, "yÎY).

В этом случае f называется изоморфизмом, а g – обратным отображением для f.

Рассмотрим множество делителей (D_n, |) натурального числа n³1, упорядоченное отношением делимости a | b Û a – делитель числа b (в этом случае говорят, что a – делит b).

Пример 3. Пусть p и q – различные простые числа >1. Диаграмма Хассе множества (D_n, |) с n=p²q показана на рисунке

Рис. 4.9. Диаграмма Хассе множества делителей

В общем случае диаграмма Хассе частично упорядоченного множества (D_n,|) состоит из ребер m-мерного параллелепипеда, где m – число различных простых делителей числа n.

Теорема 1. Пусть n>0 – положительное натуральное число, n = - его разложение в произведение попарно не равных простых множителей p_i>1. Тогда частично упорядоченное множество (D_n, |) будет изоморфно декартовому произведению [a₁]´ [a₂]´ ××× ´ [a_m] линейно упорядоченных множеств.

Доказательство. Каждый делитель числа n = будет равен числу , для некоторых 0£ b₁£a₁, 0£ b₂£a₂, × × ×, 0£ b_m£a_m. Изоморфизм определяется как отображение, ставящее в соответствие числу элемент (b₁, b₂, × × ×, b_m).