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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Свойство рефлексивности при задании отношения матрицей смежности характеризуется тем, что
все элементы, лежащие на главной диагонали, отмечены (равны 1 или зачернены); при задании отноше-
ния графом каждый элемент имеет петлю – дугу вида (m, m) (рис. 6, а). Рефлексивными бинарными от-
ношениями в множестве M = {a, b, c} являются отношения, представленные с помощью графов на рис.
7, а, б, в, ж, з, к.
Отношение T в множестве M называется антирефлексивным, если
(∀ m ∈ M) ((m, m) ∉ T).
Свойство антирефлексивности при задании отношения матрицей смежности характеризуется тем,
что ни один элемент, лежащий на главной диагонали, не отмечен (равен 0 или не зачернен); при задании
отношения графом ни один его элемент не имеет петлю. Антирефлексивными бинарными отношениями
в множестве M = {a, b, c} являются отношения, представленные на рис. 7, д, е, и, л.
Отношение T в множестве M будем называть нерефлексивным, если оно не является ни рефлексив-
ным, ни антирефлексивным. Нерефлексивными являются отношения на рис. 7, г, м, н.
Отношение Т в множестве М называется симметричным, если
(∀ a, b ∈ M, a ≠ b) ((a, b) ∈ T → (b, a) ∈ T).
Матрица смежности симметричного отношения является симметричной относительно главной диа-
гонали, а при задании отношения в виде графа следствием симметричности является наличие между
всякой парой вершин, находящихся в отношении T, двух противоположно направленных дуг (рис. 6, б).
Симметричными бинарными отношениями в множестве M = {a, b, c} являются отношения, представ-
ленные на рис. 7, а, б, в.
Отношение Т в множестве М называется антисимметричным, если
(∃ a, b ∈ M, a ≠ b) ((a, b) ∈ T) и
(∀ a, b ∈ M, a ≠ b) ((a, b) ∈ T → (b, a) ∉ T).
Антисимметричными бинарными отношениями в множестве M = {a, b, c} являются отношения, пред-
ставленные на рис. 7, д, ж, з, и, н.
Отношение T в множестве M будем называть несимметричным, если оно не является ни симмет-
ричным, ни антисимметричным. Несимметричными являются отношения на рис. 7, г, е, к, л, м.
Отношение T в множестве M называется транзитивным, если
(∀a, b, с ∈ M, a ≠ b, a ≠ c, b ≠ c)((a, b) ∈ T, (b, c) ∈ T → (a, c) ∈ T).
В графе, задающем транзитивное отношение T, для всякой пары дуг таких, что конец первой совпа-
дает с началом второй, существует третья дуга, имеющая общее начало с первой и общий конец со второй
(рис. 6, в), − транзитивно замыкающая дуга. Транзитивными бинарными отношениями в множестве
M = {a, b, c} являются отношения, представленные на
рис. 7, а, б, в, д, ж, з, и, к, л.
a
b c
a
b c
a
b c
a
b c
a
b c
a
b c
a
b c
a
b c
a
b c
a
b c
a
b c
a
b c
a
b c
а)
б)
в) г)
д)
е)
ж)
з) и)
к)
л)
м)
н)
Рис.7

Страницы