Транзитивный остов

Определение:

Транзитивным остовом (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] E' = \{ (k, m) \in E \ | \ \forall l: [ [/math] вершина [math] l [/math] достижима из [math] k ] \wedge (l, m) \in E \Longrightarrow k = l \} [/math]

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Псевдокод

 R' = R
 foreach a in X
   foreach b in X
     foreach c in X
       if aRb and bRc and aRc
         R'.delete(pair(a, c))

Источники

• Wikipedia: Transitive reduction
• J.A. La Poutré and J. van Leeuwen «Maintenance of transitive closures and transitive reductions of graphs», 1987