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

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

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

Другими словами, $R^{\ast <!--\; \ast \; -->}$$R^{*}$ — минимальное надмножество $R$$R$, выдерживающее $P$$P$.

Пример Править

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

См. также Править

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