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

Введем понятие транзитивного замыкания, связанное с бинарными отношениями, которое понадобится в дальнейшем.

Определение 11. Пусть отношение

задано на декартовом квадрате

некоторого множества

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

называется новое отношение

, состоящее из кортежей

, для которых выполняется:

либо кортеж

либо найдется конечная последовательность элементов

, такая, что все кортежи

принадлежат отношению

Очевидно, что

Пример 7. Пусть множество

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

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

причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением

("непосредственно используется в") и состоит из следующих кортежей:

Конструкция

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

Таблица 5 Отношение R

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

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

Конструкция

Где используется

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

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

Очевидный смысл замыкания

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

Содержание раздела

Главная сайта