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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

15
3. БИНАРНЫЕ ОТНОШЕНИЯ.
СПОСОБЫ ЗАДАНИЯ И СВОЙСТВА
Понятие отношения является фундаментальным понятием дискрет-
ной математики, которое используют для обозначения связей между ка-
кими-либо объектами.
Декартово произведение двух равных между собой множеств назы-
вают квадратом множества М: М × М = М
2
. Бинарным отношением Т в
множестве М называется подмножество его квадрата: Т ⊂ М
2
. Говорят,
что элементы m
i
и m
j
находятся в отношении T, если (m
i
, m
j
) ∈ T. Совокуп-
ность множества М и заданного в нём бинарного отношения Т называется
графом G:
G = 〈M, T
〉,
где M – носитель графа (множество вершин), T – сигнатура графа (мно-
жество дуг).
Рассмотрим задание бинарного отношения с помощью матрицы
смежности и фактор-множества.
При матричном задании используют двумерную таблицу – матрицу
смежности, каждой строке (столбцу) которой взаимно однозначно со-
поставляют элемент множества М. Тогда каждая клетка (i, j) таблицы
взаимно однозначно соответствует элементам множества М
2
. Клетки
(i, j), которые соответствуют элементам бинарного отношения Т, как-то
отмечают (например, зачерняют или помещают в неё единицу), а осталь-
ные клетки оставляют неотмеченными (незачернёнными или записывают
в них нули).
В качестве иллюстрации рассмотрим предложенную американским
математиком Джоном фон Нейманом (1903 − 1957) блок-схему ЭВМ, ко-
торая состоит из множества устройств:
M = {a, b, c, d, e},
где a – устройство ввода; b – арифметическое устройство (процессор);
c – устройство управления; d – запоминающее устройство; e – устройство
вывода. Если информация из устройства m
i
поступает в устройство m
j
,
то устройства m
i
и m
j
находятся в отношении T. Бинарное отношение T
зададим перечислением элементов:
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)}.
Это же отношение можно задать матрицей смежности следующим
образом:

Страницы