Изменения

Для удобства представим отношение в виде графа: <tex> G = \left < V, E \right > </tex>. Его транзитивным остовом будет граф <tex> G' = \left < V, E' \right > </tex>.  Введём несколько обозначений:* <tex> u \underset{G}{\longrightarrow} v </tex> — в графе <tex> G </tex> есть ребро из вершины <tex> u </tex> в <tex> v </tex>;* <tex> u \underset{G}{\overset{*}{\longrightarrow}} v </tex> — в графе <tex> G </tex> есть путь (возможно, пустой) из вершины <tex> u </tex> в <tex> v </tex> (то есть вершина <tex> v </tex> достижима из <tex> u </tex>);* <tex> u \underset{G}{\overset{+}{\longrightarrow}} v </tex> — в графе <tex> G </tex> есть непустой путь из вершины <tex> u </tex> в <tex> v </tex>. Также введём определение транзитивного замыкания в терминах теории графов: {{Определение|definition='''Транзитивным замыканием''' графа <tex> G = \left < V, E \right > </tex> называется граф <tex> G^* = \left < V, E^* \right > </tex>, где <tex> E^* = \left \{ (i, j) \in V \times V | i \underset{G}{\overset{*}{\longrightarrow}} j \right \} </tex>.}} Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\longrightarrow}} j \Longrightarrow i \neq j </tex>. Докажем теорему, из которой следует алгоритм.

<tex> E' = \left \{ (k, m) \in E \ | \ \forall l: [ </tex> вершина <tex> k \underset{G}{\overset{*}{\longrightarrow}} l </tex> достижима из <tex> k ] \wedge (l, m) \in E \Longrightarrow k = l ] \right \} </tex>

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