Транзитивное замыкание отношения: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Транзитивное замыкание отношения''' (''[[Transitive closure of a relation]]'') -
'''Транзитивное замыкание отношения''' (''[[Transitive closure of a relation]]'')
для данного транзитивного бинарного отношения <math>R</math> такое отношение
для данного транзитивного бинарного отношения <math>\,R</math> такое отношение
<math>R^{\ast}</math>, что <math>xR^{\ast}y</math> тогда и только тогда, когда существует
<math>R^{\ast}</math>, что <math>xR^{\ast}y</math> тогда и только тогда, когда существует
последовательность
последовательность


<math>x = x_{0}, x_{1}, \ldots, x_{n} = y</math>
:::::<math>x = x_{0}, x_{1}, \ldots, x_{n} = y</math>


такая, что <math>n > 0</math> и
такая, что <math>\,n > 0</math> и


<math>x_{i}Rx_{i+1}, \; i = 0, 1, 2, \ldots, n-1.</math>
:::::<math>x_{i}Rx_{i+1}, \; i = 0, 1, 2, \ldots, n-1.</math>


Из свойства транзитивности следует, что
Из свойства транзитивности следует, что


<math>xRy \Rightarrow xR^{\ast}y</math>
:::::<math>xRy \Rightarrow xR^{\ast}y</math>


и что <math>R</math> является подмножеством <math>R_{\ast}</math>. Рефлексивное замыкание
и что <math>\,R</math> является подмножеством <math>R_{\ast}</math>. Рефлексивное замыкание
аналогично транзитивному замыканию, но включает и возможность <math>n=0</math>.
аналогично транзитивному замыканию, но включает и возможность <math>\,n=0</math>.
Транзитивное и рефлексивное замыкания играют важную роль в методах
Транзитивное и рефлексивное замыкания играют важную роль в методах
синтаксического анализа и компилирования, а также в методах отыскания
синтаксического анализа и компилирования, а также в методах отыскания
[[путь|путей]] на [[граф|графе]].
[[путь|путей]] на [[граф|графе]].
==Литература==
==Литература==
[Словарь]
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.

Навигация