Транзитивное замыкание
Транзитивное замыкание в теории множеств — это операция на бинарных отношениях. Транзитивное замыкание бинарного отношения R на множестве X есть наименьшее транзитивное отношение на множестве X, включающее R.
Например, если X — это множество людей (и живых, и мёртвых), а R — отношение «является родителем», то транзитивное замыкание R — это отношение «является предком». Если X — это множество аэропортов, а xRy эквивалентно «существует рейс из x в y», и транзитивное замыкание R равно P, то xPy эквивалентно «можно долететь из x в y самолётом» (хотя иногда придётся лететь с пересадками)
Пример
правитьПусть множество A представляет собой следующее множество деталей и конструкций:
A = {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}
причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением R («непосредственно используется в») и состоит из следующих кортежей:
Конструкция | Где используется |
---|---|
Болт | Двигатель |
Болт | Колесо |
Гайка | Двигатель |
Гайка | Колесо |
Двигатель | Автомобиль |
Колесо | Автомобиль |
Ось | Колесо |
Таблица 1. Отношение R.
Транзитивное замыкание состоит из кортежей (добавленные кортежи помечены жирным):
Конструкция | Где используется |
---|---|
Болт | Двигатель |
Болт | Колесо |
Гайка | Двигатель |
Гайка | Колесо |
Двигатель | Автомобиль |
Колесо | Автомобиль |
Ось | Колесо |
Болт | Автомобиль |
Гайка | Автомобиль |
Ось | Автомобиль |
Таблица 2. Транзитивное замыкание отношения R.
Очевидный смысл замыкания R состоит в описании включения деталей друг в друга не только непосредственно, а через использование их в промежуточных деталях, например, болт используется в автомобиле, так как он используется в двигателе, а двигатель используется в автомобиле.
Для улучшения этой статьи по математике желательно:
|