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

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

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

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

Приклади

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

Див. також

• Транзитивне відношення
• Транзитивне замикання
• Діаграми Гассе

Джерела

• Шаблон:Куратовский.Мостовский.Теория множеств
• Шаблон:Ван.дер.Варден.Алгебра