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

2012-04-10T17:20:24Z

109.188.200.204:

{{Определение
|definition=
'''Транзитивным замыканием''' <tex>\mathrm{TrCl}(R)</tex> отношения <tex>R</tex> на множестве <tex>X</tex> называется пересечение всех транзитивных отношений, содержащих <tex>R</tex> как подмножество (иначе, минимальное [[транзитивное отношение]], содержащее <tex>R</tex> как подмножество).}}
Например, если <tex>V</tex> - множество городов, и на них задано отношение <tex>R</tex>, означающее, что если <tex>x R y</tex>, то "существует автобусный маршрут из x в y", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из x в y, передвигаясь на автобусах".

== Существование и описание ==
Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее <tex>R</tex> как подмножество (например, <tex>X \times X</tex>).

{{Теорема
|statement=
Докажем, что <tex>R^+</tex> является транзитивным замыканием отношения <tex>R</tex>.
:<tex>R^+ = \bigcup\limits_{i \in \mathbb{N}} R^i</tex>

|proof=
* <tex>R \subset R^+</tex> по определению <tex>R^+</tex>
* <tex>R^+</tex> транзитивно. Пусть <tex>a R^+ b</tex> и <tex>b R^+ c</tex>. Это значит, что существуют i, j такие, что <tex>a R^i b</tex> и <tex>b R^j c</tex>. Но тогда <tex>a R^{i+j} c</tex>, и, так как <tex>R^{i+j} \subset R^+</tex>, то <tex>a R^+ c</tex>
* <tex>R^+</tex> - минимальное отношение, удовлетворяющее представленным требованиям. Пусть <tex>T</tex> - транзитивное отношение, содержащее <tex>R</tex> в качестве подмножества. Покажем, что <tex>R^+ \subset T</tex>. <tex>R \subset T \Leftrightarrow R^i \subset T</tex> для любого натурального <tex>i</tex>. Докажем это по индукции. <tex>R^1 = R \subset R^+</tex>, как было показано выше. Пусть верно для любого <tex>i \le k</tex>. Пусть <tex>a R^{k+1} c</tex>. Но тогда существует <tex>b: aR^kb</tex> и <tex>bRc</tex>, но <tex>R \subset T, R^k \subset T</tex>, следовательно <tex>aTb, bTc</tex>. Из транзитивности <tex>T</tex> следует, что <tex>aTc</tex>, следовательно <tex>R^{k+1} \subset T</tex>.
}}

== Построение транзитивного замыкания ==
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <tex>R</tex> как отношение <tex>T</tex> такое, что <tex>aTb</tex> тогда и только тогда, когда существуют <tex>x_1, x_2, ..., x_n</tex> такие, что <tex>aRx_1</tex>, <tex>x_1Rx_2</tex>, <tex>x_2Rx_3</tex>, ..., <tex>x_{n-1}Rx_n</tex>, <tex>x_nRb</tex>, то есть существует путь из вершины <tex>a</tex> в вершину <tex>b</tex> по рёбрам графа отношения.

{{Теорема
|statement=
Если <tex>R</tex> - отношение на конечном множестве размера n, то транзитивным замыканием такого отношения будет отношение
:<tex>T = \bigcup\limits_{i = 1}^{n} R^i</tex>.

|proof=
Действительно, если по рёбрам графа есть путь длины <tex>l > n</tex>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, пока она не будет не превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <tex>n</tex> можно "выкинуть" из объединения.
}}

Для построения транзитивного отношения, заданного матрицей смежности, используется [[алгоритм Флойда — Уоршелла]].

== Свойства транзитивного замыкания ==
* Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение
* Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть <tex>aTb</tex>, значит существуют <tex>x_1, x_2, ..., x_n</tex> такие, что <tex>aRx_1, x_1Rx_2, ..., x_nRb</tex>. Но из симметричности отношения <tex>R</tex> следует <tex>bRx_n, x_nRx_{n-1}, ..., x_1Ra</tex>, а, следовательно, <tex>bTa</tex>
* Транзитивное замыкание не сохраняет антисимметричность, например, для отношения <tex>\{(a, b), (b, c), (c, a)\}</tex> на множестве <tex>\{a, b, c\}</tex>
* Транзитивное замыкание транзитивного отношения - оно само

== Рефлексивно-транзитивное замыкание ==
Отношение <tex>R^* = R^+ \cup R^0</tex>, где
:<tex>R^0 = \{(e, e) | e \in X\}</tex>
иногда называют рефлексивно-транзитивным замыканием, хотя часто под "транзитивным замыканием" подразумевается именно <tex>R^*</tex>. Обычно различия между этими отношениями не являются значительными.

== Ссылки ==
*[http://en.wikipedia.org/wiki/Transitive_closure Transitive closure (англ.)]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Отношения ]]

Викиконспекты - Вклад участника [ru]

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