Транзитивное замыкание отношения

Материал из WikiGrapp
Перейти к:навигация, поиск

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

x = x_{0}, x_{1}, \ldots, x_{n} = y

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

x_{i}Rx_{i+1}, \; i = 0, 1, 2, \ldots, n-1.

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

xRy \Rightarrow xR^{\ast}y

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

Литература

  • Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.