Транзитивный остов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм для антисимметричных отношений)
м (Алгоритм для антисимметричных отношений)
Строка 29: Строка 29:
 
Докажем, что <tex> E^- \subseteq \left \{  (k, m) \in E \ | \  \forall l: [ k G^* l \wedge (l, m) \in E \Longrightarrow k = l ] \right \}</tex>:
 
Докажем, что <tex> E^- \subseteq \left \{  (k, m) \in E \ | \  \forall l: [ k G^* 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, m) </tex> из <tex> E^- </tex> приведёт к образованию меньшего графа с тем же транзитивным замыканием, что нарушает условие минимальности транзитивного остова). Поэтому по определению транзитивного остова <tex> k G^+ m </tex>. Пусть <tex> l </tex> — вершина, для которой выполняется <tex> k G^* \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, m) \in E \Longrightarrow k = l ] </tex>. Поскольку <tex> k G^+ m </tex>, существует такая вершина <tex> l </tex>, что <tex> k G^* \wedge l G m </tex>, что приводит к выводу, что <tex> (k, m) \in E </tex>.
+
Пусть <tex> G^- </tex> уже построен. Пусть <tex> (k, m) \in E^- </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, m) \in E \Longrightarrow k = l ] </tex>. Поскольку <tex> k G^+ m </tex>, существует такая вершина <tex> l </tex>, что <tex> k G^* \wedge l G m </tex>, что приводит к выводу, что <tex> (k, m) \in E </tex>.
  
 
Докажем, что <tex> \left \{  (k, m) \in E \ | \  \forall l: [ k G^* l \wedge (l, m) \in E \Longrightarrow k = l ] \right \} \subseteq  E^- </tex>:
 
Докажем, что <tex> \left \{  (k, m) \in E \ | \  \forall l: [ k G^* l \wedge (l, m) \in E \Longrightarrow k = l ] \right \} \subseteq  E^- </tex>:

Версия 19:32, 6 июня 2012

Определение:
Транзитивным остовом (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 G v [/math] — в графе [math] G [/math] есть ребро из вершины [math] u [/math] в [math] v [/math];
  • [math] u G^* v [/math] — в графе [math] G [/math] есть путь (возможно, рёберно пустой) из вершины [math] u [/math] в [math] v [/math] (то есть вершина [math] v [/math] достижима из [math] u [/math]);
  • [math] u G^+ 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 | i G^* j \right \} [/math].


Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: [math] \forall i, j \in V: i G^+ j \Longrightarrow i \neq j [/math].

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

Теорема:
Пусть [math] G^- = \left \lt V, E^- \right \gt [/math]. Тогда [math] E^- = \left \{ (k, m) \in E \ | \ \forall l: [ k G^* l \wedge (l, m) \in E \Longrightarrow k = l ] \right \} [/math]
Доказательство:
[math]\triangleright[/math]

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

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

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

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

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

Псевдокод

 [math] R^- [/math] = [math] R [/math]
 foreach [math] a [/math] in [math] X [/math]
   foreach [math] b [/math] in [math] X [/math]
     foreach [math] c [/math] in [math] X [/math]
       if [math] aRb [/math] and [math] bRc [/math] and [math] aRc [/math]
         [math] R^- [/math].delete(pair([math] a [/math], [math] c [/math]))

Источники