Изменения

== Алгоритм для антисимметричных отношений ==Воспользуемся определениями транзитивного замыкания и [[Транзитивное Для удобства представим отношение|транзитивного отношения]]в виде графа: <tex> G = \left < V, E \right > </tex>. Изначально Его транзитивным остовом будет граф <tex> RG' = R \left < V, E' \right > </tex>. ОчевидноТак как отношение антисимметрично, что если для то граф ацикличен. {{Теорема|statement=<tex> aE' = \{ (k, bm) \in E \ | \ \forall l: [ </tex> вершина <tex> l </tex> достижима из <tex> k ] \wedge (l, c m) \in X E \Longrightarrow k = l \} </tex> существуют |proof=Пусть <tex> aRb(k, bRcm) \in E' </tex>. Тогда <tex> k \neq m </tex> (иначе после удаления ребра <tex> (k, aRc m) </tex> из <tex> E' </tex>получится меньший граф с тем же транзитивным замыканием, то что противоречит определению). Поэтому в пути от <tex> k </tex> к <tex> m </tex> в графе <tex> G </tex> есть как минимум одно ребро.Предположим, что <tex> k \neq l </tex>. Так как граф ацикличен, <tex> l \neq m </tex>. Так же так как транзитивное замыкание <tex> G </tex> равно транзитивному замыканию <tex> G' </tex>, в графе <tex> G' </tex> вершина <tex> l </tex> достижима из <tex> k </tex>, а <tex> m </tex> — из <tex> Rl </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) \left notin E' </tex>. Так как <tex> G </tex> ацикличен, <tex> k \neq m </tex> и отсюда в <tex> G' </tex> вершина <tex> m </tex> достижима из <tex> k </tex>. Поскольку <tex> (k, m) \notin E' </tex>, существует вершина <tex> l </tex> такая, что есть путь из <tex> k </tex> в <tex> l </tex> и из <tex> l </tex> в <tex> m < a/tex>, c и <tex> k \neq l \right neq m </tex>. Это значит, что в <tex> G </tex> что есть путь из <tex> k </tex> в <tex> l </tex> и из <tex> l </tex> в <tex> m </tex> (причём в каждом пути будет как минимум по одному ребру). Поскольку <tex> G </tex> ацикличен, это значит, что в <tex> G </tex> существует вершина <tex> l' </tex> такая, что есть путь как минимум в одно ребро из <tex> k </tex> в <tex> l' </tex> и есть ребро <tex> (l', m) </tex>.Это противоречит нашему предположению.}} === Псевдокод ===

for (each foreach a in X) for (each foreach b in X) for (each foreach c in X) if (aRb and bRc and aRc)