Дискретная математика. Громов Ю.Ю - 19 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

19
Множество M с заданным в нём отношением упорядоченности R или
отношением строгой упорядоченности S, называется частично упорядо-
ченным множеством. Частично упорядоченное множество M, в котором
любые два элемента m
i
и m
j
находятся в отношении упорядоченности, на-
зывается линейно упорядоченным множеством. Например, частично упо-
рядоченные множества представлены на рис. 7, д, ж, з, и. Из них первые
два являются линейно упорядоченными множествами.
На рисунке 8 приведён ещё один пример частично упорядоченного
множества, при этом в качестве отношения упорядоченности рассмотре-
но отношение включения множеств ⊂ .
Иногда частично упорядоченные множества изображают в виде
графов, у которых удалены все петли и транзитивно замыкающие дуги.
Граф H, задающий частично упорядоченное множество с удалёнными
петлями и транзитивно замыкающими дугами, называется диаграммой
Хассе. Диаграмма Хассе частично упорядоченного множества, представ-
ленного на рис. 8, изображена на рис. 9, а.
Под изоморфизмом между двумя упорядоченными множествами
M и M
*
будем понимать взаимно однозначное соответствие η между
M и M
*
такое, что из m
i
≤ m
j
следует η(m
i
) ≤ η(m
j
) и из η(m
i
) ≤ η(m
j
) следу-
ет m
i
≤ m
j
.
Два упорядоченных множества называются изоморфными множе-
ствами тогда и только тогда, когда между ними существует изоморфизм.
Например, булеан B ({y, x, a}) и множество M = {1, 2, 3, 5, 6, 10, 15, 30}
являются изоморфными множествами, если булеан упорядочен отноше-
нием включения множеств ⊂ , а множество M упорядочено бинарным от-
ношением T: (m
i
, m
j
) ∈ T тогда и только тогда, когда m
i
делит m
j
без ос-
татка.
Под отношением, обратным отношению R, понимают такое от-
ношение
R
, при котором (m
i
, m
j
) ∈
R
тогда и только тогда, когда
(m
j
, m
i
) ∈ R.
1={y, x, a}
1={y, x, a}
1={y, x, a}
{y, x}
{y, x}
{y, x}
{y, a}
{y, a}
{y, a}
{a, x}
{a, x}
{a, x}
{y}
{y}
{y}
{x}
{x}
{x}
{a}
{a}
{a}
∅
∅
∅
Рис. 8
Рис. 9
а)
б)

Страницы