304
правки
Изменения
Нет описания правки
Для построения транзитивного отношения множества, заданного матрицей смежности, используется алгоритм Флойда-Уоршала.
== Свойства транзитивного замыкания ==
* Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение
* Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть <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>
