Свойства бинарных отношений

1. Отношение R в множестве М называется рефлексивным , если для справедливо

В матрице смежности на главной диагонали стоят единицы.

В графе каждый элемент (вершина) имеет петлю – дугу вида (т,т):

2. Если для справедливо , то отношение R называется антирефлексивным.

В матрице смежности на главной диагонали стоят нули.

В графе нет ни одной петли.

3. Отношение R в множестве М называется симметричным, если для из условия следует , .

Матрица смежности симметрична относительно главной диагонали.

В графе любая пара вершин связана двумя противоположно направленными дугами:

4. Отношение R в множестве М называется антисимметричным, если для из условий и следует, что m_i = m_j или оба отношения и выполняются одновременно только тогда, когда т_i = m_j .

Матрица смежности несимметрична.

В графе могут быть петли, но связь между вершинами, если она имеется, отображается только одной дугой.

5. Отношение R в множестве М называется асимметричным (несимметричным), если для и взаимоисключаются, т.е. если , то и наоборот.

Матрица смежности несимметрична с нулевыми элементами на главной диагонали.

В графе петли отсутствуют, а вершины могут быть связаны только одной дугой.

Если отношение асимметрично, то оно и антирефлексивно.

6. Отношение R в множестве М называется транзитивным , если для из условий и следует, что .

В графе для всякой пары дуг таких, что конец первой совпадает с началом второй, существует третья дуга, имеющая общее начало с первой и общий конец со второй дугой. Эта дуга называется транзитивно замыкающей дугой: