Рефлексивність
Розглянемо графи відношень паралельності та рівності. Вони мають петлі, які говорять про те, що який би відрізок із множини Х ми не взяли, про нього можна сказати, що він паралельний самому собі чи що він рівний самому собі.
Про відношення паралельності і рівності говорять, що вони володіють властивістю рефлексивності або, просто що вони рефлексивні.
Означення. Відношення R на множині Х називається рефлексивним, якщо про будь-який елемент множини Х можна сказати, що він знаходиться у відношенні R з самим собою.
|
Якщо відношення R рефлексивне, то в кожній вершині графа є петля.
Симетричність
Звернемо тепер увагу на графи відношень паралельності, перпендикулярності та рівності відрізків. Їх особливість в тому, що якщо є одна стрілка, яка з’єднує пару елементів, то обов’язково є і інша, яка з’єднує ті самі елементи, але в протилежному напрямку. Ці стрілки говорять про те, що:
1) якщо перший відрізок паралельний другому відрізку, то і другий паралельний першому;
2) якщо перший відрізок перпендикулярний другому відрізку, то і другий перпендикулярний першому;
3) якщо перший відрізок рівний другому відрізку, то і другий відрізок рівний і першому.
Означення. Відношення R множині Х називається симетричним, якщо із того, що елемент х знаходиться у відношенні R з елементом у, слідує, що і елемент у знаходиться у відношенні R з елементом х.
|
уRх
Граф симетричного відношення володіє особливістю: разом із кожною стрілкою, ідучої від х до у, граф містить і стрілку, йдучу від у до х.
Антисиметричність
Про відношення «довше» говорять, що воно має властивість антисиметричності або, просто, асиметричне.
Означення. Відношення R на множині Х називається асиметричним, якщо для різних елементів х та у із множини Х із того, що елемент х знаходиться у відношенні R з елементом у, слідує, що елемент у відношенні R з елементом х не знаходиться.
|
Граф антисиметричного відношення володіє особливістю: якщо дві вершини графа з’єднані стрілкою, то ця стрілка тільки одна. Справедливе і зворотне твердження: граф, вершини якого з’єднуються тільки однією стрілкою, являється графом антисемитричного відношення.
Транзитивність
Зустрічаються відношення, які не володіють ні однією з властивостей.
Н.: розглянемо відношення «бути братом» на множині дітей однієї сім’ї. Нехай в сім’ї троє дітей: Коля, Міша, Таня. Тоді граф відношення «бути братом» буде таким:
Він показує, що дане відношення не володіє ні властивістю симетричності, ні властивості асиметричності.
Є ще одна особливість графів відношень паралельності, рівності та «довше»: якщо стрілка іде від першого елемента до другого елемента і від другого – до третього, то обов’язково є стрілка, яка іде від першого елемента до третього. Ця особливість графів відображає властивість даних відношень, яке називається властивістю транзитивності.
Означення. Відношення R на множині х називається транзитивним, якщо із того, що елемент х знаходиться у відношенні R з елементом у і елемент у знаходиться у відношенні R з елементом z, слідує, що елемент х знаходиться у відношенні R з елементом z.
|
Граф транзитивного відношення з кожною парою стрілок від х до у та від у до z, має і стрілку, яка іде від х до z.
