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

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

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

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

задано на декартовом квадрате некоторого множества . Транзитивным замыканием отношения называется новое отношение , состоящее из кортежей , для которых выполняется:

• либо кортеж
  
  ,

• либо найдется конечная последовательность элементов
  
  , такая, что все кортежи
  
  принадлежат отношению
  
  .

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

.

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

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

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

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

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

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

---

---

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

---