Транзитивное замыкание отношений

Определение 4.1. Отношение называется транзитивным замыканием отношения , определенного на множестве M, тогда и только тогда, когда существуют такие , что .

Пример

На множестве N определено отношение . Тогда транзитивное замыкание этого отношения для значений 1<2<…<6 будет отношение 1<6. (Рисунок 4.1)

Рисунок 4.1

Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком».

Транзитивным замыканием отношения «иметь общую стену» для жильцов одного дома является отношение « жить на одном этаже».

Пример. Пусть R задано на M, . R транзитивно, если для любых a,b,с из аRb и bRс следует аRс. Вматрице такого отношения должно выполняться следующее условие: если в i-й строке стоит единица, например в j-й координате (столбце) строки, т.е. , то всем единицам в j-й строке (пусть этим единицам соответствуют k-е координаты такие, что ) должны соответствовать единицы в i-й строке в тех же k-хкоординатах, т.е. (и, может быть, еще и в других координатах). Это условие иллюстрируется на рисунке 4.2, где кружком выделена единица , для которой производится проверка условия, а стрелками показана последовательность проверки данного условия.

В матрице транзитивного отношения это условие должно выполняться для любых таких, что . И наоборот, если в матрице R имеется хотя бы одна единица , для которой данное условие не выполняется, то R не транзитивно.

Рисунок 4.2