Изменения

Перейти к: навигация, поиск

Транзитивный остов

418 байт добавлено, 01:11, 9 января 2017
Описание алгоритма
Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </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>. 
=== Псевдокод ===
'''function''' <tex>f</tex>(<tex>X</tex>: '''List<T>''', <tex>R</tex>: '''List<T>'''):
65
правок

Навигация