Изменения

{{В разработкеОпределение|definition='''Транзитивным замыканием''' (англ. ''transitive closure'') <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>, то "существует автобусный маршрут из <tex> x</tex> в <tex> y</tex>", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из <tex> x</tex> в <tex> y</tex>, передвигаясь на автобусах".

'''Транзитивным == Существование и описание ==Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее <tex>R</tex> как подмножество (например, <tex>X \times X</tex>). {{Теорема|statement=Докажем, что <tex>R^+</tex> является транзитивным замыканием''' отношения <mathtex>R</tex>.:<tex>R^+ = \mathrmbigcup\limits_{TrCli \in \mathbb{N}}(R)^i</tex> |proof=* <tex>R \subset R^+</tex> по определению <tex>R^+</tex>* <tex>R^+</tex> транзитивно. Пусть <tex>a R^+ b</mathtex> отношения и <mathtex>b R^+ c</mathtex> на множестве . Это значит, что существуют <mathtex>Xi, j </mathtex> называется пересечение всех транзитивных отношенийтакие, содержащих что <mathtex>a R^i b</mathtex> и <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> {{---}} транзитивное отношение, содержащее <mathtex>R</mathtex> в качестве подмножества). НапримерПокажем, если что <tex>R^+ \subset T</tex>. <tex>R \subset T \Leftrightarrow R^i \subset T</tex> для любого натурального <mathtex>Vi</mathtex>. Докажем это по индукции. <tex>R^1 = R \subset R^+</tex> - множество городов, как было показано выше. Пусть верно для любого <tex>i \leqslant 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> как отношение <mathtex>RT</tex> такое, что <tex>aTb</mathtex> тогда и только тогда, когда существуют <tex>x_1, x_2, \ldots, означающееx_n</tex> такие, что если x R y<tex>aRx_1, x_1Rx_2, x_2Rx_3, \ldots, x_{n-1}Rx_n, x_nRb</tex>, то "есть существует автобусный маршрут путь из x вершины <tex>a</tex> в y"вершину <tex>b</tex> по рёбрам графа отношения. {{Теорема|statement=Если <tex>R</tex> {{---}} отношение на конечном множестве размера n, то транзитивным замыканием этого такого отношения будет отношение "существует возможность добраться из x :<tex>T = \bigcup\limits_{i = 1}^{n} R^i</tex>. |proof=Действительно, если по рёбрам графа есть путь длины <tex>l > n</tex>, то он проходит по всем вершинам графа, а, значит, в yэтом пути есть цикл и его можно отбросить, передвигаясь на автобусахтем самым уменьшив длину пути. Длину пути можно уменьшать до того, пока она не будет не превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <tex>n</tex> можно "выкинуть"из объединения.}}

Для построения транзитивного замыкания отношения, заданного матрицей смежности, используется [[алгоритм Флойда — Уоршелла]]. == Существование и описание Свойства транзитивного замыкания ==* Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение* Транзитивное замыкание существует для любого симметричного отношениясимметрично. Для этого отметимДействительно, пусть <tex>aTb</tex>, значит существуют <tex>x_1, x_2, \ldots, x_n</tex> такие, что пересечение любого множества транзитивных отношений транзитивно<tex>aRx_1, x_1Rx_2, \ldots, x_nRb</tex>. Более тогоНо из симметричности отношения <tex>R</tex> следует <tex>bRx_n, x_nRx_{n-1}, \ldots, x_1Ra</tex>, а, следовательно, <tex>bTa</tex>* Транзитивное замыкание не сохраняет антисимметричность, например, для отношения <tex>\{(a, b), (b, c), (c, a)\}</tex> на множестве <tex>\{a, обязательно существует b, c\}</tex>* Транзитивное замыкание транзитивного отношения {{---}} оно само == Рефлексивно-транзитивное отношение, содержащее замыкание ==Отношение <mathtex>R^* = R^+ \cup R^0</mathtex> как подмножество (например, где:<mathtex>R^0 = \{(e, e) | e \in X \times X}</tex>иногда называют рефлексивно-транзитивным замыканием, хотя часто под "транзитивным замыканием" подразумевается именно <tex>R^*</mathtex>. Обычно различия между этими отношениями не являются значительными. == См. также ==* [[Транзитивное_отношение|Транзитивное отношение]]* [[Алгоритм_Флойда_—_Уоршалла|Алгоритм Флойда-Уоршалла (построение транзитивного замыкания отношения).]]* [[Транзитивный_остов|Транзитивный остов]]

Докажем, что <math>R^+<== Источники информации ==*[http:/math> является транзитивным замыканием отношения <math>R</math>en.wikipedia.:<math>R^+ = \bigcup\limits_{i \in \mathbb{N}} R^i<org/wiki/math>Transitive_closure Wikipedia | Transitive closure (англ.)]

* <math>R \subset R^+</math> по определению <math>R^+</math>* <math>R^+</math> транзитивно. Пусть <math>a R^+ b</math> и <math>b R^+ c</math>. Это значит, что существуют i, j такие, что <math>a R^i b</math> и <math>b R^j c</math>. Но тогда <math>a R^{i+j} b</math>, [[Категория:Дискретная математика и, так как <math>R^{i+j} \subset R^+ \leftarrow a R^+ b</math>алгоритмы]]* <math>R^+</math> - минимальное отношение, удовлетворяющее представленным требованиям. Пусть <math>T</math> - транзитивное отношение, содержащее <math>R</math> в качестве подмножества. Покажем, что <math>R^+ \subset T</math>. <math>R \subset T \longleftrightarrow R^i \subset T</math> для любого натурального <math>i</math>[[Категория: Отношения ]]