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

Задати бінарне відношення на множині А можна за допомогою списку пар, булевої матриці, матриці взаємин, таблиці фактів чи певної властивості відношення. Також відношення можна звести до орієнтованого графа, який можна подати різними способами, що буде розглянуто в методичних вказівках до основ теорії графів.

Найзручніший спосіб задати зв'язок між елементами двох множин – записати властивість, притаманну цьому відношенню.

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

Приклад2.4. Нехай A ={1, 2, 3, 4, 6}, а відношення R задано властивістю

R= { (а,b)|а націло ділиться b }.

Як записати відношення R впорядкованими парами елементів?

Очевидно, що R ={(1,1), (2,1), (2,2), (3,1), (3,3), (4,1), (4,2), (4,4), (6,1), (6,2), (6,3), (6,6)}.▲

Матричний спосіб ґрунтується на поданні відношення R відповідною йому прямокутною булевою матрицею. Розглянемо , де множина , а множина .

Відповідна булева матриця

складатиметься з елементів

де кількість рядків матриці рівна кількості елементів множини A, а кількість стовбців рівна кількості елементів множини B, , .

Приклад 2.5. Для представлення матричним способом бінарних відношень, зручно вставити значення відповідного i -го елементу матриці A навпроти відповідних стовбців чи рядків. Для наведеного у прикладі 2.4 відношення матриця має такий вигляд:

Матриця взаємин і таблиця фактів є зручними, коли необхідно представити одразу кілька відношень, визначених на тій самій множині. Таблиця фактів будуються з елементу відношень, та відношень у які входить цей елемент.

Приклад 2.6. Розглянемо відношення R: “ X є одногрупником Y ” і відношення S: “ X подобається Y ” визначених на множині студентів { Володя, Ігор, Степан, Наталя, Олена, Оксана}. Відомо, що Володя і Наталя вчаться у групі ПI-11, а Степан і Олена у групі у групі ПI-12, Наталя подобається Володі і Степану, а Володя подобається Наталі і Олені. Представимо відношення між ними у вигляді таблиці фактів:

X	Y	Відношення
Володя	Наталя	“є одногрупником”, “подобається”
Володя	Олена	“подобається”
Наталя	Володя	“є одногрупником”, “подобається”
Наталя	Степан	“подобається”
Олена	Степан	“є одногрупником”
Степан	Олена	“є одногрупником”

Матриця відношень будується подібним чином до булевої матриці, тільки її елементами у i- му рядку та j -му стовбці будуть відношення, у які входять ці елементи.

Приклад 2.7. Побудуємо матрицю взаємин для відношення у попередньому прикладі.

	Володя	Наталя	Олена	Степан
Володя		“одногрупник” “подобається”	“подобається”
Наталя	“одногрупник”, “подобається”			“подобається”
Олена				“одногрупник”
Степан			“одногрупник”

Очевидно, якщо розглядати матрицю взаємин і таблицю фактів лише для одного відношення, то вони будуть фактично ідентичні булевій матриці і списку впорядкованих пар, але займатимуть більше місця у пам’яті комп’ютера.