Графы и бинарные отношения.

Между ориентированными графами без кратных ребер с множеством вершин V = {v₁, ..., v_n} и бинарными отношениями на множестве V существует взаимно-однозначное соответ­ствие: отношению R соответствует ориентированный граф G (R), в кото­ром ребро (v', v") существует, если и только если выполнено v'Rv". Аналогичное взаимно-однозначное соответствие существует между симметрическими бинарными отношениями и неориентированными графами.

Рассмотрим теперь соответствие между операциями над отноше­ниями и операциями над графами. Каждое отношение R имеет отрица­ние R, истинное тогда и только тогда, когда R ложно. Например, для отношения равенства v' = v" отрицанием является отношение неравенства v' v", для отношения ортогональности v' v", опре­деленного для элементов векторного пространства, отрицанием является отношение отличия скалярного произведения от 0: (v', v") 0. Граф G ( R) является дополнением графа G (R) по отношению к полному ориентированному графу К(V) с множеством вершин V, на котором задано рассматриваемое бинарное отношение R, и множеством дуг E (К (V)) = V X V. Граф G (R^-1), где R^-1 — отношение, обратное R, отличается от графа G(R) тем, что направления всех дуг заменены на обратные.

Отношение R' содержит отношение R, если они определены на од­ном и том же множестве V и из v' Rv" следует v' R' v". В этом случае гово­рят также, что отношение R' следует из отношения R, и пишут R' R. Соответствующие графы G(R) и G(R') имеют одно и то же множество вершин V, а множество Е(R) ребер первого является подмножеством множества Е(R) ребер второго. Таким образом, G(R) является суграфом графа G (R'), т. е. G (R') G (R).

Для любых бинарных отношений R₁ и R₂, заданных на одном и том же множестве V, можно определить сумму (объединение) R₁ U R₂ и пересечение

v' (R₁U R₂) v" = v' R₁ v" V v' R₂ v";

v' (R₁ R₂) v" = v' R₁ v" & v' R₂ v".

Соответствующие графы также являются суммой и пересечением

G(R₁U R₂) = G(R₁) U G(R₂);

G(R₁ R₂) = G(R_l) G(R₂).

Некоторые типы графов хорошо описываются на языке бинарных отношений. Например, нуль-граф

Æ(V), не имеющий ребер, соответ­ствует нулевому отношению v'0v", ложному для любой пары { v', v"} V > V; полному ориентированному графу К (V) соответствует уни­версальное отношение v'U v", всегда истинное.

Если R рефлексивно, то G (R) имеет петли во всех вершинах; если R антирефлексивно, то G (R) не имеет петель. Если R транзитивно, то в графе G (R) для каждой пары ребер (v', v") и (v", v"') имеется замыкаю­щее ребро (v', v"').