Изменения

'''Транзитивным остовом''' (''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R' ^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R' ^- </tex> равно транзитивному замыканию <tex> R </tex>.

Для удобства представим отношение в виде графа: <tex> G = \left < V, E \right > </tex>. Его транзитивным остовом будет граф <tex> G' ^- = \left < V, E' ^- \right > </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>.

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

<tex> R' ^- </tex> = <tex> R</tex> foreach <tex> a </tex> in <tex> X</tex> foreach <tex> b </tex> in <tex> X</tex> foreach <tex> c </tex> in <tex> X</tex> if <tex> aRb </tex> and <tex> bRc </tex> and <tex> aRc</tex> <tex> R'^- </tex>.delete(pair(<tex> a</tex>, <tex> c</tex>))

* [http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1987/1987-25.pdf J.A. La Poutré and J. van Leeuwen . «Maintenance of transitive closures and transitive reductions of graphs», 1987]