Ориентированным графом

Def: Графом называется фигура на плоскости, состоящая из конечного числа точек – вершин графа – и линий, соединяющих некоторые из вершин. Линия, соединяющая какие-либо две вершины графа, называется ребром графа. Линии могут быть прямыми или кривыми. Точки пересечения некоторых ребер графа могут не являться вершинами графа. Граф, на котором указаны стрелками направления его ребер, называется ориентированным.

Существует простой способ представления бинарных отношений на конечных множествах ориентированными графами. Пусть А – непустое конечное множество и R – бинарное отношение на А, то есть . Представим элементы множества А точками на плоскости. Каждой паре при поставим в соответствие ориентированное ребро, идущее от точки a к точке b. Паре поставим в соответствие петлю с фиксированным направлением обхода (например, всегда против часовой стрелки):

Таким образом, бинарному отношению R ставится в соответствие следующая геометрическая фигура: точки плоскости, представляющие элементы множества , ориентированные ребра – каждой паре ставится в соответствие ориентированное ребро, идущее от точки a к точке b, или петля, если . Такая геометрическая фигура называется ориентированным графом отношения R или просто графом отношения R.

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

Пример 2. Построить граф отношения: .