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

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

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

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

Приклади

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

Див. також

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

Джерела

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

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