Свойства отношений

1. Рефлексивность. Отношение называется рефлексивным, если . Тогда:

а) в матрице рефлексивного отношения на главной диагонали заданы 1;

б) в графе при каждой вершине имеется петля.

Соответственно, если отношение антирефлексивно, то выражение вида не является верным, в этом случае диагональные элементы матрицы равны 0.

2. Симметричность. Отношение - симметрично, если из вытекает . Тогда:

а) матрица отношения симметрична, т.е. .

б) каждая вершина графа имеет исходящую дугу и входящую дугу .

3. Асимметричность. Для пары выполняется либо , либо , т.е. если выполняется, то нет. В этом случае граф не может содержать одновременно дуги и (содержит одну из этих дуг).

4. Антисимметричность. Для антисимметричного отношения выражения и справедливы тогда, когда . Для антисимметричного отношения граф не может одновременно содержать дуги и при .

5. Транзитивность. Из и следует .

6. Ацикличность. Из , ,…, следует, что (т.е. путь на графе не является циклом).