![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Задати бінарне відношення на множині А можна за допомогою списку пар, булевої матриці, матриці взаємин, таблиці фактів чи певної властивості відношення. Також відношення можна звести до орієнтованого графа, який можна подати різними способами, що буде розглянуто в методичних вказівках до основ теорії графів.
Найзручніший спосіб задати зв'язок між елементами двох множин – записати властивість, притаманну цьому відношенню.
Інший спосіб задати зв'язок між елементами двох множин – записати впорядковані пари елементів, що перебувають у цьому зв'язку.
Приклад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. Побудуємо матрицю взаємин для відношення у попередньому прикладі.
Володя | Наталя | Олена | Степан | |
Володя | “одногрупник” “подобається” | “подобається” | ||
Наталя | “одногрупник”, “подобається” | “подобається” | ||
Олена | “одногрупник” | |||
Степан | “одногрупник” |
Очевидно, якщо розглядати матрицю взаємин і таблицю фактів лише для одного відношення, то вони будуть фактично ідентичні булевій матриці і списку впорядкованих пар, але займатимуть більше місця у пам’яті комп’ютера.
Дата публикования: 2015-09-17; Прочитано: 3001 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!