2.7. Ориентированные графы и бинарные отношения

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

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

Бинарное отношение, заданное некоторым ориентированным графом, иногда можно предстагить более простым способом, не требующим полного перечисления. Например, граф на рис. 2.7, является фактически одним из возможных представлений отношения включения определенного на подмножествах множества, содержащего три элемента. Это видно из рис. 2.8, где вершины отождествляются с соответствующими подмножествами множества

Заметим, что в общем случае не имеет смысла брать бинарное отношение, заданное первоначально в некоторой «замкнутой форме», и строить соответствующий граф для изучения свойства этого отношения. С другой стороны, по данному ориентированному графу часто невозможно найти простую замкнутую форму отношения, которому он соответствует. В тех случаях, когда это удается сделать, средства одной теории могут быть применены для решения задач, возникших в другой.

Рис. 2.7.

Рис. 2.8.

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

Воспользуемся для описания специального класса ориентированных графов, не имеющих строго параллельных ребер, некоторой терминологией бинарных отношений. Рефлексивным графом будем называть граф, имеющий петлю в каждой вершине. Симметрическим графом является граф, в котором каждой дуге соответствует дуга Транзитивным графом называется граф, в котором существование дуг и означает существование дуги Из этого следует, что в транзитивном графе существование любого пути из вершины в вершину у означает существование дуги из и в у.

Граф, показанный на рис. 2.8, является транзитивным, но нерефлексивным и несимметрическим. В действительности он является антисимметрическим в том смысле, что существование дуги а ( гарантирует отсутствие дуги

Упражнения

(см. скан)