Замыкание (отношения)

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

1. $R \subset 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)}.

См. также

• Алгоритм Уоршелла