390
правок
Изменения
→Доказательство корректности: Если отношение ТОЛЬКО антисимметрично, то граф может иметь цикл
{{Определение
|definition=
'''Транзитивным остовом''' (или '''транзитивным сокращением''', англ. ''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
}}
__TOC__
== Алгоритм для антисимметричных отношений ==
===Описание алгоритма===
Пусть первоначально <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>'''):
<tex>R^- = R</tex>
'''foreach''' <tex>a \in X</tex>
'''foreach''' <tex>b \in X</tex>
'''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>
===Доказательство корректности===
Для удобства представим отношение в виде [[Основные определения теории графов|графа]]: <tex> G = \left < V, E \right > </tex>. Его транзитивным остовом будет граф <tex> G^- = \left < V, E^- \right > </tex>.
Введём несколько обозначений:
* <tex> u \underset{G}{\to} v </tex> — {{---}} в графе <tex> G </tex> есть ребро из вершины <tex> u </tex> в <tex> v </tex>,* <tex> u \underset{G}{\leadsto} v </tex> — {{---}} в графе <tex> G </tex> есть путь (возможно, рёберно пустой) из вершины <tex> u </tex> в <tex> v </tex>,* <tex> u \underset{G}{\overset{+}{\leadsto}} v </tex> — {{---}} в графе <tex> G </tex> есть рёберно непустой путь из вершины <tex> u </tex> в <tex> v </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>.
}}
Докажем теорему, из которой следует алгоритм.
}}
=== Псевдокод Ассимптотика=== '''function''' <tex>f</tex>(Для множества <tex>X</tex>: '''List<T>''', c количеством элементов <tex>Rn</tex>: '''List<T>'''): алгоритм работает за <tex>RO(n^- = R3)</tex> '''foreach''' , так как в каждом из трёх циклов мы пробегаемся по всем элементам множества <tex>a \in X</tex> '''foreach''' <tex>b \in X</tex> '''foreach''' <tex>c \in X</tex> '''if''' <tex>aRb</tex> '''and''' <tex>bRc</tex> '''and''' <tex>aRc</tex> <tex>R^- </tex>.delete(pair<tex>\langle a, c\rangle</tex>)
==См. также==
