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

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

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

Другими словами, $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)\}$.

См. также

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