Дискретная математика / Отношения

Отношения.

Основные положения

Фундаментальным понятием дискретной математики является понятие отношения, которое исполь­зуют для обозначения связи между какими-либо объектами. n-арным отношением, заданным на множестве М, называется подмножество n-й степени множества М. Для строгого математического описания любых связей между элементами двух множеств используется понятие бинарного отноше­ния. Бинарным отношением между множествами М и В называется под­множество R прямого произведения М х В. В этом случае, когда М = В, мы говорим просто об отношении R на М.

Совокупность множества А с заданным в нем бинарным отношением RМ² называется графом G:

G = < М, R >

где М- носитель графа (множество вершин); R - сигнатура графа (множество дуг).

Рассмотрим наиболее важные свойства бинарных отношений на примере графов:

1. Отношение R в множестве М называется рефлексивным, если

Свойство рефлексивности при задании отношения матрицей смежности характеризуется тем, что все элементы, лежащие на главной диагонали, отмечены (равны 1 или зачернены); при задании отноше­ния графом каждый элемент имеет петлю - дугу вида (m,m) (рис. 1, а). Рефлексивными бинарными от­ношениями в множестве М = {а, Ь, с) являются отношения, представленные с помощью графов на рис. 2, а, б, в, ж, з, к.

2. Отношение R в множестве М называется антирефлексивным, если

Свойство антирефлексивности при задании отношения матрицей смежности характеризуется тем, что ни один элемент, лежащий на главной диагонали, не отмечен (равен 0 или не зачернен); при задании отношения графом ни один его элемент не имеет петлю. Антирефлексивными бинарными отношениями в множестве М = {а, Ь, с} являются отношения, представленные на рис. 7, д, е, и, л.

Рис.1.

3. Отношение R в множестве М будем называть нерефлексивным, если оно не является ни рефлексив­ным, ни антирефлексивным. Нерефлексивными являются отношения на рис. 7, г, м, н.

4. Отношение R в множестве М называется симметричным, если

Матрица смежности симметричного отношения является симметричной относительно главной диа­гонали, а при задании отношения в виде графа следствием симметричности является наличие между всякой парой вершин, находящихся в отношении R, двух противоположно направленных дуг (рис. 6, б). Симметричными бинарными отношениями в множестве М = {а, Ь, с} являются отношения, представ­ленные на рис. 7, а, б, в.

5. Отношение R в множестве М называется антисимметричным, если

и

Антисимметричными бинарными отношениями в множестве М= {а, Ь, с} являются отношения, пред­ставленные на рис. 7, д, ж', з, и, н.

6. Отношение R в множестве М будем называть несимметричным, если оно не является ни симмет­ричным, ни антисимметричным. Несимметричными являются отношения на рис. 7, г, е, к, л, м.

7. Отношение R в множестве М называется транзитивным, если

В графе, задающем транзитивное отношение R, для всякой пары дуг таких, что конец первой совпа­дает с началом второй, существует третья дуга, имеющая общее начало с первой и общий конец со второй (рис. 6, в), - транзитивно замыкающая дуга. Транзитивными бинарными отношениями в множестве М = {а, Ь, с} являются отношения, представленные на рис. 7, а, б, в, д, ж, з, и, к, л.

8. Отношение R в множестве М называется антитранзитивным, если

и

Антитранзитивными бинарными отношениями в множестве M = {а, b, с} являются отношения, пред­ставленные на рис. 7, г, н.

9. Отношение R в множестве М будем называть нетранзитивным, если оно не является ни транзитив­ным, ни антитранзитивным. Нетранзитивными являются отношения на рис. 7, е, м.

Рис.2.