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