Изменения

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

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

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

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

Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <mathtex>R</mathtex> - это такое как отношение <mathtex>T</mathtex>такое, что <mathtex>aTb</mathtex> тогда и только тогда, когда существуют <mathtex>x_1, x_2, ...\ldots, x_n</mathtex> такие, что <mathtex>aRx_1, x_1Rx_2, x_2Rx_3, \ldots, x_{n-1}Rx_n, x_nRb</tex>, то есть существует путь из вершины <tex>a</mathtex>в вершину <tex>b</tex> по рёбрам графа отношения. {{Теорема|statement=Если <tex>R</tex> {{---}} отношение на конечном множестве размера n, то транзитивным замыканием такого отношения будет отношение:<mathtex>x_1Rx_2T = \bigcup\limits_{i = 1}^{n} R^i</mathtex>. |proof=Действительно, если по рёбрам графа есть путь длины <mathtex>l >x_2Rx_3n</mathtex>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути.Длину пути можно уменьшать до того, пока она не будет не превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <tex>n</tex> можно "выкинуть" из объединения.}} Для построения транзитивного замыкания отношения, заданного матрицей смежности, используется [[алгоритм Флойда — Уоршелла]]. == Свойства транзитивного замыкания ==* Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение* Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть <tex>aTb</tex>, значит существуют <tex>x_1, x_2, \ldots, x_n</tex> такие, что <tex>aRx_1, x_1Rx_2, \ldots, x_nRb<math/tex>x_. Но из симметричности отношения <tex>R</tex> следует <tex>bRx_n, x_nRx_{n-1}Rx_n, \ldots, x_1Ra</mathtex>, а, следовательно, <mathtex>x_nRbbTa</mathtex>* Транзитивное замыкание не сохраняет антисимметричность, например, то есть существует путь из вершины для отношения <mathtex>\{(a, b), (b, c), (c, a)\}</mathtex> в вершину на множестве <mathtex>\{a, b, c\}</mathtex> по рёбрам графа * Транзитивное замыкание транзитивного отношения{{---}} оно само == Рефлексивно-транзитивное замыкание ==Отношение <tex>R^* = R^+ \cup R^0</tex>, где:<tex>R^0 = \{(e, e) | e \in X\}</tex>иногда называют рефлексивно-транзитивным замыканием, хотя часто под "транзитивным замыканием" подразумевается именно <tex>R^*</tex>. Обычно различия между этими отношениями не являются значительными.

Из этого определения можно легко понять, если <math>R</math> == См. также ==* [[Транзитивное_отношение|Транзитивное отношение]]* [[Алгоритм_Флойда_—_Уоршалла|Алгоритм Флойда- отношение на конечном множестве размера n, то транзитивным замыканием такого Уоршалла (построение транзитивного замыкания отношения будет отношение)]]:<math>T = \bigcup\limits_{i = 1}^{n} R^i</math>.* [[Транзитивный_остов|Транзитивный остов]]

Действительно, если по рёбрам графа есть путь длины <math>l > n<== Источники информации ==*[http:/math>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути/en.wikipedia. Длину пути можно уменьшать до того, как она не будет превосходить количество вершин графа org/wiki/Transitive_closure Wikipedia | Transitive closure (элементов множестваангл.), а значит, все пути длины более, чем <math>n</math> можно "выкинуть" из объединения.]