65
правок
Изменения
Нет описания правки
Введём несколько обозначений:
* <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>.
Также введём определение транзитивного замыкания в терминах теории графов:
Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.
===Описание алгоритма===
Рассмотрим всевозможные комбинации из трёх любых элементов <tex>a, b, c \in X</tex>. И если для этих элементов существуют отношения <tex>aRb</tex>, <tex>bRc</tex> и <tex>aRc</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^- </tex>.delete(pair<tex>\langle a, c\rangle</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> включены друг в друга, они совпадают, то есть равны.
}}
==См. также==
