3.2. Представление отношений

Возможны несколько специальных способов задания отношений.

Представление отношений диаграммами

Пусть   А B. Это отношение между элементами множеств А и B. Если множества A и B счетные, то их можно представить на плоскости множествами точек из двух непересекающихся областей, обозначаемых как A и B. Если (a, b) , то точки, соответствующие a и b, соединяются ориентированной дугой. Такое представление аналогично диаграммам для отображений. При этом для диаграмм отношений допускается как многозначность связи элементов A с элементами B, так и отсутствие связей.

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

Табличное задание отношений

Если множества A и B являются конечными и A = {a₁,..., a_m}, B= {b₁, ... , b_n}, то всякое отношение   А B можно представить таблицей, состоящей из m строк и n столбцов, имеющей следующий вид:

	b1 bj bn
a1 ai am	. . . . . . . . i,j . . . . . . . . .

В этой таблице значение всякого элемента _i,_j определяется соотношением:

1, если (a_i, b_j)

_i,_j =

0, если (a_i, b_j).

Всякая заполненная нулями и единицами таблица, состоящая из m строк и n столбцов, представляет некоторое отношение на множествах A и B, составленное из всех таких пар (a_i, b_j), для которых _i,_j = 1.

Определенное соотношение таблиц и отношений на множествах является биективным. Табличное представление отношений удобно для программной реализации алгоритмов решения задач, связанных с отношениями.

3.3. Операции над отношениями

ОПРЕДЕЛЕНИЕ

Пусть А B и B C. Тогда отношение А C называется произведением отношений и , если выполнено условие:

.

Произведение двух отношений и обозначается как ◦ или как . Произведение отношений обладает свойством ассоциативности.

ТЕОРЕМА 3.1

Если заданы отношения А B, B C, С D, то справедливо равенство ◦( ◦ ) = ( ◦ )◦ .

Доказательство

1. Покажем, что ( ) ( ) .

Действительно, пусть (a, d) ( ), т.е. существует b такое, что a  b и b( )d. Тогда существует такое с, что b с и с d. Поэтому a( )с. Это означает, что a(( ) )d. Следовательно, справедливо включение ( ) ( ) .

2. Покажем, что ( ) ) ( ).

Пусть (a, d) ( ) . Тогда существует такое с, что a ( )с и с d. Поэтому найдется такой элемент b, для которого справедливы соотношения: a b и b с. Поэтому b( )d, т.е. a ( )d.

Следовательно, имеет место включение множеств:

( ) ( ) .

Значит, ( ) = ( ) .

Доказательство окончено.

Заметим, что произведение отношений является аналогом произведения отображений. Для того, чтобы увидеть такую аналогию достаточно сопоставить произвольной функции f: A B отношение {(x, f(x))  xA}, которое называется графиком этой функции. Тогда, если отображение h является произведением отображений g и f, то график h произведением графиков для g и f.

Рассмотрим пример. Пусть A  это множество людей, а C  множество городов.

Пусть на этих множествах определены отношения:  A  A  отношение знакомства людей, а  A  B  отношение проживания в некотором городе. То есть, если справедливо соотношение ab, то это означает, что a знает b. Поэтому отношение  представляет такие связи между людьми игородами, для которого справедливость соотношения a( )c означает, что a имеет знакомого в городе c. При этом точное знание конкретного человека, связывающего a и c не требуется, поскольку для выполнимости отношения ac важно лишь его существование.