Дискретная математика. Кулаков Ю.В - 14 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Рассмотрим информационный обмен между устройствами m
i
и m
j
, которые находятся в отношении
T, если информация из устройства m
i
поступает в устройство m
j
. Это отношение можно задать в виде
матрицы смежности следующим образом:
a b c d e
0 1 1 1 0
a
0 0 1 1 1
b
B
= 1 1 0 1 1
c
.
0 1 1 0 1
d
0 0 1 0 0
e
Граф G, задаваемый рассмотренным отношением T, изображен на рис. 5. На этом рисунке (и в
дальнейшем) вершины графа изображаются в виде кружков (иногда в виде точек), дуги – в виде стре-
лок, исходящих из m
i
и входящих в m
j
, если (m
i
, m
j
) ∈ T; при этом вершина m
i
– начало дуги, а вершина
m
j
– ее конец.
Рассмотрим задание бинарного отношения с помощью фактор-множества.
Окрестностью единичного радиуса элемента m
i
∈ M называется множество элементов m
j
∈ M та-
ких, что (m
i
, m
j
) ∈ T, Т ⊂ М
2
. Часто вместо термина окрестность единичного радиуса используют тер-
мин сечение.
Множество окрестностей единичного радиуса, взятых для всех элементов множества M при задании
в нем отношения Т ⊂ М
2
, называется фактор-множеством M/T множества M по отношению T. Фактор-
множество M/T полностью определяет отношение T.
Зададим фактор-множество для рассматриваемого примера в виде двух строк, в первой из которых
поместим элементы множества М, во второй под каждым элементом запишем окрестность единичного
радиуса этого элемента:
a b c d e
{b, c, d} {c, d, e}{a, b, d,
e}
{b, c, e}{c}
Бинарное отношение, задаваемое графом G = 〈M, T〉 (рис. 5), можно задать и перечислением его дуг:
M = {a, b, c, d, e}, T = {(a, b), (a, c), (a, d), (b, c), (b, d), (b, e),
(c, a), (c, b), (c, d), (c, e), (d, b), (d, c), (d, e), (e, c)}.
Рассмотрим наиболее важные свойства бинарных отношений.
Отношение T в множестве M называется рефлексивным, если
(∀ m ∈ M) ((m, m) ∈ T).
a
b
c
d
e
m
m
j
m
i
m
i
m
j
m
k
а)
б)
в)
Рис. 5
Рис. 6

Страницы