418
правок
Изменения
Нет описания правки
'''Транзитивным остовом''' (''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R' </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R' </tex> равно транзитивному замыканию <tex> R </tex>.
}}
== Алгоритм ==
Воспользуемся определениями транзитивного замыкания и [[Транзитивное отношение|транзитивного отношения]]. Изначально <tex> R' = R </tex>. Очевидно, что если для <tex> a, b, c \in X </tex> существуют <tex> aRb, bRc, aRc </tex>, то из <tex> R' </tex> нужно исключить <tex> \left < a, c \right > </tex>.
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))
== Источники ==
* [http://en.wikipedia.org/wiki/Transitive_reduction Wikipedia: Transitive reduction]
