|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Диаграмма Хассе частично упорядоченного множестваНапомним, что ориентированным графом называется пара (V,A), состоящая из множества V и подмножества AÍV´V. Элементы из A называются стрелками, а из V – вершинами. Для стрелки (u,v) вершина u называется началом, а из v – концом. Пусть (X,£) – частично упорядоченное множество. Множество ]x,y[ = {vÎX: x<v<y} называется открытым интервалом с концами x и y. Определение 1. Диаграммой Хассе называется ориентированный граф (V,A) с V=X и A ={ (u,v): u<v и ]u,v[ = Æ }. Пример 1. На рис. 5.1 показана диаграмма Хассе множества P({0,1,2}) подмножеств множества {0,1,2}, упорядоченное отношением Í. Рис. 5.1. Диаграмма Хассе множества подмножеств Предполагаются, что ребра направлены сверху вниз. Пример 2. Для целого неотрицательного числа n³0 будем обозначать через [n] множество {0, 1, ∙ ∙ ∙, n}, с отношением 0 < 1< ∙ ∙ ∙ < n. Его диаграммой Хассе будет ориентированный граф, приведенный на рис. 5.2.
·®·®·® × × × ®·®· Рис. 5.2. Диаграмма Хассе
Частично упорядоченные множества (X, £) и (Y, £) называются изоморфными, если существуют неубывающие отображения f: X®Y и g: Y®X такие, что f(g(y))=y и g(f(x))=x ("xÎX, "yÎY). В этом случае f называется изоморфизмом, а g – обратным отображением для f. Рассмотрим множество делителей (Dn, |) натурального числа n³1, упорядоченное отношением делимости a | b Û a – делитель числа b (в этом случае говорят, что a – делит b). Пример 3. Пусть p и q – различные простые числа, большие единицы. Диаграмма Хассе множества (Dn, |) с n=p2q показана на рисунке 5.3. Рис. 5.3. Диаграмма Хассе множества делителей В общем случае диаграмма Хассе частично упорядоченного множества (Dn,|) состоит из ребер m -мерного параллелепипеда, где m – число различных простых делителей числа n. Теорема 1. Пусть n>0 – положительное натуральное число, n = - его разложение в произведение попарно не равных простых множителей pi>1. Тогда частично упорядоченное множество (Dn, |) будет изоморфно декартовому произведению [a1]´ [a2]´ ××× ´ [am] линейно упорядоченных множеств. Доказательство. Каждый делитель числа n = будет равен числу , для некоторых 0£ b1£a1, 0£ b2£a2, × × ×, 0£ bm£am. Изоморфизм определяется как отображение, ставящее в соответствие числу элемент (b1, b2, × × ×, bm). Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.) |