43

Глава 2

Бинарные отношения

2.1 Определения и примеры

Пусть заданы множества M и L.

Определение. Бинарным отношением называется подмножество

R µ M £ L:

Если R отношение, то будем писать: x 2 M; y 2 L, hx; yi 2 R, либо (x; y)2 R, либо xRy и говорить: x находится в отношении R к y, либо выполняется соотношение xRy.

Примеры 2.1.

1. S — множество групп на факультете, T — множество преподавателей на факультете.

R µ S £ T; xRy; x 2 S; y 2 T ;

xRy — группа x слушает лекции преподавателя y.

2.Отношение “быть старше”:

R µ M £ M; xRy — x старше y.

3.Отношение “быть севернее”: R µ M £ M; xRy — город x находится севернее города y.

4.Отношение “быть знакомым с”: xRy — x знаком с y.

5.Отношение <: h2; 5i 2<; h5; 2i 62<. J

За м е ч а н и е. Иногда бинарным отношением называют только R µ M £M, а R µ M £L называют соответствием. I

44 Глава 2. Бинарные отношения

Если R µ M £ M, то отношение также обозначают в виде упорядоченной пары hR; Mi, где R µ M £ M, и говорят — отношение R определено на множестве M. Для R µ M £ L обозначение hR; M; Li.

В общем случае рассматриваются n-арные (или n-мест- ные) отношения R µ M1 £ M2 £ ¢ ¢ ¢ Mn, то есть множество кортежей вида hx1; x2; : : : ; xni, где xi 2 Mi. В частности, все Mi могут совпадать.

Примеры 2.2.

1.Тернарное (трехместное) отношение hx; y; zi для x + y = z.

2.Расписание занятий.

Здесь мы подошли к способам задания отношений. Расписание — это пример табличного способа задания (точно такой же как и способ задания множества перечислением, ведь отношение — множество).

для любой пары hx; yi 2 M £ M.

3. Задание отношения матрицей.

Пусть jMj = n и элементы M = fx1; x2; ¢ ¢ ¢ ; xng пронумерованы целыми числами от 1 до n. Построим квадратную

матрицу R = krijk размерности n £ n. i-я строка матрицы со-

ответствует i-му элементу M, j-й столбец — j-му элементу

M,

Матрица отношения krijk содержит всю информацию о том, какие пары элементов из M принадлежат отношению

R.

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

С другой стороны, если задана (0-1)матрица размерности n £ n, и фиксирована нумерация на M, то тем самым на M задается некоторое отношение R. I

Матрица krijk, все элементы которой rij = 0, задает пустое отношение.

Матрица, все элементы которой rij = 1, задает полное (универсальное) отношение M £ M.

Матрица ¢ = k±ijk, где ½ 1; если i = j

0; если i =6 j

задает диагональное отношение (единичное, или отношение

равенства).

Матрица с элементами rij = 1 ¡ ±ij задает антидиагональное отношение.

Матрицы пустого, полного, диагонального и антидиагонального отношений не зависят от выбора нумерации элементов.

4. Дескриптивное задание отношения (с помощью характеристического предиката). В этом случае отношение

R = fhx; yijP (x; y)g

определяется как множество пар hx; yi, таких, что высказывание P (x; y) — истинно.

Пример 2.3. x выше y, если рост (x) > рост (y). J 5. Представление отношения графом.

Одно из определений графа: граф G = (M; R) задан, если задано множество M и бинарное отношение R на нем. Элементы множества M называются вершинами графа, а пары hx; yi 2 R – дугами (пары вида hx; xi называются петлями).

Для небольших размерностей удобно иллюстрировать отношения (графы) с помощью диаграммы. Элементы множества M (вершины графа) изображаются в виде точек (или небольших окружностей) на плоскости; если пара hx; yi 2 R, то x; y соединяют стрелкой, идущей из x в y. Эту диаграмму также называют графом. Граф, определенный таким образом, называется ориентированным (орграфом).

Таким образом, бинарное отношение и соответствующий ему граф являются представлениями друг друга: если задано бинарное отношение, то задан и соответствующий ему граф, и наоборот, если задан граф, то задано и соответствующее ему бинарное отношение.

Примеры 2.4.

1. Пустому отношению соответствует граф без дуг и петель (пустой граф). Все элементы матрицы пустого отношения – нулевые.

x3 x4

Рис. 2.1. Пустое отношение (пустой граф)

2. Диагональное отношение представляется графом, в каждой вершине которого имеется петля (заметим, что стрелку на петле можно и не изображать). Матрица отношения ¢ содержит единицы на главной диагонали, остальные элементы ¢ – нули.