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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

20
Принцип, в соответствии с которым отношение, обратное отноше-
нию упорядоченности, также является отношением упорядоченности, на-
зывается принципом двойственности.
Двойственным к частично упорядоченному множеству называется
частично упорядоченное множество, определённое на том же носителе с
помощью обратного отношения. На рисунке 9, б изображена диаграмма,
являющаяся двойственной к диаграмме Хассе (см. рис. 9, а).
Другим важным бинарным отношением является отношение эквива-
лентности ∼, под которым понимается бинарное отношение, обладающее
свойствами рефлексивности, симметричности и транзитивности.
Классом эквивалентности K(m
a
) элемента m
a
называется множество
всех элементов m
i
, каждый из которых находится с элементом m
a
в отно-
шении эквивалентности:
K(m
a
) = { m
i
/ m
i
∼ m
a
}.
Два различных класса эквивалентности K(m
x
) и K(m
y
) не пересека-
ются: K(m
x
) ∩ K(m
y
) = ∅.
Представление множества M в виде попарно непересекающихся
подмножеств вида M
i
будем называть разбиением этого множества:
U
i
i
M
= M,
M
a
i
∩
M
b
i
= ∅, i
a
≠ i
b
.
Таким образом, классы эквивалентности образуют разбиение мно-
жества. Тестом распознавания отношения эквивалентности может быть
приведение его матрицы смежности с помощью перестановки строк и
столбцов к клеточному виду, при котором вдоль главной диагонали мат-
рицы расположены единичные подматрицы, а остальные элементы мат-
рицы равны нулю. Каждая единичная подматрица называется клеткой и
соответствует своему классу эквивалентности.
На рисунке 10 приведён пример клеточной
матрицы, в которой единичные подматрицы за-
штрихованы. Данная матрица имеет три клетки и
представляет отношение эквивалентности с тремя
классами эквивалентности.
Графы, представленные на рис. 7, а, б и в,
задают отношения эквивалентности с тремя, дву-
мя и одним классами соответственно.
Задачи и упражнения
1. Представить с помощью матрицы смежности, графа и фактор-
множества бинарное отношение Т в множестве M = {a, b, c, d}, заданное
перечислением элементов:
Рис. 10

Страницы