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

Бинарное отношение R определяется как соотношение

aRb, (5.4)

которое выполняется для некоторых пар элементов заданного множества V. В соответствии со сказанным выше, бинарное отношение может быть представлено в виде графа с множеством вершин V:

G(R) = G(V), (5.5)

так что ребро (а,b) принадлежит G тогда и только тогда, когда в R выполняется соотношение (5.4).

Обратно, любой граф без параллельных рёбер определяет бинарное отношение R на своем множестве вершин, если положить aRb для каждого eго ребра. Поэтому можно говорить о взаимно однозначном соответствии между бинарными отношениями на множестве V, с одной стороны, и графами с однократными ребрами на множестве вершин V – с другой.

Остановимся коротко на некоторых связях между бинарными отношениями и графами. Нуль-граф 0 отвечает нулевому отношению

a 0 b,

которое не выполняется ни для какой пары элементов. Полный граф U отвечает универсальному отношению

aUb,

которое выполняется для любой пары элементов.

Отношение R называется симметричным, если aRb имеет место в том и только в том случае, когда bRa.

Отношение R называется рефлексивным, если aRa для любого a из V. Соответствующий граф имеет петлю в каждой вершине. Отношение антирефлексивно, если aRa никогда не выполняется, т. е. граф не имеет петель.

Отношение R транзитивно, если из aRb и bRc следует aRc. Для графа это означает, что если G(R) содержит ребра (а,b) и (b,с), то он также содержит и замыкающее ребро (а,с) .

Отношения эквивалентности. Отношение R, определенное на множестве V, называется отношением эквивалентности, если оно:

1) рефлексивно,

2) симметрично,

3) транзитивно.

Все элементы из V, эквивалентные данному элементу a, образуют множество R(a), которое называется классом эквивалентности элемента а. Из рефлексивности R следует, что a принадлежит R(a). Если aRb и bRc, то из транзитивности следует aRc, так что R(а) содержит R(b). Поэтому из симметричности отношения мы получаем, что R(а) = R(b) при aRb.

Заметим, что два различных класса эквивалентности R(a) и R(c) не могут иметь какого-либо общего элемента b, так как иначе было бы R(a) = R(c). Таким образом, классы эквивалентности образуют разбиение V, т. е. разложение V на непересекающиеся подмножества. Обратно, по разбиению множества V однозначно порождается отношение эквивалентности R(V).

Если R рефлексивно и симметрично, но не является транзитивным, то оно называется отношением толерантности или «похожести». Например, таковым является отношение R, задаваемое следующим образом: R(a,b) если и только если X(a) – X(b)< , где X – признак, определённый для всех a,bV, >0 – вещественное число. Это отношение играет особую роль в анализе данных.

Частичное упорядочение. Отношение a ≤ b, заданное на произвольном множестве V, называется (нестрогим) частичным упорядочением, если оно рефлексивно, транзитивно и

из aRb и bRa следует, что a=b.

Соответствующий граф транзитивен, имеет петли, и любые две вершины в нем соединены не более чем одним ребром.

При строгом частичном упорядочении a<b, которое, также как и нестрогое, обладает свойством транзитивности, соответствующий граф не имеет петель, т.е. ни для какого a из V не выполняется aRa и ни при каких a,b невозможно, чтобы aRb и bRa.

Если для нестрогого или строгого частичного упорядочения для любых a,b из V, таких, что a≠b, выполняется aRb или bRa, то такое частичное упорядочение называется линейным.