Транзитивне скорочення

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Транзитивне скорочення бінарного відношення R на множині X — це найменше відношення на множині X, транзитивне замикання якого збігається з транзитивним замиканням R.

«Найменше відношення» визначається за допомогою відношення включення.

Якщо транзитивне замикання R є антисиметричним та скінченним, тоді транизитивне скорочення буде єдиним.

Приклади[ред.ред. код]

В теорії графів бінарне відношення на множині представляється орієнтованим графом. На малюнках: граф нетранзитивного відношення (зліва), граф його транзитивного скорочення (справа).

Tred-G.png Tred-Gprime.png

Див. також[ред.ред. код]

Джерела[ред.ред. код]