Page 37 - 2589

A    x 1 ,y 1   ,, x 1 y 3   ,, x 2 y 1   ,, x 2 y 3   ,, x 3 y 1   ,, x 3 y 2   ,, x 3 y 4   ,, x 5 y 2 ,

 , yx   ,, x y   ,, x y   ,, x y   ,, x y .
4 3 5 4 5 2 4 3 5 4
Перерізи за всіма елементами множини X представлені у
таблиці:
x x x x x
1 2 3 4 5
{y , y } {y , y , y } {y , y , y } {y } {y , y }
1 3 1 3 4 1 2 4 3 2 4

3.2 Представлення відношень

Подання бінарних відношень за допомогою матриці та
графа. З попереднього зрозуміло, що відношення може бути

подане за допомогою фактора множини. Розглянемо ще два
способи подання скінченного бінарного відношення: за
допомогою матриці й графа.

Матричний спосіб ґрунтується на поданні відношення
A  X  Y відповідною йому прямокутною таблицею (матрицею),
що складається з нулів та одиниць, де стовпці – перші
координати, а рядки – другі, причому на перетині i-го стовпця і

j -го рядка буде 1, якщо виконується співвідношення Ayx j
, або 0
i
- якщо воно не виконується.

Приклад 3.3: Для заданого у прикладі 3.2 відношення A
матриця відношень має наступний вигляд:

x x x x x
1 2 3 4 5
y 1 1 1 0 0
1

y 0 0 1 0 1
2
y 1 1 0 1 0
3
y 0 1 1 0 1
4

Матриця повного відношення — це квадратна матриця, що
складається лише з одиниць; матриця тотожного (діагонального)

відношення – це квадратна матриця, яка складається з нулів та
одиниць по головній діагоналі; матриця порожнього відношення
– це квадратна матриця, що складається лише з нулів.
Відношення можна також зображати за допомогою

орієнтованого графа. Його вершини відповідають елементам

37