4.4 Бинарные отношения и графы

Бинарное отношение R определяется как соотношение A R B, которое выполняется для некоторых пар элементов заданного множества V. В соответствии с этим БО может быть представлено в виде графа с множеством вершин V, у которого ориентированное ребро (А, B) присутствует тогда и только тогда, когда выполняется отношение A R B.

Обратно, любой граф определяет БО R на множестве своих вершин V, если наличию ребра (А, B) соответствует выполнение A R B.

Имеется, однако, небольшое различие между этими двумя понятиями. Приписывать отношению кратность обычно нет надобности. Поэтому говорить о взаимно-однозначном соответствии между БО и графом можно лишь для графа с однократными ребрами.

Нуль-граф отвечает нулевому отношению А Æ B, которое не выполняется ни для одной пары элементов.

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

Каждое отношение R имеет дополнительное отношение (или отрицание) , которое выполняется тогда и только тогда, когда не выполняется R. Граф G() является дополнительным графом для G(R) по отношению к полному графу U, определенному на множестве вершин V.

G() = U(V) - G(R),
или U(V) = G(R) È G().

Для любого отношения R существует обратное отношение R*:

Соотношение B R* а выполняется тогда и только тогда, когда выполняется А R B.

Очевидно, что граф G(R*) есть обратный граф для G(R), то есть G(R) и G(R*) – это ориентированные графы с вершинами V и противоположной ориентацией ребер.

Если R* = R (т. е. A R B = A R* B), то такое отношение называется симметричным. В этом случае вершины А и B должны быть соединены ориентированными ребрами (двумя) по одному в каждом направлении. Это соответствует одному неориентированному ребру. Таким образом, симметричным отношениям соответствуют неориентированные графы.

Кроме симметрии у отношений есть свойство рефлексивности: А R а Выполняется для любых А Î V. Соответствующий граф имеет петлю в каждой вершине.

Если А R а не выполняется ни для какой А Î V, то отношение антирефлексивно, и ему соответствует граф без петель.

Если из A R B и B R с следует А R с, то отношение транзитивно. Ему соответствует граф G(R), в котором если есть ребра (A, B) и (B, С), то всегда есть и ребро (А, С), их замыкающее.

< Предыдущая		Следующая >