390
правок
Изменения
→Доказательство корректности: Если отношение ТОЛЬКО антисимметрично, то граф может иметь цикл
{{Определение
|definition=
'''Транзитивным остовом''' (или '''транзитивным сокращением''', англ. ''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
}}
== Алгоритм для антисимметричных отношений ==
===Описание алгоритма===
Пусть первоначально <tex>R^-=R</tex>. Чтобы найти минимальное отношение сделать <tex>R^-</tex> минимальным отношением на <tex>X</tex> такое, таким, что транзитивное замыкание <tex>R^-</tex> будет равно транзитивному замыканию <tex>R</tex>, рассмотрим всевозможные комбинации из каждых трёх элементов <tex>a, b, c \in X</tex>. И если Если для этих элементов существуют отношения существует каждое из отношений: <tex>aRb</tex>, <tex>bRc</tex> и <tex>aRc</tex>, {{---}} то избавимся от отношения исключим отношение <tex>aRc</tex> из <tex>R^-</tex>. После проверки всех комбинаций и исключения ненужных отношений получаем искомое отношение <tex>R^-</tex>.
=== Псевдокод ===
'''function''' <tex>f</tex>(<tex>X</tex>: '''List<T>''', <tex>R</tex>: '''List<T>'''):
'''foreach''' <tex>c \in X</tex>
'''if''' <tex>aRb</tex> '''and''' <tex>bRc</tex> '''and''' <tex>aRc</tex>
<tex>R^- = R^-\setminus(a, c)</tex>
===Доказательство корректности===
{{Определение
|definition=
'''Транзитивным замыканием''' (англ. ''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>.
==См. также==
