Транзитивное замыкание

Эта статья о транзитивном замыкании отношения; о транзитивном замыкании множества см. Транзитивное замыкание множества.

Транзитивное замыкание в теории множеств — это операция на бинарных отношениях. Транзитивное замыкание бинарного отношения R на множестве X есть наименьшее транзитивное отношение на множестве X, включающее R.

Например, если X — это множество людей (и живых, и мёртвых), а R — отношение «является родителем», то транзитивное замыкание R — это отношение «является предком». Если X — это множество аэропортов, а xRy эквивалентно «существует рейс из x в y», и транзитивное замыкание R равно P, то xPy эквивалентно «можно долететь из x в y самолётом» (хотя иногда придётся лететь с пересадками)

Пример

Пусть множество A представляет собой следующее множество деталей и конструкций:

A = {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}

причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением R («непосредственно используется в») и состоит из следующих кортежей:

Конструкция	Где используется
Болт	Двигатель
Болт	Колесо
Гайка	Двигатель
Гайка	Колесо
Двигатель	Автомобиль
Колесо	Автомобиль
Ось	Колесо

Таблица 1. Отношение R.
Транзитивное замыкание состоит из кортежей (добавленные кортежи помечены жирным):

Конструкция	Где используется
Болт	Двигатель
Болт	Колесо
Гайка	Двигатель
Гайка	Колесо
Двигатель	Автомобиль
Колесо	Автомобиль
Ось	Колесо
Болт	Автомобиль
Гайка	Автомобиль
Ось	Автомобиль

Таблица 2. Транзитивное замыкание отношения R.

Очевидный смысл замыкания R состоит в описании включения деталей друг в друга не только непосредственно, а через использование их в промежуточных деталях, например, болт используется в автомобиле, так как он используется в двигателе, а двигатель используется в автомобиле.