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

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

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

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

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

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