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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Псевдокод)
Строка 41: Строка 41:
  
 
=== Псевдокод ===
 
=== Псевдокод ===
   <tex> R^- </tex> = <tex> R </tex>
+
   '''function''' f(X: '''vector<T>''', R: '''vector<T>'''):
  '''foreach''' <tex> a </tex> '''in''' <tex> X </tex>
+
    R<tex>^- </tex> = R
    '''foreach''' <tex> b </tex> '''in''' <tex> X </tex>
+
    '''foreach''' a '''in''' X
      '''foreach''' <tex> c </tex> '''in''' <tex> X </tex>
+
      '''foreach''' b '''in''' X
        '''if''' <tex> aRb </tex> '''and''' <tex> bRc </tex> '''and''' <tex> aRc </tex>
+
        '''foreach''' c '''in''' X
          <tex> R^- </tex>.delete(pair<tex>\langle a </tex>, <tex> c \rangle</tex>)
+
          '''if''' aRb '''and''' bRc '''and''' aRc
 +
            R<tex>^- </tex>.delete(pair<tex>\langle</tex>a, c<tex>\rangle</tex>)
  
 
== Источники информации ==
 
== Источники информации ==

Версия 21:14, 8 января 2017

Определение:
Транзитивным остовом (англ. 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 | i \underset{G}{\leadsto} j \right \} [/math].


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

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

Теорема:
Пусть [math] G^- = \left \lt V, E^- \right \gt [/math]. Тогда [math] E^- = \left \{ k \underset{G}{\to} m \ | \ \forall l: [ 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 \ | \ \forall l: [ 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: [ 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 \ | \ \forall l: [ 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: [ 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 \ | \ \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} [/math] включены друг в друга, они совпадают, то есть равны.
[math]\triangleleft[/math]

Псевдокод

 function f(X: vector<T>, R: vector<T>):
   R[math]^- [/math] = R
   foreach a in X
     foreach b in X
       foreach c in X
         if aRb and bRc and aRc
           R[math]^- [/math].delete(pair[math]\langle[/math]a, c[math]\rangle[/math])

Источники информации