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

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

Транзитивным остовом (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] a, b, c \in X [/math] существуют [math] aRb, bRc, aRc [/math], то из [math] R' [/math] нужно исключить [math] \left \lt a, c \right \gt [/math].

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

Источники

• Wikipedia: Transitive reduction