Изменения

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

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

2 байта убрано, 01:15, 9 января 2017
Нет описания правки
__TOC__
== Алгоритм для антисимметричных отношений ==
===Описание алгоритма===
Чтобы найти минимальное отношение <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>'''):
<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^-\setminus(a, c)</tex>
 
===Доказательство корректности===
Для удобства представим отношение в виде [[Основные определения теории графов|графа]]: <tex> G = \left < V, E \right > </tex>. Его транзитивным остовом будет граф <tex> G^- = \left < V, E^- \right > </tex>.
'''Транзитивным замыканием''' графа <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>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>'''):
<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^-\setminus(a, c)</tex>
===Доказательство корректности===
Докажем теорему, из которой следует алгоритм.
65
правок

Навигация