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

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

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

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

Приклади

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

Див. також

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

Джерела

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

• Ван дер Варден Б. Л. Алгебра. — Москва : Наука, 1975. — 623 с. — ISBN 5-8114-0552-9.(рос.)