Тема 4. Замыкание отношений. Транзитивное замыкание, рефлексивное замыкание. Алгоритм Уоршалла вычисления транзитивного замыкания.

Замыкание отношений.

Замыканием отношения R относительно свойства P называется такое множество R*, что:

1. RÌR*.

2. R^* обладает свойством P.

3. R^* является подмножеством любого другого отношения, содержащего R и обладающего свойством P.

Замыкание является весьма общим математическим понятием. Неформально говоря, замкнутость означает, что многократное выполнение допустимых шагов не выводит за определенные границы.

Пример

Пусть на множестве A={1,2,3,4} задано отношение R={(1,2),(3,4),(4,2)}. Видно, что отношение R не симметрично, не рефлексивно и не транзитивно. Замыканием R относительно свойства симметричности является R^*={(1,2),(3,4),(4,2);(2,1),(4,3),(2,4)}. Замыканием R относительно рефлексивности является R^*={(1,2),(3,4),(4,2);(1,1),(2,2),(3,3),(4,4)}. Замыканием R относительно транзитивности является множество R^*={(1,2),(3,4),(4,2);(3,2)}.