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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Доказательство корректности: Если отношение ТОЛЬКО антисимметрично, то граф может иметь цикл)
 
(не показано 7 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Транзитивным остовом''' (англ. ''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
+
'''Транзитивным остовом''' (или '''транзитивным сокращением''', англ. ''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
 
}}
 
}}
  
 
__TOC__
 
__TOC__
 
== Алгоритм для антисимметричных отношений ==
 
== Алгоритм для антисимметричных отношений ==
 +
===Описание алгоритма===
 +
Пусть первоначально <tex>R^-=R</tex>.
 +
 +
Чтобы сделать <tex>R^-</tex> минимальным отношением на <tex>X</tex>, таким, что транзитивное замыкание <tex>R^-</tex> будет равно транзитивному замыканию <tex>R</tex>, рассмотрим всевозможные комбинации из каждых трёх элементов <tex>a, b, c \in X</tex>. Если для этих элементов существует каждое из отношений: <tex>aRb</tex>, <tex>bRc</tex> и <tex>aRc</tex>, {{---}} то исключим отношение <tex>aRc</tex> из <tex>R^-</tex>. После проверки всех комбинаций и исключения ненужных отношений получаем искомое отношение <tex>R^-</tex>.
 +
 +
=== Псевдокод ===
 +
  '''function''' <tex>f</tex>(<tex>X</tex>: '''List<T>''', <tex>R</tex>: '''List<T>'''):
 +
    <tex>R^- = R</tex>
 +
    '''foreach''' <tex>a \in X</tex>
 +
      '''foreach''' <tex>b \in X</tex>
 +
        '''foreach''' <tex>c \in X</tex>
 +
          '''if''' <tex>aRb</tex> '''and''' <tex>bRc</tex> '''and''' <tex>aRc</tex>
 +
            <tex>R^- = R^-\setminus(a, c)</tex>
 +
 +
===Доказательство корректности===
 
Для удобства представим отношение в виде [[Основные определения теории графов|графа]]: <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: Строка 31:
 
{{Определение
 
{{Определение
 
|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 \mid i \underset{G}{\leadsto} j \right \} </tex>.
+
'''Транзитивным замыканием''' (англ. ''transitive closure'') графа <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>.
 
}}
 
}}
+
Так как отношение антисимметрично и транзитивно, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.
Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.
 
===Описание алгоритма===
 
Чтобы найти минимальное отношение <tex>R^-</tex> на <tex>X</tex> такое, что транзитивное замыкание <tex>R^-</tex> равно транзитивному замыканию <tex>R</tex>, рассмотрим всевозможные комбинации из каждых трёх элементов <tex>a, b, c \in X</tex>. И если для этих элементов существуют отношения <tex>aRb</tex>, <tex>bRc</tex> и <tex>aRc</tex>, то избавимся от отношения <tex>aRc</tex>. После проверки всех комбинаций получаем отношение <tex>R^-</tex>.
 
  
=== Псевдокод ===
 
  '''function''' <tex>f</tex>(<tex>X</tex>: '''List<T>''', <tex>R</tex>: '''List<T>'''):
 
    <tex>R^- = R</tex>
 
    '''foreach''' <tex>a \in X</tex>
 
      '''foreach''' <tex>b \in X</tex>
 
        '''foreach''' <tex>c \in X</tex>
 
          '''if''' <tex>aRb</tex> '''and''' <tex>bRc</tex> '''and''' <tex>aRc</tex>
 
            <tex>R^-\setminus(a, c)</tex>
 
 
===Доказательство корректности===
 
 
Докажем теорему, из которой следует алгоритм.
 
Докажем теорему, из которой следует алгоритм.
  
Строка 51: Строка 53:
 
Так как множества <tex> E^- </tex> и <tex> \left \{  k \underset{G}{\to} m \mid  \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: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, то есть равны.
 
}}
 
}}
 +
 +
===Ассимптотика===
 +
Для множества <tex>X</tex> c количеством элементов <tex>n</tex> алгоритм работает за <tex>O(n^3)</tex>, так как в каждом из трёх циклов мы пробегаемся по всем элементам множества <tex>X</tex>.
  
 
==См. также==
 
==См. также==

Текущая версия на 21:54, 10 сентября 2018

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


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

Описание алгоритма[править]

Пусть первоначально [math]R^-=R[/math].

Чтобы сделать [math]R^-[/math] минимальным отношением на [math]X[/math], таким, что транзитивное замыкание [math]R^-[/math] будет равно транзитивному замыканию [math]R[/math], рассмотрим всевозможные комбинации из каждых трёх элементов [math]a, b, c \in X[/math]. Если для этих элементов существует каждое из отношений: [math]aRb[/math], [math]bRc[/math] и [math]aRc[/math], — то исключим отношение [math]aRc[/math] из [math]R^-[/math]. После проверки всех комбинаций и исключения ненужных отношений получаем искомое отношение [math]R^-[/math].

Псевдокод[править]

 function [math]f[/math]([math]X[/math]: List<T>, [math]R[/math]: List<T>):
   [math]R^- = R[/math]
   foreach [math]a \in X[/math]
     foreach [math]b \in X[/math]
       foreach [math]c \in X[/math]
         if [math]aRb[/math] and [math]bRc[/math] and [math]aRc[/math]
           [math]R^- = R^-\setminus(a, c)[/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].

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

Определение:
Транзитивным замыканием (англ. transitive closure) графа [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] \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 \mid \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 \mid \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 \mid \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 \mid \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} [/math] включены друг в друга, они совпадают, то есть равны.
[math]\triangleleft[/math]

Ассимптотика[править]

Для множества [math]X[/math] c количеством элементов [math]n[/math] алгоритм работает за [math]O(n^3)[/math], так как в каждом из трёх циклов мы пробегаемся по всем элементам множества [math]X[/math].

См. также[править]

Источники информации[править]