Рефлексивність, симетричність, антисиметричність, транзитивність

Рефлексивність

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

Про відношення паралельності і рівності говорять, що вони володіють властивістю рефлексивності або, просто що вони рефлексивні.

Означення. Відношення R на множині Х називається рефлексивним, якщо про будь-який елемент множини Х можна сказати, що він знаходиться у відношенні R з самим собою.

	R рефлексивне на Х Û хRх для будь-якого хÎХ

 

 

Якщо відношення R рефлексивне, то в кожній вершині графа є петля.

Симетричність

Звернемо тепер увагу на графи відношень паралельності, перпендикулярності та рівності відрізків. Їх особливість в тому, що якщо є одна стрілка, яка з’єднує пару елементів, то обов’язково є і інша, яка з’єднує ті самі елементи, але в протилежному напрямку. Ці стрілки говорять про те, що:

1) якщо перший відрізок паралельний другому відрізку, то і другий паралельний першому;

2) якщо перший відрізок перпендикулярний другому відрізку, то і другий перпендикулярний першому;

3) якщо перший відрізок рівний другому відрізку, то і другий відрізок рівний і першому.

Означення. Відношення R множині Х називається симетричним, якщо із того, що елемент х знаходиться у відношенні R з елементом у, слідує, що і елемент у знаходиться у відношенні R з елементом х.

	R симетричне на ХÛхRу уRх

 

Граф симетричного відношення володіє особливістю: разом із кожною стрілкою, ідучої від х до у, граф містить і стрілку, йдучу від у до х.

Антисиметричність

Про відношення «довше» говорять, що воно має властивість антисиметричності або, просто, асиметричне.

Означення. Відношення R на множині Х називається асиметричним, якщо для різних елементів х та у із множини Х із того, що елемент х знаходиться у відношенні R з елементом у, слідує, що елемент у відношенні R з елементом х не знаходиться.

	R антисиметричне на Х Û хRу та х≠у уRх

 

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

Транзитивність

Зустрічаються відношення, які не володіють ні однією з властивостей.

Н.: розглянемо відношення «бути братом» на множині дітей однієї сім’ї. Нехай в сім’ї троє дітей: Коля, Міша, Таня. Тоді граф відношення «бути братом» буде таким:

Він показує, що дане відношення не володіє ні властивістю симетричності, ні властивості асиметричності.

Є ще одна особливість графів відношень паралельності, рівності та «довше»: якщо стрілка іде від першого елемента до другого елемента і від другого – до третього, то обов’язково є стрілка, яка іде від першого елемента до третього. Ця особливість графів відображає властивість даних відношень, яке називається властивістю транзитивності.

Означення. Відношення R на множині х називається транзитивним, якщо із того, що елемент х знаходиться у відношенні R з елементом у і елемент у знаходиться у відношенні R з елементом z, слідує, що елемент х знаходиться у відношенні R з елементом z.

	R транзитивне на ХÛхRу та уRz хRz

 

Граф транзитивного відношення з кожною парою стрілок від х до у та від у до z, має і стрілку, яка іде від х до z.