Представление бинарных отношений графами.

Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.

Граф представляет собой конечный набор точек плоскости (вершины графа). Часть вершин может быть соединена отрезками со стрелками или без них (дуги и рёбра). Фигура, состоящая из вершин и дуг (отрезки со стрелками), называется ориентированным графом. Фигура, состоящая из вершин и рёбер (без направлений), называется неориентированным графом. Пусть, например, даны конечные множества , . Зададим на этих множествах бинарное отношение: .

 

 

 

 

Полученная фигура называется графом отношения . Любое бинарное отношение, заданное на конечных множествах, может быть представлено в виде некоторого графа. Верно и обратное: всякий граф представляет собой некоторое бинарное отношение на тех конечных множествах, на которых определён граф.

Т.к. бинарные отношения между элементами множеств и являются подмножествами , то можно говорить о включении одного бинарного отношения в другое, а также о пересечении и объединении бинарных отношений, или о дополнении к бинарному отношению. Дополнение бинарного отношения определяют следующим образом: . Другими словами пара тогда и только тогда, когда .

Если на множестве заданы произвольные бинарные отношения и , то можно рассматривать произведение бинарных отношений, а так же единичное, нулевое и обратное бинарные отношения.

Определение 7: Произведение определим следующим образом: элементы находятся в отношении тогда и только тогда, когда во множестве существует хотя бы один такой элемент , что и .

Произведение бинарных отношений обладает свойством ассоциативности, но не коммутативно.

Определение 8: Единичным бинарным отношением (или диагональю) называется бинарное отношение , такое, что тогда и только тогда, когда . Другими словами единичное бинарное отношение задается множеством всех пар, для всех .

Для любого бинарного отношения на множестве имеет место равенство: , т. е. коммутативность в этом случае выполняется.

Отметим, что пустое (нулевое) бинарное отношение играет роль нуля при умножении бинарных отношений. Для любого бинарного отношения имеет место свойство: .

Для любого бинарного отношения , обратное отношение определяется следующим образом: тогда и только тогда, когда . Очевидным является тот факт, что , а также .

Замечание: Понятие бинарного отношения допускает обобщения. Если на множестве задано одно или несколько - местных отношений, то такое множество называется моделью. Теория моделей – это один из разделов современной алгебры.