Изменения

* <tex> u G^* v </tex> — в графе <tex> G </tex> есть путь (возможно, рёберно пустой) из вершины <tex> u </tex> в <tex> v </tex> (то есть вершина <tex> v </tex> достижима из <tex> u </tex>);

Пусть <tex> G^- = \left < V, E^- \right > </tex>. Тогда <tex> E^- = \left \{ (k, G m) \in E \ | \ \forall l: [ k G^* l \wedge (l, G m) \in E \Longrightarrow k = l ] \right \} </tex>

Докажем, что <tex> E^- \subseteq \left \{ (k, G m) \in E \ | \ \forall l: [ k G^* l \wedge (l, G m) \in E \Longrightarrow k = l ] \right \}</tex>:

Пусть <tex> G^- </tex> уже построен. Пусть <tex> (k, m) \in EG^- m </tex>. Тогда <tex> k \neq m </tex> (так как иначе удаление ребра <tex> (k, m) </tex> из <tex> E^- </tex> приведёт к образованию меньшего графа с тем же транзитивным замыканием, что нарушает условие минимальности транзитивного остова). Поэтому по определению транзитивного остова <tex> k G^+ m </tex>.

Пусть <tex> l </tex> — вершина, для которой выполняется <tex> k G^* l \wedge l G 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 (G^-)^+ l \wedge l (G^-)^+ 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 G^* l \wedge (l, G m) \in E \Longrightarrow k = l ] </tex>. Поскольку <tex> k G^+ m </tex>, существует такая вершина <tex> l </tex>, что <tex> k G^* l \wedge l G m </tex>, что приводит к выводу, что <tex> (k, G m) \in E </tex>.

Докажем, что <tex> \left \{ (k, G m) \in E \ | \ \forall l: [ k G^* l \wedge (l, G m) \in E \Longrightarrow k = l ] \right \} \subseteq E^- </tex>:

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

Так как множества <tex> E^- </tex> и <tex> \left \{ (k, G m) \in E \ | \ \forall l: [ k G^* l \wedge (l, G m) \in E \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, что и требовалось доказать.