304
правки
Изменения
Нет описания правки
== Построение транзитивного замыкания ==
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <math>R</math> - это такое как отношение <math>T</math>такое, что <math>aTb</math> тогда и только тогда, когда существуют <math>x_1, x_2, ..., x_n</math> такие, что <math>aRx_1</math>, <math>x_1Rx_2</math>, <math>x_2Rx_3</math>, ..., <math>x_{n-1}Rx_n</math>, <math>x_nRb</math>, то есть существует путь из вершины <math>a</math> в вершину <math>b</math> по рёбрам графа отношения.
Из этого определения можно легко понять, если <math>R</math> - отношение на конечном множестве размера n, то транзитивным замыканием такого отношения будет отношение
* Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть <math>aTb</math>, значит существуют <math>x_1, x_2, ..., x_n</math> такие, что <math>aRx_1, x_1Rx_2, ..., x_nRb</math>. Но из симметричности отношения <math>R</math> следует <math>bRx_n, x_nRx_{n-1}, ..., x_1Ra</math>, а, следовательно, <math>bTa</math>
* Транзитивное замыкание не сохраняет антисимметричность, например, для отношения <math>\{(a, b), (b, c), (c, a)\}</math> на множестве <math>\{a, b, c\}</math>
* Транзитивное замыкание транзитивного отношения - оно само
== Рефлексивно-транзитивное замыкание ==
Отношение <math>R^* = R^+ \cup R^0</math>, где
:<math>R^0 = \{(e, e) | e \in X\}</math>
иногда называют рефлексивно-транзитивным замыканием, хотя часто под "транзитивным замыканием" подразумевается именно <math>R^*</math>. Обычно различия между этими отношениями не являются значительными.
