13
правок
Изменения
Новая страница: «{{Определение |definition= '''Транзитивным остовом''' (''transitive reduction'') [[Определение отношения|отн...»
{{Определение
|definition=
'''Транзитивным остовом''' (''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
}}
__TOC__
== Алгоритм для антисимметричных отношений ==
Для удобства представим отношение в виде графа: <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=
'''Транзитивным замыканием''' графа <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}{\leadsto} j \right \} </tex>.
}}
Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.
Докажем теорему, из которой следует алгоритм.
{{Теорема
|statement=
Пусть <tex> G^- = \left < V, E^- \right > </tex>. Тогда <tex> E^- = \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex>
|proof=
Докажем, что <tex> E^- \subseteq \left \{ k \underset{G}{\to} m \ | \ \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 </tex>. Тогда <tex> k \neq m </tex> (так как иначе удаление ребра <tex> (k, m) </tex> из <tex> E^- </tex> приведёт к образованию меньшего графа с тем же транзитивным замыканием, что нарушает условие минимальности транзитивного остова). Поэтому по определению транзитивного остова <tex> k \underset{G}{\overset{+}{\leadsto}} m </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> G </tex> ацикличен, поэтому <tex> l \neq m </tex>. Поскольку <tex> G^* = (G^-)^* </tex>, верно <tex> k \underset{G^-}{\overset{+}{\leadsto}} l \wedge l \underset{G^-}{\overset{+}{\leadsto}} 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}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] </tex>. Поскольку <tex> k \underset{G}{\overset{+}{\leadsto}} m </tex>, существует такая вершина <tex> l </tex>, что <tex> k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m </tex>, что приводит к выводу, что <tex> k \underset{G}{\to} m </tex>.
Докажем, что <tex> \left \{ k \underset{G}{\to} m \ | \ \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> k G^- m </tex>, от противного. Предположим, что <tex> (k, m) \notin E^- </tex>. Поскольку <tex> G </tex> ацикличен, <tex> k \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> E^- </tex> и <tex> \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, что и требовалось доказать.
}}
=== Псевдокод ===
'''Set'''<tex>\langle</tex>'''Edge'''<tex>\rangle</tex> transitiveReduction(<tex>\mathtt{V}</tex>: '''Set'''<tex>\langle</tex>'''Vertex'''<tex>\rangle</tex>, <tex>\mathtt{E}</tex>: '''Set'''<tex>\langle</tex>'''Edge'''<tex>\rangle</tex>):
<tex>\mathtt{E^-} = \mathtt{E}</tex>
'''foreach''' <tex> a </tex> '''in''' <tex>\mathtt{V}</tex>
'''foreach''' <tex> b </tex> '''in''' <tex>\mathtt{V}</tex>
'''foreach''' <tex> c </tex> '''in''' <tex>\mathtt{V}</tex>
'''if''' (<tex> \langle a, b \rangle \in \mathtt{E} </tex> '''and''' <tex> \langle b, c \rangle \in \mathtt{E} </tex> '''and''' <tex> \langle a, c \rangle \in \mathtt{E} </tex>)
<tex>\mathtt{E^-} \setminus \{ \langle a, c \rangle \}</tex>
'''return''' <tex>\mathtt{E^-}</tex>
== Источники ==
* [http://en.wikipedia.org/wiki/Transitive_reduction Wikipedia: Transitive reduction]
* [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]
|definition=
'''Транзитивным остовом''' (''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
}}
__TOC__
== Алгоритм для антисимметричных отношений ==
Для удобства представим отношение в виде графа: <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=
'''Транзитивным замыканием''' графа <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}{\leadsto} j \right \} </tex>.
}}
Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.
Докажем теорему, из которой следует алгоритм.
{{Теорема
|statement=
Пусть <tex> G^- = \left < V, E^- \right > </tex>. Тогда <tex> E^- = \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex>
|proof=
Докажем, что <tex> E^- \subseteq \left \{ k \underset{G}{\to} m \ | \ \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 </tex>. Тогда <tex> k \neq m </tex> (так как иначе удаление ребра <tex> (k, m) </tex> из <tex> E^- </tex> приведёт к образованию меньшего графа с тем же транзитивным замыканием, что нарушает условие минимальности транзитивного остова). Поэтому по определению транзитивного остова <tex> k \underset{G}{\overset{+}{\leadsto}} m </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> G </tex> ацикличен, поэтому <tex> l \neq m </tex>. Поскольку <tex> G^* = (G^-)^* </tex>, верно <tex> k \underset{G^-}{\overset{+}{\leadsto}} l \wedge l \underset{G^-}{\overset{+}{\leadsto}} 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}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] </tex>. Поскольку <tex> k \underset{G}{\overset{+}{\leadsto}} m </tex>, существует такая вершина <tex> l </tex>, что <tex> k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m </tex>, что приводит к выводу, что <tex> k \underset{G}{\to} m </tex>.
Докажем, что <tex> \left \{ k \underset{G}{\to} m \ | \ \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> k G^- m </tex>, от противного. Предположим, что <tex> (k, m) \notin E^- </tex>. Поскольку <tex> G </tex> ацикличен, <tex> k \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> E^- </tex> и <tex> \left \{ k \underset{G}{\to} m \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, что и требовалось доказать.
}}
=== Псевдокод ===
'''Set'''<tex>\langle</tex>'''Edge'''<tex>\rangle</tex> transitiveReduction(<tex>\mathtt{V}</tex>: '''Set'''<tex>\langle</tex>'''Vertex'''<tex>\rangle</tex>, <tex>\mathtt{E}</tex>: '''Set'''<tex>\langle</tex>'''Edge'''<tex>\rangle</tex>):
<tex>\mathtt{E^-} = \mathtt{E}</tex>
'''foreach''' <tex> a </tex> '''in''' <tex>\mathtt{V}</tex>
'''foreach''' <tex> b </tex> '''in''' <tex>\mathtt{V}</tex>
'''foreach''' <tex> c </tex> '''in''' <tex>\mathtt{V}</tex>
'''if''' (<tex> \langle a, b \rangle \in \mathtt{E} </tex> '''and''' <tex> \langle b, c \rangle \in \mathtt{E} </tex> '''and''' <tex> \langle a, c \rangle \in \mathtt{E} </tex>)
<tex>\mathtt{E^-} \setminus \{ \langle a, c \rangle \}</tex>
'''return''' <tex>\mathtt{E^-}</tex>
== Источники ==
* [http://en.wikipedia.org/wiki/Transitive_reduction Wikipedia: Transitive reduction]
* [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]
