Участник:D1v1nation/TR — различия между версиями

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

Текущая версия на 04:30, 15 июня 2016

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


Алгоритм построения для антисимметричных отношений

Определения и обозначения

Для удобства представим отношение в виде графа: [math] G = \left \lt V, E \right \gt [/math]. Его транзитивным остовом будет граф [math] G^- = \left \lt V, E^- \right \gt [/math].

Введём несколько обозначений:

  • [math] u \underset{G}{\to} v [/math] — в графе [math] G [/math] есть ребро из вершины [math] u [/math] в [math] v [/math];
  • [math] u \underset{G}{\leadsto} v [/math] — в графе [math] G [/math] есть путь (возможно, рёберно пустой) из вершины [math] u [/math] в [math] v [/math];
  • [math] u \underset{G}{\overset{+}{\leadsto}} v [/math] — в графе [math] G [/math] есть рёберно непустой путь из вершины [math] u [/math] в [math] v [/math].

Также введём определение транзитивного замыкания в терминах теории графов:

Определение:
Транзитивным замыканием графа [math] G = \left \lt V, E \right \gt [/math] называется граф [math] G^* = \left \lt V, E^* \right \gt [/math], где [math] E^* = \left \{ (i, j) \in V \times V \mid i \underset{G}{\leadsto} j \right \} [/math].


Теоретическое обоснование алгоритма

Утверждение:
Граф [math] G [/math] ацикличен, то есть в нём выполняется следующее: [math] \forall i, j \in V \colon i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j [/math].
[math]\triangleright[/math]
От противного: пусть [math] \exists i, j \in V \colon i \underset{G}{\overset{+}{\leadsto}} j, j \underset{G}{\overset{+}{\leadsto}} i, i \neq j[/math]. По антисимметричности исходного отношения получаем [math] i = j [/math], что противоречит предположению.
[math]\triangleleft[/math]

Докажем теорему, из которой следует алгоритм.

Теорема:
Пусть [math] G^- = \left \lt V, E^- \right \gt [/math]. Тогда [math] E^- = \left \{ k \underset{G}{\to} m \mid \forall l \colon [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} [/math]
Доказательство:
[math]\triangleright[/math]
  • Докажем, что [math] E^- \subseteq \left \{ k \underset{G}{\to} m \mid \forall l \colon [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \}[/math]:

Пусть [math] G^- [/math] уже построен. Пусть [math] k \underset{G^-}{\to} m [/math]. Тогда [math] k \neq m [/math] (так как иначе удаление ребра [math] (k, m) [/math] из [math] E^- [/math] приведёт к образованию меньшего графа с тем же транзитивным замыканием, что нарушает условие минимальности транзитивного остова). Поэтому по определению транзитивного остова [math] k \underset{G}{\overset{+}{\leadsto}} m [/math].

Пусть [math] l [/math] — вершина, для которой выполняется [math] k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m [/math]. Докажем, что [math] k = l [/math], от противного. Пусть [math] k \neq l [/math]. [math] G [/math] ацикличен, поэтому [math] l \neq m [/math]. Поскольку [math] G^* = (G^-)^* [/math], верно [math] k \underset{G^-}{\overset{+}{\leadsto}} l \wedge l \underset{G^-}{\overset{+}{\leadsto}} m [/math]. Поскольку [math] G^- [/math] ацикличен, путь из [math] k [/math] в [math] l [/math] не может содержать ребра [math] (k, m) [/math], аналогично путь из [math] l [/math] в [math] m [/math] не может содержать [math] (k, m) [/math]. Поэтому в [math] G^- [/math] существует путь из [math] k [/math] в [math] m [/math], не содержащий в себе ребро [math] (k, m) [/math], значит, удаление [math] (k, m) [/math] из [math] E^- [/math] не изменит транзитивное замыкание, что противоречит условию минимальности [math] E^- [/math]. Поэтому [math] \forall l \colon [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] [/math]. Поскольку [math] k \underset{G}{\overset{+}{\leadsto}} m [/math], существует такая вершина [math] l [/math], что [math] k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m [/math], что приводит к выводу, что [math] k \underset{G}{\to} m [/math].

  • Докажем, что [math] \left \{ k \underset{G}{\to} m \mid \forall l \colon [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} \subseteq E^- [/math]:

Предположим, что [math] k \underset{G}{\to} m [/math] и [math] \forall l \colon [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] [/math]. Докажем, что [math] k G^- m [/math], от противного. Предположим, что [math] (k, m) \notin E^- [/math]. Поскольку [math] G [/math] ацикличен, [math] k \neq m [/math] и поэтому [math] k \underset{G^-}{\overset{+}{\leadsto}} m [/math]. Поскольку [math] (k, m) \notin E^- [/math], существует вершина [math] l [/math] такая, что [math] k \underset{G^-}{\leadsto} l \wedge l \underset{G^-}{\leadsto} m [/math] и [math] k \neq l \neq m [/math], поэтому [math] k \underset{G}{\overset{+}{\leadsto}} l \wedge l \underset{G}{\overset{+}{\leadsto}} m [/math]. Поскольку [math] G [/math] ацикличен, существует вершина [math] l' \neq k [/math], для которой выполняется [math] k \underset{G}{\overset{+}{\leadsto}} l' \wedge l' \underset{G}{\to} m [/math], что противоречит нашему предположению.

  • Так как множества [math] E^- [/math] и [math] \left \{ k \underset{G}{\to} m \mid \forall l \colon [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} [/math] включены друг в друга, они совпадают, что и требовалось доказать.
[math]\triangleleft[/math]

Псевдокод

 Set[math]\langle[/math]Edge[math]\rangle[/math] transitiveReduction([math]V[/math]: Set[math]\langle[/math]Vertex[math]\rangle[/math], [math]E[/math]: Set[math]\langle[/math]Edge[math]\rangle[/math]):
   [math]E^- = E[/math]
   for [math] a \in V[/math]
     for [math] b \in V[/math]
       for [math] c \in V[/math]
         if ([math] \langle a, b \rangle \in E [/math]) and ([math] \langle b, c \rangle \in E [/math]) and ([math] \langle a, c \rangle \in E [/math])
           [math]E^- = E^- \setminus \{ \langle a, c \rangle \}[/math]
   return [math]E^-[/math]

См. также

Источники

[[Категория: Дискретная математика и алгоритмы]] [[Категория:Отношения]] плашечки раскомментируем после мёрджа