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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

16
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 ∈ M. Если (m
i
, m
j
) ∈ T, в графе рисуется
стрелка, выходящая их вершины m
i
и входящая в вершину m
j
. При этом
вершина m
i
называется началом дуги (m
i
, m
j
), а вершина m
j
− её концом.
Рассмотрим задание бинарного отношения с помощью фактор-
множества.
Окрестностью единичного радиуса элемента m
i
∈ M, которую будем
обозначать через O(m
i
), называется множество элементов m
j
∈ M таких,
что (m
i
, m
j
) ∈ T. Довольно часто вместо термина окрестность единичного
радиуса используют термин сечение.
Множество окрестностей единичного радиуса, взятых для всех эле-
ментов множества M при задании в нём отношения Т ⊂ М
2
, называется
фактор-множеством M / T множества M по отношению T. Фактор-
множество M / T полностью определяет отношение T.
Зададим фактор-множество для рассматриваемого примера блок-
схемы ЭВМ в виде двух строк, в первой из которых поместим элементы
множества М, во второй под каждым элементом запишем окрестность
единичного радиуса этого элемента:
M / T =
a b c d e
{b c d} {c d e} {a b d e} {b c e} {c}
a
b
c
d
e
m
m
j
m
i
m
i
m
j
m
k
а)
б)
в)
Рис. 5 Рис. 6

Страницы