5.2. Графы и отношения
Бинарное отношение на множестве 
представляет собой набор упорядоченных пар из элементов множества X. Например, если X — множество людей, a R — отношение «является сыном», то упорядоченная пара 
означает, что 
является сыном 
. Этот факт обозначается также 
Наиболее удачный способ представления бинарного отношения R на множестве X — с помощью ориентированного графа, вершины которого представляют собой элементы множества X, а дуги — упорядоченные пары элементов, определяющие отношение 
Рис. 5.7. Ориентированный граф, представляющий отношение «является делителем».
Например, на рис. 5.7 приведено представление отношения «является делителем» на множестве 
Рассмотрим множество 
и отношение R на множестве X:
1) R называется рефлексивным, если любой элемент 
входит в отношение R с самим собой, т. е. для любого 
2) R называется симметричным, если 
влечет за собой 
3) R называется транзитивным, если 
влечет за собой 
4) R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Если R — отношение эквивалентности на множестве S, то последнее однозначно разбивается на такие подмножества 
что элементы 
у множества S принадлежат 
тогда, когда 
Подмножества 
называют классами эквивалентности, порожденными отношением R на множестве 
Пусть множество X состоит из положительных целых чисел. Тогда
1) отношение «является делителем» рефлексивно и транзитивно;
2) отношение «равно» рефлексивно, симметрично и транзитивно, следовательно, является отношением эквивалентности. Ориентированный граф, представляющий рефлексивное отношение, называется рефлексивным ориентированным графом. Подобным образом определяются симметричные и транзитивные ориентированные графы. Относительно этих графов можно сделать следующие замечания:
1. В рефлексивном ориентированном графе при каждой вершине имеется инцидентная ей петля.
2. В симметричном ориентированном графе между любыми смежными вершинами имеются две противоположно ориентированные дуги. Поэтому, если ребро поставить в соответствие паре противоположно ориентированных дуг, можно рассматривать неориентированный граф как представление симметричного отношения.
3. Дуга 
присутствует в транзитивном графе G, если из вершины 
имеется ориентированный путь в вершину 
