4194
правки
Транзитивное замыкание отношения: различия между версиями
Перейти к навигации
Перейти к поиску
Транзитивное замыкание отношения (посмотреть исходный код)
Версия от 18:13, 21 сентября 2011
, 21 сентября 2011нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||