390
правок
Изменения
→Доказательство корректности: Если отношение ТОЛЬКО антисимметрично, то граф может иметь цикл
'''Транзитивным замыканием''' (англ. ''transitive closure'') графа <tex> G = \left < V, E \right > </tex> называется граф <tex> G^* = \left < V, E^* \right > </tex>, где <tex> E^* = \left \{ (i, j) \in V \times V \mid i \underset{G}{\leadsto} j \right \} </tex>.
}}
Так как отношение антисимметричнои транзитивно, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.
Докажем теорему, из которой следует алгоритм.
Так как множества <tex> E^- </tex> и <tex> \left \{ k \underset{G}{\to} m \mid \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, то есть равны.
}}
===Ассимптотика===
Для множества <tex>X</tex> c количеством элементов <tex>n</tex> алгоритм работает за <tex>O(n^3)</tex>, так как в каждом из трёх циклов мы пробегаемся по всем элементам множества <tex>X</tex>.
