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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

24
При задании S-отношений при помощи двудольного графа буквы
выступают в качестве элементов подмножества V
+
, слова − в качестве
элементов подмножества V
−
, и дуга (v
α
, v
β
) имеет место тогда и только
тогда, когда буква, соответствующая вершине v
α
∈ V
+
, входит в слово,
соответствующее вершине v
β
∈ V
−
. Двудольный граф, задающий пример
рассматриваемого 3-отношения, изображён на рис. 13.
Понятие модели является одним из основных в дискретной матема-
тике. Моделью Ψ называется совокупность множества M и множества за-
данных в нём отношений S:
Ψ = 〈M, R〉.
При этом множество M называют носителем модели, а множество R =
= {R
11
, R
12
, ...,
1
1n
R , R
21
, R
22
, ...,
2
2n
R , ..., R
m1
, R
m2
, ...,
m
mn
R
} − сигнатурой
модели. Здесь отношение R
ij
⊂ M
i
, а значение i определяет арность от-
ношения.
Алгебраической системой называется совокупность множества M с
заданными в нём операциями и отношениями. Частным случаем алгеб-
раической системы является алгебра отношений.
Задачи и упражнения
1. Установить, является ли симметричным заданное 3-арное отно-
шение T в множестве M = {a, b, c, d, e, g}:
а) Т = {(a, b, c), (c, b, a), (b, c, d), (d, c, b)};
б) Т = {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)};
в) Т = {(a, b, c), (c, b, a), (b, c, d), (d, c, b), (c, d, e), (e, d, c)};
г) Т = {(a, b, d), (a, d, b), (b, a, d), (b, d, a), (d, a, b), (d, b, a),
(a, e, g), (a, g, e), (e, a, g), (e, g, a), (g, a, e), (g, e, a)};
д) Т = {(a, c, e), (a, e, c), (c, a, e), (c, e, a), (e, a, c), (e, c, a), (a, b, g), (a,
g, b), (b, a, g), (b, g, a), (g, a, b), (g, b, a), (b, d, e), (b, e, d), (d, b, e),
(d, e, b), (e, b, d), (e, d, b)}.
Симметричные отношения представить матрицей инцидентности Q,
модельным графом, гиперграфом и двудольным графом, а также указать
какие слова они определяют.
с и ы а р о
Рис. 13
µ
1
µ
2
µ
3
µ
4

Страницы