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

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

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

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

Пример

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

См. также

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