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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Транзитивное замыкание отношения''' (''Transitive closure of a relation'') - для данного тр...)
 
Нет описания правки
Строка 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> тогда и только тогда, когда существует
Строка 18: Строка 18:
Транзитивное и рефлексивное замыкания играют важную роль в методах
Транзитивное и рефлексивное замыкания играют важную роль в методах
синтаксического анализа и компилирования, а также в методах отыскания
синтаксического анализа и компилирования, а также в методах отыскания
путей на графе.
[[путь|путей]] на [[граф|графе]].
==Литература==
==Литература==
[Словарь]
[Словарь]

Версия от 13:54, 7 февраля 2010

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

[math]\displaystyle{ x = x_{0}, x_{1}, \ldots, x_{n} = y }[/math]

такая, что [math]\displaystyle{ n \gt 0 }[/math] и

[math]\displaystyle{ x_{i}Rx_{i+1}, \; i = 0, 1, 2, \ldots, n-1. }[/math]

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

[math]\displaystyle{ xRy \Rightarrow xR^{\ast}y }[/math]

и что [math]\displaystyle{ R }[/math] является подмножеством [math]\displaystyle{ R_{\ast} }[/math]. Рефлексивное замыкание аналогично транзитивному замыканию, но включает и возможность [math]\displaystyle{ n=0 }[/math]. Транзитивное и рефлексивное замыкания играют важную роль в методах синтаксического анализа и компилирования, а также в методах отыскания путей на графе.

Литература

[Словарь]