Рефлексивное замыкание отношений

Пусть тождественное отношение Е состоит из упорядоченных пар самого себя – . Тогда R*=R°ÈE (R* – рефлексивное замыкание, а R° – транзитивное замыкание).

Если R транзитивно и рефлексивно, то R*=R.

Пример. Используя R – отношение на N такое, что получим .

Алгоритм Уоршалла.

Вход: отношение, заданное матрицей R.

Выход: транзитивное замыкание отношения, заданное матрицей Т.

S:= R

for i from 1 to n do

for j from 1 to n do

for k from 1 to n do

T[j, k]:= S[j, k] V S[j, i] & S[i, k]

End for

End for

S:= T