Изменения

'''Транзитивным остовом''' (или '''транзитивным сокращением''', англ. ''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>'''): <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>. }}Так как отношение антисимметричнои транзитивно, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>. Докажем теорему, из которой следует алгоритм.

Пусть <tex> G^- = \left < V, E^- \right > </tex>. Тогда <tex> E' ^- = \left \{ (k, m) \in E underset{G}{\ | to} m \ mid \forall l: [ </tex> вершина <tex> k \underset{G}{\leadsto} l </tex> достижима из <tex> k ] \wedge (l, \underset{G}{\to} m) \in E \Longrightarrow k = l ] \right \} </tex>

Докажем, что <tex> E^- \subseteq \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> G^- </tex> уже построен. Пусть <tex> (k, \underset{G^-}{\to} m) \in E' </tex>. Тогда <tex> k \neq m </tex> (так как иначе после удаления удаление ребра <tex> (k, m) </tex> из <tex> E' ^- </tex> получится меньший граф приведёт к образованию меньшего графа с тем же транзитивным замыканием, что противоречит определениюнарушает условие минимальности транзитивного остова). Поэтому в пути от по определению транзитивного остова <tex> k </tex> к <tex> \underset{G}{\overset{+}{\leadsto}} m </tex> в графе <tex> G </tex> есть как минимум одно ребро.Возьмём :Пусть <tex> l </tex> такую— вершина, что для которой выполняется <tex> k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m </tex> достижима из . Докажем, что <tex> k = l </tex>, и есть ребро из от противного. Пусть <tex> k \neq l </tex> в <tex> m </tex>. Предположим, что <tex> k \neq l G </tex>. Так как граф ацикличен, поэтому <tex> l \neq m </tex>. Так же так как транзитивное замыкание Поскольку <tex> G </tex> равно транзитивному замыканию <tex> ^* = (G' ^-)^* </tex>, в графе верно <tex> k \underset{G' </tex> вершина <tex> ^-}{\overset{+}{\leadsto}} l \wedge l </tex> достижима из <tex> k </tex>, а <tex> \underset{G^-}{\overset{+}{\leadsto}} m </tex> — из <tex> l </tex>. Поскольку <tex> G' ^- </tex> также ацикличен, поэтому в пути от путь из <tex> k </tex> к в <tex> l </tex> не может быть содержать ребра <tex> (k, m) </tex>. Также в пути от , аналогично путь из <tex> l </tex> к в <tex> m </tex> не может быть ребра содержать <tex> (k, m) </tex>. Поэтому существует путь в <tex> G' ^- </tex> от существует путь из <tex> k </tex> к в <tex> m </tex>, который не содержит содержащий в себе ребро <tex> (k, m) </tex>. Поэтому , значит, удаление ребра не изменяет транзитивное замыкание.Теперь предположим, что <tex> (k, m) \notin </tex> из <tex> E' ^- </tex>. Так как не изменит транзитивное замыкание, что противоречит условию минимальности <tex> G E^- </tex> ацикличен, . Поэтому <tex> \forall l: [ k \neq underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] </tex> и отсюда в . Поскольку <tex> k \underset{G' }{\overset{+}{\leadsto}} m </tex> , существует такая вершина <tex> m l </tex> достижима из , что <tex> k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m </tex>. Поскольку , что приводит к выводу, что <tex> (k, \underset{G}{\to} m) \notin 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 \} \subseteq E^- </tex> такая: :Предположим, что есть путь из <tex> k \underset{G}{\to} m </tex> в и <tex> \forall l : [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] </tex> и из . Докажем, что <tex> l k G^- m </tex> в , от противного. Предположим, что <tex> (k, m ) \notin E^- </tex>. Поскольку <tex> G </tex> ацикличен, и <tex> k \neq l \neq m </tex>. Это значит, что в и поэтому <tex> k \underset{G ^-}{\overset{+}{\leadsto}} m </tex> что есть путь из . Поскольку <tex> (k , m) \notin E^- </tex> в , существует вершина <tex> l </tex> и из такая, что <tex> k \underset{G^-}{\leadsto} l \wedge l \underset{G^-}{\leadsto} m </tex> в и <tex> k \neq l \neq m </tex> (причём в каждом пути будет как минимум по одному ребру). Поскольку , поэтому <tex> k \underset{G }{\overset{+}{\leadsto}} l \wedge l \underset{G}{\overset{+}{\leadsto}} m </tex> ацикличен, это значит, что в . Поскольку <tex> G </tex> ацикличен, существует вершина <tex> l' \neq k </tex> такая, что есть путь как минимум в одно ребро из для которой выполняется <tex> k \underset{G}{\overset{+}{\leadsto}} l' \wedge l' \underset{G}{\to} m </tex> в , что противоречит нашему предположению. Так как множества <tex> l' 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>. Это противоречит нашему предположениювключены друг в друга, они совпадают, то есть равны.

=== Псевдокод Ассимптотика=== R' = R foreach a in Для множества <tex>X foreach b in X foreach </tex> c in количеством элементов <tex>n</tex> алгоритм работает за <tex>O(n^3)</tex>, так как в каждом из трёх циклов мы пробегаемся по всем элементам множества <tex>X</tex>. if aRb and bRc and aRc R'==См.delete(pair(aтакже==* [[Транзитивное замыкание]]* [[Остовные деревья: определения, c))лемма о безопасном ребре]]

== Источники информации ==

* ''J.A. La Poutré and J. van Leeuwen . «Maintenance of transitive closures and transitive reductions of graphs»'', 1987. [[Категория: Дискретная математика и алгоритмы]][[Категория: Отношения ]]